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

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

作　　者：陈继业[1] 张君[1] 

机构地区：[1]邵阳学院理学与信息科学系,湖南邵阳422000

出　　处：《邵阳学院学报（自然科学版）》2006年第1期1-4,共4页Journal of Shaoyang University：Natural Science Edition

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

关 键 词：旅行商问题 环游 插入算法 遗传算子 近似算法 

分 类 号：O242[理学—计算数学]