使用A *搜索算法来解决3x3三维盒子拼图？

Question

我正在做家庭作业中的3x3三维盒子拼图问题。我将与C.

代码

有26个箱，并在第一，第一个地方是空的。通过滑动盒子，我必须按正确的顺序排列它们。红色数字显示正确顺序，第27位最后必须为空。我不希望你给我代码;我在论坛搜索，似乎我必须使用A* search algorithm，但如何？

你能告诉我关于如何在这个问题上使用A *算法的提示吗？我应该使用什么类型的数据结构？

Answer 1

你知道图表是如何工作的，以及A *如何在它们上找到最短路径，对吧？

其基本思想是，拼图的每个配置都可以被认为是图形中的顶点，并且边表示移动（通过连接移动之前和之后的配置）。

找到一组从原始配置到所需配置的移动可以看作是一个路径发现问题。

Answer 2

定义您的问题作为一个状态-图表：
G=(V,E)其中V=S={(x_1,x_2,...,x_54) | all possible states the 3d board can be in} [各号码表示在3D板的单个“正方形”]。
并定义E={(v1,v2)| it is possible to move from state v1 to state v2 with a single step}备选定义[相同]为E是通过使用函数successors(v)：
对于V各自ν：successors(v)={all possible boards you can get, with 1 step from v}

你还需要一个admissible heuristic function，一个非常好的针对此问题可以是：基本上，它是来自其目标的每个数字的总和manhattan distances。

现在，一旦我们获得了这些数据，我们就可以在定义的启发式图G上开始运行A *。由于我们的启发式功能是可以接受的[说服自己为什么！]，由于admissibility and optimality of A*的原因，保证A *找到的解决方案是最优的。
查找实际路径：当您开发目标状态时，A *将结束。 [x_i=i用我们之前使用的术语]。通过使用每个节点中的parent字段，您将通过从目标回溯到源代码找到指向它的路径。