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

Question

我正在做作业中的3x3三维盒子拼图问题.我将用C编码.

有26个盒子,起初,第一个地方是空的.通过滑动盒子,我必须按正确的顺序排列它们.红色数字显示正确的顺序,第27个位置最后必须为空.我不想让你给我代码; 我在论坛中搜索,似乎我必须使用A*搜索算法,但是如何？

你能给我一些关于如何在这个问题上使用A*算法的技巧吗？我应该使用什么类型的数据结构？

Answer 1

将问题定义为状态图:
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}一个替代定义[相同] : 对于V中的每个v:Esuccessors(v)
successors(v)={all possible boards you can get, with 1 step from v}

你还需要一个可接受的启发函数,这个问题的一个很好的问题可能是:h(state)=Sigma(manhattan_distance(x_i)) where i in range [1,54])基本上,它是每个数字与目标的曼哈顿距离的总和.

现在,一旦我们得到这些数据,我们就可以开始在定义的图G上运行A*,并使用定义的启发式算法.而且由于我们的启发式功能是可以接受的[说服自己为什么!],由于A*的可接受性和最优性,保证解决方案A*发现将是最佳的.
查找实际路径:当您开发目标状态时,A*将结束.[ x_i=i按照我们之前使用的术语].您可以使用parent每个节点中的字段,从目标返回到源,找到它的路径.

Answer 2

您知道图的工作原理以及 A* 如何在图上找到最短路径，对吧？

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

找到从原始配置到所需配置的一组移动可以被视为路径查找问题。