2.5旅行商问题 上节讨论的哈密顿问路不涉及边的长度。但是在许多实际问题中，每条边都可以有它 的权。边权可以是该路的长度，旅行的费用或所需的时闻，这样需要在可能众多的H回路 中拣选总长最短（或总化费最省，旅途时间最少）的一条。显然这种问题的求解难度也非 常大。 给定一个正权完全图，求其总长最短的哈密顿回路，这就是著名的旅行商问题。容易 知道，对u个结点的完全图，存在？n-1)!个不同的H回路。旅行商间题也属于NP完 企问题，如果采用枚举法，将需要对。(n一J)!个不同的H回路进行比较，在较大时，这 在让算上是不可行的。对这类问题一种好的精确求解法是分支与界法。以下我们举例说 明它的基本思路。 例2.5.1图2.19表示5个城市间的铁路线，各边的值 表示该线路的旅途费用。求从出发经各城市-次且仪-次 最后返回总费用最省的一条路径。 解：该问题就是求G的一条最短的H回路。采用分支与 10 界法的基本思路是： 1,首先将边权由小至大排序，初始界d一∞。该例中 a:a342a:5a:6a12a:3a34a23a45a2s :3449101011131620 为了尽快找到最优解，我们采用DFS方法和以下的分支判断 图2.19 步骤： 2.在边权序列中依次选边进行深探，直至选取n条边，判断是否构成H可路（每个结 点标号只出现2次，月这些边只构成一个回路)，若是，d,d(s),结束。。 该例中 ds:）=d(1)=d(a53,a2,as,aaa2)=30, 山于，出现了3次，故非所求。 3.(继续深探)依次剔除当前中的最长边，加入后面第一条待选边，进行深探，如 果它是H回路且d(s,)<da,则d-d(s:)作为界。 4.(退栈过程)不能再深探时需要退栈。如果栈空，结束，其最佳值为d,。否则如果 新分支的d(s)≥d,继续退栈：若d(s)<d,转3。 整个求解过程如图2.20所示，其中a,表示删除a,a,表示保留该边。中于d(6)=32, 是合理解，同时其余分支的值都人它，因此它是最短的H回路。 图2.20中 d(1)=d(a3,a42a:sa1,az)=30。 d(2)=d(a33a2a15,a4,a1a)=30。 d(3)-d(as,a2as,a1,a4)=31。 ·21
au B d13 a a13 d(5) a15/ d(6) d(7) A au d(1)a13 a13 C、 d(2)a4 a d(3》az d(4) a13/ d(8) 图2.20 d(4)=d(a53a2a45,a4,a23)=33·。 d(5)=d(a3,a42,a1s,a12,a1s)=31。 d(6)=d(a63,a42,a1s,a:2,aa4)=32·。 d(7)=d(a53,a42,a1ea1a,a34)=32。 d(8)=d(a53,a42,a1a,a:2,a13)=36。 所以最优解为d(6)=32。 由于对边权进行了排序，因此每删去一条短边，增一条长边，其总和是非减的。即该结 点以下分支的各种状态的值都不会小于该点的值。同时由于一切合理的与不合理的解都 大于等于d。,因此d。必为最优解。 从以上分析看，这种搜索过程是在不断地构造分支与确定界值。一旦确定了界值，则 对大于等于界值的分支不再搜索，而且最后得到的界值就是问题的最佳解。因此这种方法 称为分支与界法。从该例看，分支与界法比枚举法优越得多，但是在最坏情况下，其计算复 杂度仍为O(!)。因此在实际问题中，人们经常采用近似算法求得问题的近似最优解，从 而避免浩翰的计算量。 在设计近似算法时，往往需要对原问题增加一些限制，以便能够提高计算速度和近似 效果。而这些限制又常常都是比较符合实际的。比如旅行商问题里的限制是：(1)G是无向 止杖图。(2)符合三角不等式，即任意结点，，和之间，两边长度之和大于等于第三边 长度。在这些条件下，旅行商问题有多种近似算法。这里我们介绍“便宜”算法。 算法描述如下： a.置5={2,3，…，n},w(11)←0，-1，序列T=(1,1), 0(i,)e(i,1),i∈S。 b.在S中，令 ·22*
w(j.t)=minw(i,k). AET 对回路T中的边(t,t,),(t,t), 若u(,t,)-w(t,t)≤u(j,t）-(t,l2）, 则插入到T的t,t之间，不则j插入到T的t,t2之间， 5-5-j 若S=Φ，结束。否则转c。 c.对全部i∈S,置 w(i,k)+-min(w(i,k),w(i,j)), 转b。 算法中，T是一个不断扩充的初级回路，最初是一个自环。在步骤b中，首先选取5中 与T距离最近的一个结点j。设(t)是相应的边。这时结点j或插入到回路T中t的前 面，或插到其后。这根据j插入后回路T长度增量的大小而定。即如果w(j,t)十心(j4) 一w(t,t:)≤w(),t)〦w(),t2)一w(l,t2),则插入到t与t1之间。否则在t与t2之间。这就 是“便宜”的含义。 ,例2.5.2已知图G的权矩阵，其旅行商问题采用便宜算法近似求解的过程如图 2.21所示。 27 19 18 minw(i,k):w(2,1)=18 w(5,2)=19 w(4,2)=21 05 27 24 24 27 17 18 18 23 π(T)=109 w(3,4)=17 图2.21 「0 18 35 25 277 18 0 23 2119 35 2301728 25 21170 24 271928240」 定理2.5.1设正权完全图的边权满足三角不等式，其旅行商问题的最佳解是O,便 ·23·
∠2o 宜算法的解是T。则元 证明：设往初级回路T中每圳入·个结点j后，该回路的增量是8，，二心一ex一 心。我」将证明6，与最佳解中除最长边之外的某条边（设长度为）形城对应，并月d,≤ 21u。 初始T。=0.当加入一个结点j后，由于e(j,1)=min(i,1).当然w(j,1)不会人 ()中结点1所关联的两条边巾任意一个边权。取其中小的边权为1u,自然有，≤21u。在 G中删去权为l4的边，即构成对应。 设T。时满足条件，则构造T。时，O.中肯定有·些尚 未删除的边与T-:中的结点关联，否则与()，是11回路矛 盾。设其中最短边是(p,?),如图2.22所示。假定此时由算 法加入T,的边不是(p,q),而是(，t)。显然 (j,t)u(p,9)。 (1) 出不等式 (j,t)≤w(j,t)十w(t,t),i=1,2, ∴.w(j,t)≤w(p,9)十w(t,）。 (2) 图2.22 由(1)(2)式立得 8,≤2w(p,9)。 此时8，与O,中的边(p,4)对应，删除(，9)。因此I,时也满足条件。定理得证。 使宜算法的计算复杂度是O(n)。其效率比枚举法或分支与界法要高得多。虽然从理 论上讲它的近似程度并非理想，但是在实际上它与最优解常常十分接近。比如例2.5.2的 最优解是107，而便宜算法的解是109， 2.6最短路径 以下三节讨论赋权图的最优化道路。它1都具有明显的实际背景，有相当重要的应用 价值。 按照实际问题的模型，最短路径问题可以包括： 1.某两结点之间的最短路径。 2.某结点到其它各结点的最短路径。 3.任意两结点之间的最短路径。 相应地图G各边的权w(e)还可以有如下特点：(a)均大于0：(6)均等于1；(c)是任意实 数。容奶看出，如果模型2得到解决，模型1和模型3就能迎刀而解。因此我们将只依边 权的二种情形讨论模型2的最短路径，并且局限∫求到其它各点的最短路径， 到，的-·条路径P(i)的长度记为r(i)。 r(i)= tt(e)。 心(e)表示边e=(w)的权，也记为w#。结点：到的最短路径就是满足上式的极小的 π(i)。 ·24·
如果·条长度为π()的道路P()中包含有回路('.令”()是其中不含(：的初级道 路，显然π()π()+π(C)。其中π(C)表示同路C的长度。若r()<0,即（是负长回 路，则：到，不可能有最短路径；若π()0，测()i),即，到”的最短路称一定 是初级道路。本节讨论的都是无负长回路的图、 2.6.1“正权图中1到各点的最短路径 引理2.6.1正权图G中，如果P()是，到的最短路，且，∈I(i),则()是， 到，的一条最短路。 证明：如果P(》不层最短路，则存在~条最矩路P(),使x()<π(》，这样(1)= x()+π(j,)<π(i)π(j)中十x(j,),与P()是最短路矛盾。 引理2.6.2正权图中任意，~条最短将径的长度人子其局部路径长度。 结论是显然的。 假定已经知道从，到其余各点的最短路P(,)(k=1,2,…·n),并且满是 π(1)=r(i1)π(i2)…π(in）。 由引理2.6.2知，若>l(≥1)，则P(i)不可能是P(i)的一部分。再由引理2.6.1可得 ()=识6)+w,。 这就是最短路径的Dijkstra算法的基础。 Dijkstra算法描述如下： iei订 a,置S={2,3,…,n},r(1)=0,π()= 其它 b.在S中，令 )=m不i, 置55-{j}, 若S=中，结束。否则转c。 c,对全部i∈S∩片，登 π(i)-min(r(2),r(》L'), 转b 其中执行步骤c时，j已属于(V(G)-),因此3中 可能使π(i)发生变化的只能是j的直接后继。 例2.6.1用Dijkst1ra算法求图2.23中，到其余各 点的最短路过程如下： D 1.r(3)=mnπ()a1. π(2)=6，r(4)=0, π(5)=3，r(6)=8, 2.π(5)=minr(i)3. 图么23 π(2)=6，r(4)8,r(6)=8, 3.r(2)=minx(i)=6, π(4)=8.T(61=7, ·25·