| 改善分支限界法求解旅行商问题效率的策略 |
| |
| 引用本文： | 林冬梅.改善分支限界法求解旅行商问题效率的策略[J].佛山科学技术学院学报(自然科学版),2007,25(5):43-46. |
| |
| 作者姓名： | 林冬梅 |
| |
| 作者单位： | 佛山科学技术学院,信息与教育技术中心,广东,佛山,528000 |
| |
| 摘 要： | 叙述了NP完全问题的复杂性及分支限界法求解问题最优解的策略,分析了利用分支限界法求解旅行商问题过程中影响算法求解效率的主要原因。针对欧氏空间的旅行商问题求解,提出了通过化简初始边集的策略,改善算法的求解效率,通过实验说明了该策略的有效性。该策略可应用到求解旅行商问题的其他算法中。
|
| 关 键 词： | 分支限界法 旅行商问题 初始边集 化简 |
| 文章编号： | 1008-0171（2007）05-0043-04 |
| 修稿时间： | 2007-05-08 |
Strategy of improving the efficiency of branch and bound algorithm to solve traveling salesman problem |
| |
| LIN Dong-mei.Strategy of improving the efficiency of branch and bound algorithm to solve traveling salesman problem[J].Journal of Foshan University(Natural Science Edition),2007,25(5):43-46. |
| |
| Authors: | LIN Dong-mei |
| |
| Affiliation: | Information and Educational Technology Center. Foshan University, Foshan 528000, China |
| |
| Abstract: | This paper narrates in brief the complexity of NP-hard problem and the strategy by which branch and bound algorithm solves the optimum solution of problems,and analyses the foundation stone utilizing branch and bound algorithm to solve traveling salesman problem.In allusion to traveling salesman problem existing in the Euclidean space,the strategy,simplifying the initial edge set,is put forwards to improve the efficiency of the algorithm.The validity of the method is proved by experiments.The method can be applied to other kind of algorithms used to solve traveling salesman problem. |
| |
| Keywords: | branch and bound TSP initial edge set simplifying |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
