摘要
本文对骑士巡游问题进行了研究 ,提出了求棋盘马步图的 Hamilton圈的“分治 -回溯 -合并”算法 ,其时间复杂度是 O(n2 )。分析表明该算法是求棋盘马步图一条 Hamilton圈的最优算法 。
This paper discusses the knight tour problem.A divide & conquer backtracking merge algorithm is presented for searching the Hamilton cycles of the problem.Its time complexity is O(n 2) .Analysis shows it is optimal.The algorithm is valuable to VLSI wiring.
出处
《计算机工程与科学》
CSCD
2000年第2期8-11,共4页
Computer Engineering & Science
基金
国家自然科学基金资助项目!( 695 73 0 40 )
关键词
图论
马步图
HAMILTON圈
最优算法
骑士巡游问题
graph theory
Hamilton cycle
Hamilton path
optimal algorithm
time complexity/knight tour problem
divide and conquer
