我正在做一个3×3的立体盒拼图问题在我的功课.我会用C.
有26箱,起初,第一名是空的.通过滑动盒子,我必须按正确的顺序排列.红色数字显示正确的顺序,最后第27位必须为空.我不想让你给我代码;我在论坛上搜索,似乎我必须使用A* search algorithm,但是怎么样？
你能给我一些关于我如何使用A *算法这个问题的提示吗？我应该使用什么类型的数据结构？
解决方法
将您的问题定义为状态图：
G =(V,E)其中V = S = {(x_1,x_2,…,x_54)|所有可能的状态,3d板可以在其中} [每个数字在3d板上表示单个“正方形”].
并定义E = {(v1,v2)|可以用单一步骤从状态v1移动到状态v2}通过使用函数后继者(v),E的替代定义[相同]：
对于v中的每个v：后继者(v)= {所有可能的板,你可以得到,从v一步}
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 =我以前使用的术语].通过使用每个节点中的父字段,您可以从目标返回到源,找到您的路径.
