求解旅行商问题的近似多项式算法

• 作者: 房靖 高尚
• 来源期刊: 智能系统学报
• 学科: 工学
• 关键词: 扩张方法 收缩方法 旅行商问题
• 年，卷（期）: 2010,（4）
• 页码范围: 342-346
• 分类号: TP301.6
• 字数: 2308字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-4785.2010.04.010

摘要

旅行商(TSP)问题是一个典型的组合优化问题,易于描述却难于求解.对于大规模TSP问题,目前仍没有非常有效的方法.针对弹性网络算法在求解旅行商问题中时间性能方面的不足,提出了一种快速的求解算法.在弹性网络算法基础上,提出了求解旅行商问题的扩张方法和收缩方法,它们时间复杂性低于O(N3),经过比较扩张方法的效果比较理想.在扩张方法的基础上,提出随机扩张方法和完全扩张方法,完全扩张方法的时间复杂性低于O(N4),仍然是一个多项式算法.实例表明,完全扩张方法是一个快速且有效的算法.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	高尚	江苏科技大学计算机科学与工程学院	159	1624	18.0	34.0
2	房靖	江苏科技大学计算机科学与工程学院	11	51	5.0	7.0