Rotate-N-Puzzle问题可解性分析及求解  

Rotate-N-Puzzle:Solvable analysis and solving approach

作　　者：陈云川[1] 徐峥[1] 罗克露[1] 

机构地区：[1]电子科技大学计算机科学与工程学院,成都610054

出　　处：《计算机工程与应用》2010年第15期37-40,108,共5页Computer Engineering and Applications

摘　　要：Rotate-N-Puzzle问题与N-Puzzle问题类似,问题空间也具有组合爆炸性质。经证明,Rotate-N-Puzzle的任何一个初始布局都是可解的。在此结论的基础上,给出了解长度的上界。提出了一种分治算法,在算法中的每一步,采用贪心策略求解问题。实验结果表明,该算法能够在多项式时间内快速求解规模很大的Rotate-N-Puzzle问题。Rotate-N-Puzzle is a similar problem like N-Puzzle.The problem space of Rotate-N-Puzzle is also asymptotically exponential.It’s proved that any initial configuration of Rotate-N-Puzzle is solvable.This proof also gives out the upper bound of the solution length.A divide-and-conquer algorithm is implemented,which solves the problem greedily in each step.As the experiment result states,this algorithm can solve rather large scale Rotate-N-Puzzle problems in polynomial running time.

关 键 词：搜索算法 Rotate-N-Puzzle 可解性 解上界 分治算法 贪心策略 

分 类 号：TP301.4[自动化与计算机技术—计算机系统结构]