一种求解N阶数码问题的通用算法  

A Universal Algorithm of Solving the N-Order Puzzle

作　　者：李健[1] 赵盼 

机构地区：[1]解放军外国语学院基础部,洛阳471003 [2]一拖(洛阳)集团中成机械公司,洛阳471003

出　　处：《现代计算机（中旬刊）》2014年第5期26-30,共5页Modern Computer

基　　金：解放军外国语学院科研基金项目(No.2013XYY003)

摘　　要：提出一种求解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）.

关 键 词：N阶数码问题 八数码问题 通用算法 多项式时间 

分 类 号：TP391.41[自动化与计算机技术—计算机应用技术]