你如何用A-Star或Dijkstra算法解决15-puzzle？

Question

我在我的一本AI书中读过,用于模拟或游戏中寻路的流行算法(A-Star,Dijkstra)也用于解决众所周知的"15-puzzle".

任何人都可以给我一些关于如何将15-puzzle减少到节点和边缘图的指针,以便我可以应用其中一种算法？

如果我将图中的每个节点视为游戏状态,那么该树不会变得非常大吗？或者只是这样做的方式？

Answer 1

使用15拼图的A-Star的良好启发式是位于错误位置的正方形的数量.因为每个方格至少需要移动一次,所以不合适的方格数保证小于或等于解决谜题所需的移动次数,使其成为A-Star的合适启发式方法.

Answer 2

一个快速的谷歌搜索出现了一些文章,详细介绍了这一点:一个是关于并行组合搜索,另一个是关于外部存储器图搜索

关于算法问题的一般经验法则:有人可能在你之前做过,并发表了他们的发现.

Answer 3

只需使用博弈树即可。请记住，树是图的一种特殊形式。

在您的情况下，在您进行当前节点可用的移动之一后，每个节点的叶子将成为游戏位置。