林农

(东莞理工学院 计算机学院，广东东莞 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}，

故

其……