解决8数码问题

Question

我正在尝试使用C++编写8数码游戏求解器，但在此过程中遇到了很多问题。虽然程序目前可以工作，但解决拼图需要的步骤太多了。有时它可以找到最优解，有时需要400步以上才能解决。我的主要疑问是...假设我有这个图（这只是一个草稿）：

（图片略）

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

提前感谢！

- pluralism

---

你确定你正在使用正确的方法来解决这个游戏吗？就我所记得的，这个游戏在最后几步之前可以相当轻松地解决。因此，总的来说 - 有一个直接的算法，没有必要使用树和启发式算法。 - Andrey

@Andrey：通常人们使用A算法+启发式函数来解决这个难题。我正在尝试用自己的方式解决它，不使用算法，只使用启发式函数。也许你是在提到A/IDA*算法？ - pluralism

我认为树不是解决这个谜题的好算法，因为我找到了一个在线版本并亲手解决了它。 - DiegoNolan

不要把问题空间看作一棵树，而是将其视为一个有向图，其节点是“游戏状态”，边缘是从一个游戏状态到另一个游戏状态所需的“移动”。8拼图只有362,880种可能的游戏状态，因此可以在图上进行暴力广度优先搜索，每次都获得最佳解决方案。(不过不要尝试对15拼图使用暴力搜索，因为它有1万亿个状态)。 - Kevin

@pluralism 当你说曼哈顿距离时，你是指无穷范数吗？所有8个棋子的距离之和。如果曼哈顿距离为零时最优，我不明白为什么需要检查唯一最小值，你知道最小值应该是什么。 - DiegoNolan

Answer 1

我还需要扩展树吗？

无法贪心地解决这个难题：始终选择启发式值较低的分支不会每次都带领你找到最终解决方案。因此，你必须保留其他状态进行回溯。你选择按照何种顺序扩展它们，无论是简单的BFS还是基于启发式的A*，由你自己决定。

- MvG

---

谢谢你指出来！我的方法确实可行，但是步骤太多了。你可以在这个链接http://oi47.tinypic.com/2uh3jty.jpg中看到有时需要200多个步骤，而在最后一个步骤中只需要26个步骤，可能是最优解。 - pluralism

@pluralism：两种解决方案都不是最优的。请参考使用A*算法的此实现进行比较。只需要27步而不是259步，只需要16步而不是26步。 - MvG

请注意，我在之前的评论中提到的实现并不完全正确：在A*中遇到已经看过的状态时，可能会发生减少操作。这在BFS中不是问题。但是，更正确的实现表明，我引用的数字仍然是正确的。 - MvG

是的，你说得对，我的方法很糟糕，但我只是想自己做点什么，不使用任何现有的算法 :) 可能我得转向A*算法。 - pluralism

@pluralism：解决同一问题的根本算法并不多。虽然有些微小差别，但基本上所有用于此类问题的最短路径算法都可归结为 BFS、A* 或 Dijkstra，后两者在这种情况下几乎是等效的，因为启发式函数是单调的。想要创造出完全新的可行算法将是困难的。更有可能的是，通过使用一些新术语，重新发明其中一个算法。 - MvG

Answer 2

这里你可以找到一个使用A*算法寻找从初始状态到目标状态最短路径的处理程序。该处理程序的代码可免费获取。

- rasco