我在我的一本 AI 书籍中读到，在模拟或游戏中用于寻路的流行算法（A-Star、Dijkstra）也用于解决著名的“15 谜题”。
谁能给我一些关于如何将 15 谜题简化为节点和边图的指示，以便我可以应用其中一种算法？
如果我将图中的每个节点都视为游戏状态，那么那棵树不会变得很大吗？或者这只是这样做的方法吗？
Sean
问问题
33955 次
9 回答
9
对于 A-Star 的 15 谜题，一个很好的启发式方法是位于错误位置的方格数。因为每格错位至少需要 1 步，所以错位的格数保证小于或等于解决难题所需的步数，使其成为 A-Star 的适当启发式.
于 2009-04-12T18:20:49.250 回答
7
快速的 Google 搜索会找到几篇详细介绍这一点的论文：一篇关于Parallel Combinatorial Search，一篇关于External-Memory Graph Search
关于算法问题的一般经验法则：可能有人在你之前完成了它，并发表了他们的发现。
于 2008-09-22T20:13:58.373 回答
4
这是一个关于使用 A* 算法的 8-puzzle 问题的作业，但也相当简单：
http://www.cs.princeton.edu/courses/archive/spring09/cos226/assignments/8puzzle.html
于 2009-06-20T19:01:10.967 回答
4
解决这个问题的图论方法是将棋盘的每个配置想象成图的一个顶点，然后根据棋盘的曼哈顿距离之类的东西使用带有修剪的呼吸优先搜索来从起点推导出最短路径配置到解决方案。
这种方法的一个问题是，对于任何游戏空间变得如此之大以至于不清楚如何有效地标记访问过的顶点的n x n棋盘。n > 3换句话说，没有明显的方法来评估电路板的当前配置是否与之前通过遍历其他路径发现的配置相同。另一个问题是图的大小增长得如此之快n（大约(n^2)!是 ）以至于它不适合暴力攻击，因为路径的数量在计算上变得无法遍历。
Ian Parberry 的这篇论文A Real-Time Algorithm for the (n^2 − 1)- Puzzle描述了一个简单的贪心算法，它通过完成第一行、第一列、第二行来迭代地得出一个解决方案……它几乎立即得出一个解决方案，但解决方案远非最优；从本质上讲，它以人类的方式解决了问题，而无需利用任何计算能力。
这个问题与解决魔方问题密切相关。所有游戏的图表都表明它太大而无法通过暴力解决，但是有一个相当简单的 7 步方法可以让灵巧的人在大约 1 到 2 分钟内解决任何立方体。这条路径当然不是最优的。通过学习识别定义动作序列的模式，速度可以降低到17 秒。不过，吉里的这个壮举，却是有些超人！
Parberry 所描述的方法一次只移动一个图块；可以想象，通过利用 Jiri 的灵巧性并一次移动多个图块，可以使算法变得更好。正如 Parberry 证明的那样，这不会减少从 的路径长度n^3，但会减少前导项的系数。
于 2012-04-03T09:34:47.457 回答
3
请记住，A* 将搜索问题空间，沿着您的启发式定义的最可能的目标路径前进。
只有在最坏的情况下，它才会最终不得不淹没整个问题空间，当您的问题没有实际解决方案时，往往会发生这种情况。
于 2009-10-29T10:05:03.620 回答
2
只需使用游戏树。请记住，树是图的一种特殊形式。
在您的情况下，每个节点的叶子将成为您进行当前节点可用的移动之一后的游戏位置。
于 2008-09-18T18:08:26.050 回答
2
于 2009-06-20T18:37:31.610 回答
1
还。请注意，至少使用 A-Star 算法，您需要找出一个可接受的启发式算法，以确定可能的下一步是否比另一步更接近完成的路线。
于 2008-09-22T20:19:35.567 回答
0
根据我目前的经验，关于如何解决一个 8 谜题。创建节点是必需的。跟踪所采取的每一步，并从接下来的每一步中获取曼哈顿距离，走/走到距离最短的那一步。更新节点，并继续直到达到目标
于 2020-01-25T05:38:06.267 回答