关于旅行商问题的若干启发式算法的性能比分析

Performance Ratio Analysis of Several Heuristics Algorithm for the TSP

旅行商问题的增量最小插入法、最近插入法、最近加入法的性能比已经被证明有一个上界2,本文在欧几里德平面上给出了这些方法性能比接近于2的例子。另外,我们证明了凸包选边插入法的性能比有一个关于点数的对数函数上界。

The performance ratios of the cheapest insertion method, nearest insertion method, nearest addition method of traveling salesman problem have been shown to have an upper bound 2, we show the ratios have lower bound approximate to 2. In addition, we prove the performance ratio of the convex hull insertion for the traveling salesman problem in Euclidean plane has the upper bound about a logarithmic function of the number of nodes.