为A*搜索找到良好的启发式方法

Question

我正试图找到一个叫做Twiddle的小益智游戏的最佳解决方案(这个游戏的applet可以在这里找到).游戏有一个3x3矩阵,数字从1到9.目标是使用最少的移动量使数字按正确的顺序排列.在每次移动中,您可以顺时针或逆时针旋转2x2方格.

即如果你有这种状态

6 3 9
8 7 5
1 2 4

然后顺时针旋转左上方的2x2方形

8 6 9
7 3 5
1 2 4

我正在使用A*搜索找到最佳解决方案.我的f()只是所需的旋转次数.我的启发式功能已经导致最佳解决方案(如果我修改它,请参见最后的通知),但我不认为这是你能找到的最好的解决方案.我当前的启发式获取每个角落,查看角落处的数字并计算到该数字在解决状态下将具有的位置的曼哈顿距离(这给出了将数字带到此位置所需的旋转次数)并将所有数量相加这些价值观.即你采取上面的例子:

6 3 9
8 7 5
1 2 4

这个结束状态

1 2 3
4 5 6
7 8 9 

然后启发式做了以下事情

6 is currently at index 0 and should by at index 5: 3 rotations needed
9 is currently at index 2 and should by at index 8: 2 rotations needed
1 is currently at index 6 and should by at index 0: 2 rotations needed
4 is currently at index 8 and should by at index 3: 3 rotations needed

h = 3 + 2 + 2 + 3 = 10

另外,如果h为0,但状态未完全排序,则h = 1.

但是有一个问题,就是你一次旋转4个元素.因此,在极少数情况下,您可以在一次移动中做两次(更多)这些估计的旋转.这意味着这些启发式过高估计了与解决方案的距离.

我目前的解决方法是,简单地排除计算中的一个角落,至少在我的测试用例中解决了这个问题.如果我真的解决了这个问题,或者这个启发式算法在某些边缘案例中仍然过高估计,那么我就没有做过任何研究.

所以我的问题是:你能想出什么是最好的启发式方法？

(免责声明:这是一个大学项目,所以这是一个功课.但如果可以提出,我可以自由使用任何资源,所以可以问你们.我也会相信Stackoverflow帮助我; ))

Answer 1

简单往往是最有效的。将九个数字（按行优先的顺序）视为形成一个整数。解决方案由尽可能小的整数 i(g) = 123456789 表示。因此，我建议采用以下启发式 h(s) = i(s) - i(g)。对于您的示例，h(s) = 639875124 - 123456789。