大数据

当前位置:首页 > 大数据

《算法导论》第三十五章(续1)

35.2旅行商问题

34.5.4节介绍的旅行商问题中,输人是一个完全无向图G=(V,E),其中每条边(u,v)∈E都有一个非负的整数代价cu,v),我们希望找出G的一条具有最小代价的哈密顿回路。现在我们把前面所用的记号表示略作扩充,设c(A)表示子集ACE中所有边的总代价:

QQ截图20220816155111.png

在很多实际情况中,从一个地方u直接到另一个地方w花费的代价总是最小的。如果一条路径经过了某个中转站,则它不可能具有比直接到达更小的代价。换句话说,去掉途中一-个中转站绝不会使代价增加。将这种情况加以形式化,即如果对所有的顶点u,v,w∈V,有:

c(u,w)≤c(u,v)+c(v,w)

就称代价函数c满足三角不等式。

三角不等式是个很自然的不等式,许多应用都满足三角不等式。例如,如果图的顶点为平面上的点,并且在两个顶点间旅行的代价为它们之间的欧几里得距离(即两点间的线段距离),那么这种情况就满足三角不等式。除了欧几里得距离外,还有许多其他的代价函数能满足三角不等式。

如练习35-22所示,即使代价函数满足三角不等式,也不能改变旅行商问题的NP完全性。因此,不能寄希望于找到一个准确解决旅行商问题的多项式时间算法。相反,我们应该寻找一些好的近似算法。

35.2.1节将讨论一个2近似算法,用于解决符合三角不等式的旅行商问题。35.2.2节将证明如果旅行商问题不符合三角不等式,则不存在具有固定近似比的多项式时间近似算法,除非P=NP。

35.2.1满足三角不等式的旅行商问题

利用前一小节的方法,我们首先要计算出一个结构(即最小生成树),其权值是最优旅行商路线长度的下界。接着,要利用这一最小生成树来生成一条遍历线路,其代价不大于最小生成树权值的2倍,只要代价函数满足三角不等式即可。下面的算法实现了这一过程,该算法将23.2节中的最小生成树算法MST-PRIM作为子程序加以调用。输人G是一个完全无向图。代价函数c满足三角不等式。

APPROX-TSP-TOUR(G,c)

1 select a verte r∈G.V to be a "root"vertex

2 compute a minimum spanning tree T for G from root r

using MST-PRIM(G,c,r)

3 let H be a list of vertices,ordered according to when they are first visited

in a preorder tree walk of T

4 return the hamiltonian cycle H

如12.1节所述,先序遍历会递归地访问树中的每个顶点,在第一次遇到某个顶点时(在访问其孩子之前)就输出该顶点。

图35-2说明了APPROX-TSP-TOUR的操作过程。图35-2(a)给出了一个完全无向图。图35-2(b)给出了一棵由MST-PRIM计算出来的最小生成树T,其以顶点a为根结点。图35-2(c)给出了对T进行先序遍历时,各顶点的访问顺序。图35-2(d)给出了由APPROX-TSP-TOUR返回的旅行路线。图35-2(e)给出了一个最优的旅行路线,它比图35-2(d)中的旅行路线要短约23%。

QQ截图20220816155543.png

根据练习23.2-2,即使是采用MST-PRIM的简单实现,APPROX-TSP-TOUR的运行时间也是Θ(V2)。现在我们来证明:如果旅行商问题某一实例的代价函数满足三角不等式,则APPROX-TSP-TOUR所返回的旅行路线的代价不大于最优旅行路线代价的2倍。

定理35.2  APPROX-TSP-TOUR是一个用于解决满足三角不等式的旅行商问题的多项式时间⒉近似算法。

证明  前面已经证明了APPROX-TSP-TOUR的运行时间为多项式。

设H*表示在给定顶点集合上的一个最优旅行路线。我迪过期际一个1p域下的徂从边而得到生成树,并且每条边的代价都是非负的。因此,田APPRUX-ISP-1UUK弟匕门付到的最小生成树T的权值是最优旅行路线代价的一个下界:

c(T)≤c(H*)

(35.4)

对T进行完全遍历时,在初次访问一个顶点时输出该顶点,并且在访问一棵子树返回后输出该顶点。我们称这个遍历为W。对例子中的树进行完全遍历,得到次序

a,b,c,b,h,b,a,d,e,f,e,g,e,d,a

因为该完全遍历恰经过了T的每条边两次,所以有(可以将代价c的定义加以自然的扩股,用以处理边集的情况):

c(W) = 2c(T)

(35.5

由式(35.4)和式(35.5)得

c(W)≤2c(H*)

(35.6)

即W的代价在最优旅行路线代价的2倍之内。

但是,W一般来说不是一个旅行路线,因为它对于某些顶点的访问次数超过一次。然而,根据三角不等式,如果从W中去掉一次对任意顶点的访问,代价并不会增加。(如果在对顶点u和w的访问之间,从W中去掉顶点u,所得的旅行路线顺序就指示了直接从u到w。)反复应用这个操作,可以从W中将对每个顶点除第一次访问之外的其他各次访问去掉。在我们的例子中,这样的一个操作过程即可得旅行次序:

a,b,c,h,d,e,f,g

这个次序与对树T进行先序遍历所得的次序是一样的。设H为对应先序遍历的回路。它是个哈密顿回路,因为每个顶点仅被访问一次,并且它实际上是由APPROX-TSP-TPUR计算出来的回路。因为H是通过从完全遍历W中删除了某些顶点后得到的,所以有:

c(H)c(w)

(35.7)

将不等式(35.6)和不等式(35.7)结合起来,则有c(H)≤2c(H*),从而完成对本定理的证明。

尽管定理35-2给出了很好的近似比,但在实践中,APPROX-TSP-TOUR通常并不是解决旅行商问题的最佳选择。有些近似算法的实际性能要比APPROX-TSP-TOUR算法好得多(具体可见本章末的参考文献)。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~