2

首先，我已经阅读了可以在 stackoverflow 或其他互联网搜索中找到的所有线程。我确实了解了不同的方面，但这并不是我所需要的。

我需要解决大小不超过 8 X 8 块的高峰时间拼图。

正如我在标题中所说，我想使用 A*，作为我将要使用的启发式方法：阻挡红色汽车（需要取出的那辆）路径的汽车数量应该减少或保持不变。

我已阅读高峰时段的 BFS 解决方案。

我不知道如何开始或更好地说，要遵循哪些步骤。

如果有人需要任何解释，这里是任务的链接：

http://www.cs.princeton.edu/courses/archive/fall04/cos402/assignments/rushhour/index.html

到目前为止，从我读到的内容（尤其是从 polygenelubricants 的回答中）我需要生成一个阶段图，包括初始阶段和“成功”阶段，并使用 A* 算法确定从初始到最终的最小路径？

我应该创建一个回溯函数来生成所有可能的（有效）移动吗？

正如我之前所说，我需要帮助来概述我需要采取的步骤，而不是在实施方面遇到问题。

编辑：我是否需要生成所有可能的移动，以便将它们转换为图形节点，这不是很耗时吗？我需要在 10 秒内解决一个 8X8 难题

4

1 回答 1

2

A* 是一种用于搜索图的算法。图由节点和边组成。因此，我们需要将您的问题表示为图表。

我们可以将拼图的每个可能状态称为一个节点。两个节点之间有一条边，如果它们可以通过一次移动彼此到达。

现在我们需要一个开始节点和一个结束节点。 哪些拼图状态将代表我们的开始节点和结束节点？

最后，A* 还需要一件事：一个可接受的距离启发式- 猜测拼图需要多少步才能完成。这个猜测的唯一限制是它必须小于实际的移动次数，所以实际上我们正在寻找的是一个最小界限。将启发式设置为 0 将满足这一点，但如果我们能提出更好的最小界限，算法将运行得更快。 你能想出一个谜题完成移动次数的最低限度吗？

于 2012-08-21T19:56:52.697 回答