c++ - 解决 8 谜题游戏

Question

我正在尝试用 C++ 编写一个 8 拼图游戏求解器，但在执行此操作时遇到了很多问题。该程序目前正在运行，但要解决这个难题需要太多步骤。我的意思是，有时它可以找到最佳解决方案，有时它需要多达 400 步才能解决。我的主要疑问如下。想象一下我有这个图表（这只是一个草稿）：

我使用曼哈顿距离作为启发式函数。在第一步之后，我们有两个状态，其中 f(n)=5，所以我扩展了树。展开后，我仍然得到两个 f(n)=2 的状态。这是我的疑问..我是否还需要扩展树直到我得到一个唯一的最低 f(n)？

提前致谢！

Answer 1

我还需要扩展树吗

你不能贪婪地解决这个难题：总是选择具有较低启发值的分支不会每次都引导你找到最终的解决方案。因此，您必须保留其他状态以进行回溯。扩展它们的顺序，无论是简单的 BFS 还是基于启发式的 A*，都取决于您。

Answer 2

在这里您可以找到使用 A* 算法找到从初始状态到目标状态的最短路径的处理小程序。小程序中的代码是免费的。