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

将您的问题定义为状态图：
G =(V,E)其中V = S = {(x_1,x_2,…,x_54)|所有可能的状态,3d板可以在其中} [每个数字在3d板上表示单个“正方形”].
并定义E = {(v1,v2)|可以用单一步骤从状态v1移动到状态v2}通过使用函数后继者(v),E的替代定义[相同]：
对于v中的每个v：后继者(v)= {所有可能的板,你可以得到,从v一步}

您还需要一个admissible heuristic function,这个问题可以是一个很好的例子：h(state)= Sigma(manhattan_distance(x_i))其中我在范围[1,54])基本上是每个数字的manhattan distances的总和从其目标.

现在,一旦我们得到这些数据,我们就可以用定义的启发式方法在定义的图G上运行A *.由于我们的启发式功能是可以接受的[说服自己为什么！],由于admissibility and optimality of A*,A *发现的解决方案将是最佳的.查找实际路径：A *将在开发目标状态时结束. [x_i =我以前使用的术语].通过使用每个节点中的父字段,您可以从目标返回到源,找到您的路径.