21

我正在尝试为一个名为 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 对我的帮助； ) )

4

3 回答 3

3

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

于 2011-01-01T21:27:55.233 回答
1

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

为了改进启发式，您可以查看成对的数字。例如，如果在左上角交换了数字 1 和 2，则至少需要 3 次旋转才能将它们都固定好，这比单独考虑它们的 1+1 更好。最后还是需要除以4。你可以任意配对数字，甚至尝试所有配对，找到最好的除法。

于 2011-01-04T18:03:00.927 回答
0

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

可以说，那些在最终状态下是邻居的元素应该在每一步中趋向于变得更近，因此相邻距离也可以是启发式的一部分，但可能比元素到最终状态的距离影响更弱。

于 2010-12-31T14:10:56.563 回答