计算机工程与应用
計算機工程與應用
계산궤공정여응용
COMPUTER ENGINEERING AND APPLICATIONS
2010年
15期
37-40,108
,共5页
搜索算法%Rotate-N-Puzzle%可解性%解上界%分治算法%贪心策略
搜索算法%Rotate-N-Puzzle%可解性%解上界%分治算法%貪心策略
수색산법%Rotate-N-Puzzle%가해성%해상계%분치산법%탐심책략
Rotate-N-Puzzle问题与N-Puzzle问题类似,问题空间也具有组合爆炸性质.经证明,Rotate-N-Puzzle的任何一个初始布局都是可解的.在此结论的基础上,给出了解长度的上界.提出了一种分治算法,在算法中的每一步,采用贪心策略求解问题.实验结果表明,该算法能够在多项式时间内快速求解规模很大的Rotate-N-Puzzle问题.
Rotate-N-Puzzle問題與N-Puzzle問題類似,問題空間也具有組閤爆炸性質.經證明,Rotate-N-Puzzle的任何一箇初始佈跼都是可解的.在此結論的基礎上,給齣瞭解長度的上界.提齣瞭一種分治算法,在算法中的每一步,採用貪心策略求解問題.實驗結果錶明,該算法能夠在多項式時間內快速求解規模很大的Rotate-N-Puzzle問題.
Rotate-N-Puzzle문제여N-Puzzle문제유사,문제공간야구유조합폭작성질.경증명,Rotate-N-Puzzle적임하일개초시포국도시가해적.재차결론적기출상,급출료해장도적상계.제출료일충분치산법,재산법중적매일보,채용탐심책략구해문제.실험결과표명,해산법능구재다항식시간내쾌속구해규모흔대적Rotate-N-Puzzle문제.
