如何使用 A-Star 或 Dijkstra 算法解决 15 个难题？
我在一本人工智能书籍中读到，用于模拟或游戏中寻路的流行算法（A-Star、Dijkstra）也被用来解决著名的“15 谜题”。
谁能给我一些关于如何将 15 个谜题简化为节点和边图的指示，以便我可以应用其中一种算法？
如果我将图中的每个节点视为游戏状态，那么该树不会变得很大吗？ 或者这只是做到这一点的方法？
I've read in one of my AI books that popular algorithms (A-Star, Dijkstra) for path-finding in simulation or games is also used to solve the well-known "15-puzzle".
Can anyone give me some pointers on how I would reduce the 15-puzzle to a graph of nodes and edges so that I could apply one of these algorithms?
If I were to treat each node in the graph as a game state then wouldn't that tree become quite large? Or is that just the way to do it?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
就我目前的经验而言，如何解决 8 个难题。
需要创建节点。 跟踪所采取的每一步
并从接下来的每个步骤中获取曼哈顿距离，采取/前往距离最短的步骤。
更新节点，并继续直到达到目标
For my current experience, on how to solve an 8 puzzle.
it is required to create nodes. keep track of each step taken
and get the manhattan distance from each following steps, taking/going to the one with the shortest distance.
update the nodes, and continue until reaches the goal
还。 请注意，使用 A-Star 算法，至少您需要找出一个可接受的启发式方法来确定可能的下一步是否比另一步更接近完成的路线。
Also. be mindful that with the A-Star algorithm, at least, you will need to figure out a admissible heuristic to determine whether a possible next step is closer to the finished route than another step.
在这里http://www.heyes-jones.com/astar.html
Here you go http://www.heyes-jones.com/astar.html
只需使用博弈树即可。 请记住，树是图的一种特殊形式。
在您的情况下，在您进行当前节点可用的移动之一后，每个节点的叶子将成为游戏位置。
Just use the game tree. Remember that a tree is a special form of graph.
In your case the leaves of each node will be the game position after you make one of the moves that is available at the current node.
请记住，A* 将沿着您的启发式定义的最有可能的目标路径搜索问题空间。
只有在最坏的情况下，它才会最终不得不淹没整个问题空间，当问题没有实际解决方案时，这种情况往往会发生。
Remember that A* will search through the problem space proceeding down the most likely path to goal as defined by your heurestic.
Only in the worst case will it end up having to flood fill the entire problem space, this tends to happen when there is no actual solution to your problem.
解决该问题的图论方法是将棋盘的每个配置想象为图的一个顶点，然后使用基于棋盘的曼哈顿距离之类的剪枝的呼吸优先搜索来导出从起始点开始的最短路径配置到解决方案。
这种方法的一个问题是，对于任何
nx n板，其中n > 3游戏空间变得如此之大，以至于不清楚如何有效地标记访问过的顶点。 换句话说，没有明显的方法来评估电路板的当前配置是否与之前通过其他路径发现的配置相同。 另一个问题是，随着n（大约为(n^2)!），图大小增长得如此之快，以至于它不适合暴力攻击，因为路径的数量在计算上变得无法遍历。Ian Parberry 的这篇论文
(n^2 − 1) 的实时算法)- Puzzle 描述了一种简单的贪婪算法，该算法通过完成第一行、然后第一列、然后第二行迭代地得出解决方案...它几乎立即得出解决方案，但是解决方案远非最优； 本质上，它以人类的方式解决问题，无需利用任何计算能力。这个问题与解魔方的问题密切相关。 所有游戏的图表都表明它太大，无法用蛮力解决，但是有一个相当简单的 7 步方法，可以由灵巧的人在大约 1 到 2 分钟内解决任何立方体。 这条路径当然不是最优的。 通过学习识别定义移动顺序的模式，速度可以降低到 17 秒 。 然而，吉里的这一壮举，却有些超人了！
Parberry 描述的方法一次只能移动一个方块； 人们想象，通过利用 Jiri 的灵巧性并同时移动多个图块，可以使算法变得更好。 正如 Parberry 所证明的那样，这不会减少
n^3的路径长度，但会减少首项的系数。The graph theoretic way to solve the problem is to imagine every configuration of the board as a vertex of the graph and then use a breath-first search with pruning based on something like the Manhatten Distance of the board to derive a shortest path from the starting configuration to the solution.
One problem with this approach is that for any
n x nboard wheren > 3the game space becomes so large that it is not clear how you can efficiently mark the visited vertices. In other words there is no obvious way to assess if the current configuration of the board is identical to one that has previously been discovered through traversing some other path. Another problem is that the graph size grows so quickly withn(it's approximately(n^2)!) that it is just not suitable for a brue-force attack as the number of paths becomes computationally infeasible to traverse.This paper by Ian Parberry A Real-Time Algorithm for the
(n^2 − 1)- Puzzle describes a simple greedy algorithm that iteritively arrives at a solution by completing the first row, then the first column, then the second row... It arrives at a solution almost immediately, however the solution is far from optimal; essentially it solves the problem the way a human would without leveraging any computational muscle.This problem is closely related to that of solving the Rubik's cube. The graph of all game states it too large to solve by brue force, but there is a fairly simple 7 step method that can be used to solve any cube in about 1 ~ 2 minutes by a dextrous human. This path is of course non-optimal. By learning to recognise patterns that define sequences of moves the speed can be brought down to 17 seconds. However, this feat by Jiri is somewhat superhuman!
The method Parberry describes moves only one tile at a time; one imagines that the algorithm could be made better up by employing Jiri's dexterity and moving multiple tiles at one time. This would not, as Parberry proves, reduce the path length from
n^3, but it would reduce the coefficient of the leading term.这是针对 8 谜题的作业，详细讨论了使用 A* 算法，但也相当简单：
http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html
This is an assignment for the 8-puzzle problem talked about using the A* algorithm in some detail, but also fairly straightforward:
http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html
快速谷歌搜索发现了几篇论文，其中详细介绍了这一点：一篇关于 并行组合搜索，以及 外部内存图搜索
涉及算法问题时的一般经验法则：有人可能在您之前完成了这件事，并发表了他们的发现< /em>.
A quick Google search turns up a couple papers that cover this in some detail: one on Parallel Combinatorial Search, and one on External-Memory Graph Search
General rule of thumb when it comes to algorithmic problems: someone has likely done it before you, and published their findings.
对于 15 个拼图的 A-Star 来说，一个很好的启发方法是位于错误位置的方格数量。 因为每个错位的方格至少需要 1 次移动，所以错位的方格数量保证小于或等于解决谜题所需的移动次数，这使其成为 A-Star 的合适启发式方法。
A good heuristic for A-Star with the 15 puzzle is the number of squares that are in the wrong location. Because you need at least 1 move per square that is out of place, the number of squares out of place is guaranteed to be less than or equal to the number of moves required to solve the puzzle, making it an appropriate heuristic for A-Star.