求马步图Hamilton圈的最优算法

• 作者: 杨晓帆 柏森
• 来源期刊: 计算机工程与科学
• 学科: 工学
• 关键词: 图论 哈密顿圈 哈密顿路径 最优算法 时间复杂度/骑士巡游问题 分治
• 年，卷（期）: 2000,（2）
• 所属期刊栏目: 算法研究
• 页码范围: 8-11
• 页数: 4页
• 分类号: O157.6|TP302
• 字数: 2588字
• 语种: 中文
• DOI: 10.3969/j.issn.1007-130X.2000.02.003

摘要

本文对骑士巡游问题进行了研究,提出了求棋盘马步图的Hamilton圈的"分治-回溯-合并"算法,其时间复杂度是O(n2).分析表明该算法是求棋盘马步图一条Hamilton圈的最优算法,对VLSI的布线问题具有一定的应用价值.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	杨晓帆	重庆大学计算机研究所	4	36	4.0	4.0
2	柏森	重庆通信学院二系	63	601	10.0	22.0