寻找良好的启发式方法来搜索

Question

我正在尝试找到一个名为Twiddle的小益智游戏的最佳解决方案（可以找到带有游戏的小程序 这里）。该游戏具有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。

Answer 2

计算距离时，应考虑所有元素，而不仅仅是角元素。想象一下，所有角元素1、3、7、9都在他们的家中，但所有其他元素都不是。

可以说，那些作为最终状态中邻居的元素在每个步骤中都应该越来越近，因此邻居的距离也可能是启发式的一部分，但可能比其最终状态的元素的距离弱的影响力较弱。

Answer 3

您可以通过考虑所有数字，然后将4分开并舍入下一个整数，从您的方法中获得可接受的（即，不高估）启发式。

为了改善启发式，您可以查看成对的数字。如果在左上方的数字1和2换了数字，则至少需要3个旋转来修复它们，这两个旋转都比单独考虑它们要比1+1更好。最后，您仍然需要除以4。