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

• 作者: 徐峥 罗克露 陈云川
• 来源期刊: 计算机工程与应用
• 学科: 工学
• 关键词: 搜索算法 Rotate-N-Puzzle 可解性 解上界 分治算法 贪心策略
• 年，卷（期）: 2010,（15）
• 所属期刊栏目: 研究、探讨
• 页码范围: 37-40,108
• 分类号: TP301.4
• 字数: 6903字
• 语种: 中文
• DOI: 10.3778/j.issn.1002-8331.2010.15.012

摘要

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

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	罗克露	电子科技大学计算机科学与工程学院	51	297	9.0	14.0
2	陈云川	电子科技大学计算机科学与工程学院	2	5	1.0	2.0
3	徐峥	电子科技大学计算机科学与工程学院	1	0	0.0	0.0