林农

(东莞理工学院 计算机学院，广东东莞 523808)

旅行商问题图论近似算法有效性分析

林农

(东莞理工学院 计算机学院，广东东莞 523808)

给出旅行商问题四种图论近似算法及有效性分析，改进第一种近似算法证明，修正第二、三、四种近似算法有效性的上界。

旅行商问题;NP难题;图论;近似算法;算法有效性

旅行商问题是组合数学中著名的NP难题［1，2］，它在实际中有着广泛而深入的应用，在超大规模集成电路设计和路径规划都有重要应用价值，它的计算复杂性研究在形成NP完全理论中起到奠基作用［3］。因而这几年对它的研究一直是热点问题。目前对它的研究方法有两类，第一类：思想性和构造性方法，如分支限界法和近似算法。第二类：随着智能算法在各个领域的应用，而产生的一些仿生优化算法，如遗传算法和蚂蚁算法，这一类方法和经典组合数学方法结合，能够加速算法速度，提高解的质量［3］。本文在旅行商问题的四种图论近似算法的基础上，对第一种近似算法证明给予改进，对第二、三、四种近似算法效率的上界给予修正。

1 最近邻法［4］

算法思想和基本步骤：

1) 从一个顶点开始，令P=(j1)。

2) 设当前路径为P=(j1，j2，…，jk)，从尚未搜查的n-k个顶点中加入和jk，最邻近的点jk+1，得到新的路径 P=(j1，j2，…，jk，jk+1)，直至包含 n 个顶点。

3)连接起始顶点和终止顶点，得到就是最近邻法的旅行回路。设最短哈密顿回路长度为，最近邻法旅行回路长度为Nn。

证明 设结点集 A={v1，v2，…，vmin{2k，n}}，

使得与vi相关联的最短边li，满足l1≥l2≥…≥lmin{2k，n}。

由最近邻法知：dij≥min{li，lj}，

故

其中至多有k个αi=0，则至少有min{2k，n}－k个αi=2，

在最小的情况下，k个 αi=0，对应l1，l2，…，lk，

min{2k，n}－ k 个 αi=2 ，对应 lk+1，lk+2，…，lmin{2k，n}，

(证毕)

2 最近邻插入法［4］

算法思想和基本步骤：

1)从一个顶点开始，构造不断扩大的回路。

2)设包含k个顶点的最佳回路为Tk，加入和Tk最邻近的顶点，插入位置使得回路增量最小，成新的最佳回路Tk+1，直至包含n个顶点，即得最近邻插入法旅行回路。设最短哈密顿回路长度为，最邻近插入法旅行回路长度为In。

由最近邻插入法知，存在旅行回路上点p，及点p相邻但不在旅行回路上点q(有时q=i)，及点i在同一道路上。这样点i和边pq建立一一对应关系。当插入点i时，回路增量记为δi，则δi=dij+dikdjk。

δi和dpq的关系如下：

由三角不等式，有dik-djk≤dij，从而 δi=dij+dik-djk≤2dij，又由最近邻插入法，有dij≤dpq，因此δi≤2dpq。

In和T*n的关系如下：

(证毕)

3 生成树加倍算法［5］

算法的思想和基本步骤：

1)求最小生成树;

2)利用深探法遍历最小生成树，回头时遍历边计算在内，即每条边计算两次，得一回路;

3)删除回路中后面重复出现的结点，最后一个除外，得生成树加倍算法旅行回路。

证明

(证毕)

4 生成树加匹配算法［5］

算法的思想和基本步骤：

1)求最小生成树;

2)最小生成树上的奇点，共有偶数个，求最小权匹配;

3)最小生成树及最小生成树奇点的最小权匹配构成欧拉图，求欧拉回路;

4)删除欧拉回路中后面重复出现的结点，最后一个除外。即得生成树加匹配算法旅行回路。

定理4 算法有效性为

设访问最小生成树上奇次结点的顺序和访问最短哈密顿回路结点的顺序相同，得到一个回路。该回路有偶数个结点，可以分解成两个匹配M1，M2。

由三角不等式，得

(证毕)

［1］Lawler E L，Lenstra J K，Rinnooy Kan A H G，et al．The traveling salesman problem：a guided tour of combinatorial optimization［M］．New York：Wiley，1985．

［2］Garey M R，Johnson D S．Computers and intractability：a guide to the theory of NP-Completeness［M］．San Francisco：W H Freeman，1979．

［3］陈继业．旅行商问题的近似算法研究［D］．长沙：国防科技大学，2005．

［4］卢开澄．计算机算法导引-设计与分析［M］．2版．北京：清华大学出版社，2006：276-384．

［5］谢政，李建平．网络算法与复杂性理论［M］．长沙：国防科技大学出版社，1995：332-353．

An Analysis of the Effectiveness of Approximate Algorithms Based on Graph Theory for the Traveling Salesman Problem

LIN Nong
(College of Computer，Dongguan University of Technology，Dongguan 523808，China)

Based on graph theory and their effectiveness，four approximate algorithms are given，adapting the proof technique of the first，modifying the upper bound of the second，third and fourth ．

traveling salesman;graph theory;approximate algorithm;effectiveness of algorithm

O157．5;TP301．6

A

1009-0312(2012)01-0010-04

2011-04-12

林农 (1975—)，女，福建龙岩人，讲师，硕士，主要从事图论及其算法研究。