algorithm - 最大化董事会得分

Question

棋盘是一个简单的 31 x 31 象棋网格。

• 每个方格上最多可以放置一个棋子(技术上最多可以放置 961 个棋子)
• Pieces 授予 [16 - taxicab_distance_from_middle_square] 分数(不能低于 0 分)
• 但每 block 棋子的得分是其得分的 1/24 乘以以该棋子为中心的 5 x 5 正方形内的所有其他棋子
  • 所以完全包围的棋子完全没有分数
  • 被其他 12 个棋子包围的棋子恰好获得原始分数的一半
• 目标当然是找到得分最高的棋子排列方式

我试过运行一个程序，每次将一个棋子放在任何能给出最高分的地方，但由于每次放置都会影响其他棋子的分数，所以结果显然不是最理想的。

找到(或至少接近)得分最高的棋盘状态的最佳方法是什么？

Answer 1

好的解决方案似乎具有一种有趣的结构。这是一个值为 879.25 的解决方案:

0000000000000001000000000000000
0000000000000011100000000000000
0000000000000001000000000000000
0000000000001001001000000000000
0000000000011111111100000000000
0000000000001001001000000000000
0000000000000000000000000000000
0000000011111111111111100000000
0000000111111111111111110000000
0000000000000000000000000000000
0000000000000000000000000000000
0000111111111111111111111110000
0001111111111111111111111111000
0000000000000000000000000000000
0000000000000000000000000000000
1111111111111111111111111111111
0111111111111111111111111111110
0000000000000000000000000000000
0000000000000000000000000000000
0000111111111111111111111110000
0000011111111111111111111100000
0000000000000000000000000000000
0000000000000000000000000000000
0000000011111111111111100000000
0000000001111111111111000000000
0000000000000000000000000000000
0000000000001001001000000000000
0000000000001111111000000000000
0000000000000011000000000000000
0000000000000001000000000000000
0000000000000001000000000000000

我通过模拟退火找到了这个解，以及它的 7 次旋转和反射。

如果您“猜测”中间的一排行如上，您会在上述一排行的上方和下方得到可管理的小子问题。例如，您可以通过动态规划找到这些子问题的最优解。