关于人工智能：您如何使用A-Star或Dijkstra算法求解15难题？

How do you solve the 15-puzzle with A-Star or Dijkstra's Algorithm?

我已经读过一本AI书，其中流行的算法(A-Star，Dijkstra)用于模拟或游戏中的路径查找，也用于解决著名的" 15难题"。

谁能给我一些指导，说明如何将15谜题简化为节点和边的图形，以便我可以应用其中一种算法？

如果我将图中的每个节点都视为游戏状态，那么那棵树不会变得很大吗？还是只是这样做的方法？

对于具有15个谜题的A-Star，一个很好的启发法是在错误位置的正方形数。因为每平方英寸至少需要移动1步，所以保证偏移的正方形数小于或等于解决难题所需的移动数，这使其成为A-Star的适当启发法。

Google的快速搜索提出了几篇论文，这些论文对此进行了详细介绍：一篇涉及并行组合搜索，另一篇涉及外部存储器图搜索

关于算法问题的一般经验法则：某人可能在您之前完成了该工作，并发表了他们的发现。

图论解决问题的理论方法是将板的每个配置想象为图的顶点，然后基于板的" Manhatten距离"进行基于呼吸的优先搜索并进行修剪，以从起点算起最短路径解决方案的配置。

这种方法的一个问题是，对于任何n x n板，其中n > 3的游戏空间会变得很大，因此尚不清楚如何有效地标记访问的顶点。换句话说，没有明显的方法可以评估电路板的当前配置是否与先前通过遍历其他路径发现的配置相同。另一个问题是，随着n的增长，图形的大小增长得如此之快(大约为(n^2)!)，由于路径数量在计算上变得难以遍历，因此它不适合进行强力攻击。

Ian Parberry的这篇(n^2 ? 1)的实时算法-拼图描述了一种简单的贪心算法，该算法通过完成第一行，第一列，第二行然后迭代地得出解决方案。几乎立即解决方案，但是解决方案远非最佳方案；从本质上讲，它可以解决人类无法利用任何计算能力的问题。

这个问题与解决魔方的问题密切相关。所有游戏的图形都说明它太大了，无法用蛮力解决，但是有一种相当简单的7步方法，灵巧的人可以在大约1到2分钟内使用它解决任何立方体。该路径当然是非最佳的。通过学习识别定义移动顺序的模式，速度可以降低到17秒。但是，Jiri的这一壮举有点超人！

Parberry描述的方法一次只能移动一个图块；有人认为，通过利用Jiri的灵活性并一次移动多个图块，可以使算法更好。正如Parberry所证明的那样，这不会减小n^3的路径长度，但是会减小前导项的系数。

这是对使用A *算法进行详细讨论的8难题的一项作业，但也相当简单：

http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html

请记住，A *会在问题空间中进行搜索，并按照启发式方法定义的最可能的目标路径进行搜索。

只有在最坏的情况下，它才最终不得不淹没整个问题空间，而在没有实际解决问题的方法时，往往会发生这种情况。

在这里，您可以访问http://www.heyes-jones.com/astar.html

只需使用游戏树。请记住，树是图形的一种特殊形式。

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

也。请注意，至少使用A-Star算法时，您将需要找出一种可允许的试探法，以确定可能的下一步骤是否比另一步骤更接近完成的路线。

bryanTyler的出色信息！