logo标签列表

如何使用A-Star或Dijkstra算法解决15数码难题？

artificial-intelligencegraph-theorydijkstraa-star
17

我在我的AI书籍中读到，用于模拟或游戏路径查找的流行算法（A-Star、Dijkstra）也被用来解决著名的“15拼图”问题。

请问有没有人能给我一些指导，如何将15拼图转化为节点和边缘的图形，以便我可以应用其中的一个算法？

如果我把图中的每个节点都当作一个游戏状态处理，那么这棵树会变得非常大吗？还是说这就是处理的方式？

10
这听起来像是计算机科学的作业！ - Rick Minerich
3
这是一个相当常见的计算机科学作业问题。 - monksy
9个回答
9

在15数码问题中，一个好的A-Star启发式方法是计算放错位置的方块数量。因为每个放错位置的方块至少需要移动1次，所以放错位置的方块数量保证小于或等于解决谜题所需的移动次数，使其成为A-Star的适当启发式方法。

4
我认为你提出的衡量标准不适合这个问题。直觉上，它会在棋盘上少数棋子位置错误的情况下非常脆弱。你可能最好使用从目标位置到每个棋子最终位置的距离之和作为衡量标准。 - wowest
7

快速的谷歌搜索可以找到一些详细介绍这个问题的论文：一个关于并行组合搜索，和一个关于外存图搜索。

在算法问题上的一个通用经验法则是：在你之前很可能已经有人做过了，并且发表了他们的发现。

1
你的链接有一半已经失效了。 - Jonny
4
4
使用图论的方法来解决这个问题，就是将棋盘的每个配置想象成图的一个顶点，然后使用基于类似于曼哈顿距离的剪枝的广度优先搜索，从起始配置到解决方案中得出最短路径。
这种方法的一个问题是，对于任何n x n的棋盘，其中n>3，游戏空间变得非常大，以至于不清楚如何有效地标记已访问的顶点。换句话说，没有明显的方法来评估当前棋盘配置是否与通过遍历其他路径发现的之前某个配置相同。另一个问题是，随着n的增长，图的大小增长得非常快（它大约是(n^2)!），所以它并不适合暴力攻击，因为路径数量变得计算上不可行。
这篇由Ian Parberry撰写的论文《一个实时算法解决(n^2-1)数码问题》描述了一种简单的贪心算法，通过先完成第一行、然后是第一列、第二行...来迭代地到达解决方案。它几乎可以立即得出解决方案，但解决方案远非最优；本质上，它解决问题的方式类似于人类，没有利用任何计算能力。
这个问题与解决魔方有关。所有游戏状态的图形太大，无法通过暴力破解来解决，但是有一种相当简单的7步方法，可以让灵巧的人在约1~2分钟内解决任何魔方。当然，这条路径是非最优的。通过学习识别定义移动序列的模式，速度可以降低到17秒。然而，Jiri的这项壮举有些超人了！
Parberry所描述的方法一次只移动一个方块；可以想象通过采用Jiri的灵巧性，同时移动多个方块来改进算法。正如Parberry所证明的那样，这不会减少路径长度n^3，但会减少主导项的系数。
3

请记住，A*算法会通过启发式搜索在问题空间中沿着最有可能达到目标的路径进行探索。

只有在最坏的情况下，它才会不得不对整个问题空间进行泛洪填充。这通常发生在您的问题实际上没有解决方案时。

2
1
谢谢，那是我的页面！这里有解决8数码问题的代码，它基于Ivan Bratko的Prolog编程处理方法。 - justinhj
2

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

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

1
请注意，在使用A-Star算法时，至少需要找出一种可接受的启发式方法来确定可能的下一步是否比另一个步骤更接近完成路线。
3
并不是真的。一个可行的启发式算法只需要保证它永远不会高估所需步骤的数量。如果你能够确定哪一个步骤更接近目标，那么你并不是在通常意义上进行搜索，而只是在按照步骤逐个迭代直到接近目标。 - John La Rooy
0
根据我的经验，解决8数码问题需要创建节点，跟踪每一步所采取的行动，并获取从每个后续步骤到达的曼哈顿距离，选择/前往具有最短距离的节点。更新节点并继续直到达到目标。
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接