求解旅行商问题的一种改进算法

文章研究带三角不等式的旅行商问题．设计了求解该问题的一种嵌入遗传算子的启发式算法；同时阐明该算法具有多项式时间界及其绝对性能比不超过2的界估计，因而它的算法理论基础是坚实的；选择经典算例，通过实验表明：该近似算法较之几种常用的启发式算法解的质量更高．由于该算法本质上仍为插入算法，因而程序设计方便快捷，因此它在实际应用中无疑是极有意义的．

A Kind of New Improving Algorithm to Solve the Traveling Salesman Problem

In this paper, at first, we design a kind of new approximate algorithms by inserting genetic operators to solve the traveling salesman problem, this improveraent is based upon insertion algorithm. Then, some results are strictly proved about it is polynomial algorithm and its absolute performance ratio takes more lower than two; At last, the thesis checked up the algorithms by some representative examples, and makes surely the excellent performance of the algorithms.