用启发式贪心法求解旅行商问题

被引：19

作者：

潘立登

黄晓峰

机构：

[1] 北京化工大学自动化系

来源：

关键词：

旅行商问题；启发式算法；贪心法；多项式时间算法；组合优化;

D O I：

10.13543/j.cnki.bhxbzr.1998.02.009

中图分类号：

TP202.7 [];

学科分类号：

摘要：

旅行商问题是ＮＰ完全的组合优化问题。分析了邻域启发式算法的基本操作，提出一种简单的启发式贪心法，仅利用城市间的距离信息求解旅行商问题。理论分析与实验结果表明该方法是确定性的多项式时间算法。对５个不同规模的典型的旅行商问题进行优化，均达到或优于文献中的结果。

引用

页码：48 / 53

页数：6

共 4 条

[1] 用改进的遗传算法求解中国旅行商问题 [J].

潘立登 ;

黄晓峰 .

[2] 遗传算法及其在TSP中的应用 [J].

房育栋，郝建忠，余英林，温玉汉 .

[3] 求解中国旅行商问题的新结果 [J].

杨忠 ;

鲍明 ;

张阿舟 .

[4]

动态规划[M]. 北京理工大学出版社 , 张润琦编, 1989