algorithm - 6*6拼图算法

Question

我有一个 6*6 的拼图，其中 35 个数字(1~35)随机排列。使用空白作为“寄存器”并将数字一个一个地移动以使它们有序。我可以处理一个 3*3 的拼图，但是如何处理一个 6*6 的呢？你能给我一些提示吗？

Answer 1

思路是一样的，将问题表示为状态graph , 然后运行 ​​shortest path 算法。

如果算法的效率很重要，您可能需要一个明智的算法 - 例如 A* algorithm ，这预计会非常快(相对于替代方案)并且具有良好的 admissible heuristic function .
一个较慢但更简单的解决方案可以运行 BFS .

两种算法(A*、BFS)都是完整(如果存在，总能找到解决方案)和最优(找到最短路径)。

另请注意，您可以使用宏来学习“好的”系列 Action ，以更快地获得算法。在您实现有效(虽然缓慢)的解决方案之前，请忽略此改进。

---

编辑:编码指南:
将问题视为图表:图表将是 G=(V,E) 其中 V = { 所有可能的状态} 和 E = { (u, v) |可以在一步内从状态 u 移动到状态 v }

现在，有了这张图 - 你有一个起始位置(源，作为输入给出)和一个目标(一个排序的拼图)。启动 BFS 或 A*(查看随附的维基百科链接中的伪代码)，以找到从源到目标的路径。你应该从 BFS 开始——它更简单。
最短路径算法返回的路径与从起始板到目标必须执行的一系列移动相同。

注意:您不需要创建实际图表!您只需要 a 来保存起始节点(源)- 并创建它的顶点，并有一个 successors:V->2^V 函数，它为您提供每个顶点的后继(形式上:successors(v) = { (v,u) | (v,u) 在 E 中 })。这样，您就可以动态构建图表的相关部分。