logo标签列表

寻找适用于A*搜索的良好启发式算法。

algorithmsearchgraph-algorithma-star
21
我正在尝试找到一个叫做Twiddle的小益智游戏的最佳解决方案（可以在这里找到该游戏的applet：here）。该游戏有一个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
您的启发式算法对距离的高估意味着在某些情况下可能不会导致最优解。 - CodesInChaos
1
你最好祈祷我们不会告诉Simon你在作弊。 :) - bzlm
@CodeInChaos：正如我所写的：我知道。正因为如此，我正在寻找一个更好的解决方案。 - Martin Thurau
当你谈到启发式问题时，你也写道：“我的启发式函数已经导致了最优解”。所以我不确定你是否知道高估的启发式会导致非最优解。 - CodesInChaos
你是对的。如果编辑问题以使其更清晰。 - Martin Thurau
@Martin。另请参阅：https://dev59.com/OnI95IYBdhLWcg3w3yNU - Dave Jarvis
3个回答
3

简单往往最有效。考虑按行顺序排列的九个数字，将它们视为一个整数。解决方案由最小可能的整数i(g) = 123456789表示。因此，我建议采用以下启发式方法h(s) = i(s) - i(g)。对于您的示例，h(s) = 639875124 - 123456789。

请纠正我，但这不是A*算法可用的启发式方法，因为h()需要（低估）到目标的距离。如果不使用所需的旋转作为距离测量，那么我应该使用什么？ - Martin Thurau
你说得很对。我的建议只是一个提示，也是其他情况下有用的技巧。然而，设计一个满足A*启发式要求的实值函数并不难。例如，h(n) = (i(n)-i(g))/i(s)，其中n是当前状态，g是目标状态，s是初始状态，i是如上所述定义的状态值。h(g) = 0.0。但是，你需要测试一下。告诉我们它是否找到了最优解。 - Liberius
好的，我已经测试过了。有时候会高估，因为并非每次都能找到最优解。此外，这会产生大约为1的h()值。有时值会更高，但不足以对搜索进行有效的优化。尽管如此，它还是一个聪明而坚韧的。 - Martin Thurau
好的，谢谢。如果您只想要保证最优解，对于像这样的小问题，最简单的方法是将h(n)设置为0，这总是保证低估。实际上，这将给您广度优先搜索，只要有足够的空间来存储前沿集合，就可以始终找到最优解。 - Liberius
这是不正确的。这个启发式算法不可行，并且缩小它使其可行也变得无用。将h(x)设置为0是可行的，但这样就不再是A*算法了，而是DIjkstra算法（在这种情况下等同于BFS）。 - ADdV
1

您可以通过考虑所有数字，将它们除以4并向上取整，得到一个可接受的（即不会高估）启发式方法。

为了改进启发式方法，您可以查看数字对。例如，在左上角交换数字1和2，您需要至少3次旋转才能将它们都修复好，这比单独考虑它们时的1+1更好。最后，您仍然需要除以4。您可以任意配对数字，甚至尝试所有数字对，并找到最佳的数字对分组。

0
在计算距离时，应考虑所有元素，而不仅仅是角落元素。想象一下，所有角落元素1、3、7、9都在它们的家中，但其他所有元素都不在。
可以认为，在最终状态下相邻的元素应该在每一步中趋向于更接近，因此相邻距离也可以成为启发式的一部分，但可能比元素到最终状态的距离影响要弱。
你说得对。我忘了提到如果所有角落元素都在它们的位置上，但总状态没有排序，那么h为1。 - Martin Thurau
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接