algorithm - 如何在八字游戏中的两个后代棋盘排列中做出选择？

Question

我正在尝试编写 8 谜题求解器，但我还不能：我使用曼哈顿优先级函数，我想知道，如果后代棋盘排列具有相同的优先级值，如何在它们之间做出选择。

例如：

这是最初的董事会安排：

           8 1 3
           4   2
           7 6 5

及其后代董事会安排：

I              

  8 1 3  
  4 6 2                
  7   5  

曼哈顿距离 + 移动次数 = 10

 II

  8   3   
  4 1 2   
  7 6 5 

曼哈顿距离 + 移动次数 = 12

III

  8 1 3
  4 2  
  7 6 5  

曼哈顿距离 + 移动次数 = 10

程序应该选择哪种板布置？我还是 III ？？？

Answer 1

您应该对每个数字求和曼哈顿距离（将 1 到位的曼哈顿距离加上 2 到位的曼哈顿距离......再加上 8 到位的曼哈顿距离）。如果您使用一些启发式算法（例如 A*），您将扩展第一块总和最低的板。如果两个板具有相同的总和值，那么您选择先扩展哪一个并不重要。您之前访问过的状态应该在某处保存为已关闭（这样您就不会进入循环周期）并且根本不考虑。