计算机科学 ›› 2010, Vol. 37 ›› Issue (9): 252-256.
• 人工智能 • 上一篇 下一篇
刘超,王文杰
出版日期:
发布日期:
LIU Chao,WANG Wen-jie
Online:
Published:
摘要： 为了求简单图中的所有Hamilton回路，首先，提出了一种对集合幂集进行编码的算法，引入了接口路径的概念，将Hamilton回路的运算转换为等级接口路径矩阵的运算;其次，结合肖尔茨猜想的证明，对算法复杂性的上限进行了估算;最后，以中国旅行商问题为例，给出了求解CTSP的精确算法。
关键词: 哈密顿回路，中国旅行商，组合优化，接口路径，无穷悖论
Abstract: In order to find all Hamiltonian cycles in a digraph, to begin with, it presented an encoding method for the power set, which converts the problem of Hamilton circuits into the computation of hierarchical matrix Secondly, it estimated the complexity of algorithm with the proof of Xiaerci guess.Finally, it gave the exact algorithm for CTSP.
Key words: Hamiltonian cycle, CTSP, Combination optimization, Interface path, Infinity paradox
刘超,王文杰. 一个由接口路径求Hamilton回路的算法研究[J]. 计算机科学, 2010, 37(9): 252-256. https://doi.org/
LIU Chao,WANG Wen-jie. Research on Hamiltonian Cycle Based on Path with Interface[J]. Computer Science, 2010, 37(9): 252-256. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2010/V37/I9/252
Cited
首页