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

摘要：

Rotate-N-Puzzle问题与N-Puzzle问题类似,问题空间也具有组合爆炸性质.经证明,Rotate-N-Puzzle的任何一个初始布局都是可解的.在此结论的基础上,给出了解长度的上界.提出了一种分治算法,在算法中的每一步,采用贪心策略求解问题.实验结果表明,该算法能够在多项式时间内快速求解规模很大的Rotate-N-Puzzle问题.

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

所属期刊栏目：46

分类号：TP301.4(计算技术、计算机技术)

在线出版日期：2010-08-12（万方平台首次上网日期，不代表论文的发表时间）

页数：共5页

页码：37-40,108