如果算法的效率很重要,那么您可能需要一个明智的算法 - 例如 A*算法,预计它具有相当快的速度(相对于备选方案),具有良好的可允许启发式功能.
较慢但较简单的解决方案可以运行BFS.
两种算法(A*,BFS)都是完整的(总是找到解决方案,如果存在)和最优(找到最短路径).
另请注意,您可以使用宏来学习"好"的一系列动作,以更快地获得算法.忽略此改进,直到您实现一个有效(但速度慢)的解决方案.
编辑:编码指南:
以图表的形式查看问题:图表将在G=(V,E)何处V = { all possible states}和E = { (u,v) | can move from state u to state v within a single step }
现在,使用此图表 - 您有一个起始位置(源,作为输入)和目标(一个排序的拼图).启动BFS或A*(在附带的维基百科链接中查看这些伪代码),以查找从源到目标的路径.你应该从BFS开始 - 它更简单.
最短路径算法返回的路径与您从起始板到目标所需的一系列动作相同.
注意:您无需创建实际图表!你只需要一个来保存起始节点(源) - 并创建它的顶点,并有一个successors:V->2^V函数,它为你提供每个顶点的后继(正式:) successors(v) = { (v,u) | (v,u) is in E }.这样,您可以动态构建图形的相关部分.
- @NiklasB.:由于有36个/ 2个可能的状态,并且解决方案可能需要数百次移动,我怀疑Dijkstra或BFS会足够快. (3认同)