| Rotate-N-Puzzle问题可解性分析及求解 |
| |
| 引用本文： | 陈云川,徐峥,罗克露. Rotate-N-Puzzle问题可解性分析及求解[J]. 计算机工程与应用, 2010, 46(15): 37-40. DOI: 10.3778/j.issn.1002-8331.2010.15.012 |
| |
| 作者姓名： | 陈云川 徐峥 罗克露 |
| |
| 作者单位： | 电子科技大学计算机科学与工程学院,成都,610054 |
| |
| 摘 要： | Rotate-N-Puzzle问题与N-Puzzle问题类似，问题空间也具有组合爆炸性质。经证明，Rotate-N-Puzzle的任何一个初始布局都是可解的。在此结论的基础上，给出了解长度的上界。提出了一种分治算法，在算法中的每一步，采用贪心策略求解问题。实验结果表明，该算法能够在多项式时间内快速求解规模很大的Rotate-N-Puzzle问题。
|
| 关 键 词： | 搜索算法 Rotate-N-Puzzle 可解性 解上界 分治算法 贪心策略 |
| 收稿时间： | 2008-11-21 |
| 修稿时间： | 2009-2-23 |
Rotate-N-Puzzle: Solvable analysis and solving approach |
| |
| CHEN Yun-chuan,XU Zheng,LUO Ke-lu. Rotate-N-Puzzle: Solvable analysis and solving approach[J]. Computer Engineering and Applications, 2010, 46(15): 37-40. DOI: 10.3778/j.issn.1002-8331.2010.15.012 |
| |
| Authors: | CHEN Yun-chuan XU Zheng LUO Ke-lu |
| |
| Affiliation: | Department of Computer Science ＆ Engineering,University of Electronic Science ＆ Technology of China,Chengdu 610054,China |
| |
| Abstract: | 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. |
| |
| Keywords: | search algorithm Rotate-N-Puzzle solvable upper bound divide-and-conquer algorithm greedy strategy |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《计算机工程与应用》浏览原始摘要信息 |
|
点击此处可从《计算机工程与应用》下载全文 |
