摘要
提出一种求解N阶数码问题的通用算法,可以在多项式时间内求出一个有确定上限的解。该算法将整个棋盘分为4个区域,对于归属不同区域的数码分别采用"单码归位"和"双码归位"子算法,最终使所有数码归位。分析和测试表明:该算法的时间复杂度为O(n6),而所得解决方案移动步数的上限为O(n3)。
Proposes a universal algorithm for solving the N-order Puzzle, which can find a solution with exactly upper bound in polynomial time. The board is divided into 4 regions; uses ＂single tile homing＂ and ＂double tiles homing＂ sub-algorithms for different regions＂ tiles respectively, eventually all tiles complete homing. Algorithm analysis and tests show that the time complexity of the algorithm is O （n^6）, while the upper bound of steps to move of the final solution is O（n^3）.
基金
解放军外国语学院科研基金项目(No.2013XYY003)
