圖論旅行商tsp課件

(Ⅲ)圖論

12.5

旅行商問(wèn)題

1.旅行商問(wèn)題:對(duì)正權(quán)完全圖G，求G總長(zhǎng)最短的H回路。(區(qū)別Euler回路與H回路)2.求解算法：分支定界法分支定界法是一種用較好方式搜索的準(zhǔn)枚舉法，實(shí)質(zhì)上就是按字典序枚舉所有可能情形并結(jié)合剪枝(過(guò)濾)的辦法。

例由A,B,C,D,E中的三個(gè)不同字母構(gòu)成的全部字符串，按字典序的排列：

ABC,ABD,ABE,ACD,ACE,ADE,BCD,BDE,CDE23.分支定界法初始階段：1.將全部邊按權(quán)由小到大排列；2.取前n邊作為S，置d0:=∞。(d0為已考察的H回路中最短的路長(zhǎng))迭代階段：3.若S構(gòu)成H回路且其路長(zhǎng)d(S)＜d0，則d0:=d(S)。跳過(guò)比當(dāng)前d0差的后續(xù)情形后,用剩下未考察的第一組邊作為S，返回3。全部情形考察完畢時(shí)的d0即為最短H回路長(zhǎng)度，取其值的那個(gè)S就是問(wèn)題的解。（將一條邊看作一個(gè)字符，步驟1已得各字符間的先后關(guān)系。對(duì)于長(zhǎng)為n且各字符互異的所有字符串，本算法要按字典序的順序逐一考察每一字符串)3邊：

a35a24a15a14a12a13a34a23a45a25權(quán)：

3449101011131620分支定界：

S1:a35a24a15a14

a12,非H回路,d(S1)=30;S2:a35a24a15a14

a13,非H回路,d(S2)=30；S3:a35a24a15a14

a34,非H回路,d(S3)=31；S4:a35a24a15

a14

a23,H回路,d0:=33;S5:a35a24a15

a12

a13,非H回路,d(S5)=31;S6:a35a24a15

a12a34,H回路,d(S6)=32,d0:=32;S7:a35a24a15

a13a34,非H回路,d(S6)=32;S8:a35a24

a14a12a13,非H回路,d(S6)=36;

繼續(xù)下去所得組長(zhǎng)度會(huì)比S8差，故可終止計(jì)算。5故最優(yōu)解為S6，其長(zhǎng)度為32。計(jì)算要掌握兩個(gè)要點(diǎn)：1.按字典序逐一考察各邊集；2.每次考察完一個(gè)邊集后，應(yīng)考慮是否可以用過(guò)濾條件(當(dāng)前d0值)跳過(guò)一些不必要情形的考察，因?yàn)楸犬?dāng)前d0值差的情形不需考慮。64.近似算法－－“便宜”算法

分支定界法雖可求得旅行售貨員問(wèn)題的準(zhǔn)確最優(yōu)解，但計(jì)算復(fù)雜度為O(n!)，故對(duì)大型問(wèn)題需尋找近似算法求解。需采用近似算法往往需要增加一些限制，以便能夠提高計(jì)算速度和近似程度：(1)G是無(wú)向正權(quán)圖。(2)對(duì)圖中任意的三點(diǎn)構(gòu)成的三角形，其中任何兩邊之和大于第三邊。7例(1)t10(2)找出回路外到v1最近的點(diǎn)（在第一行找）v2，插入回路：v2v11818(3)找出到v1,v2最近的點(diǎn)（第1,2行去掉第1,2列后，在此范圍找）v5，插入回路：v5v2v12718199(4)找出到v1,v2,v5最近的點(diǎn)（第1,2,5行去掉第1,2,5列后，在此范圍找）v4，插入回路：v2v1v5v418242721(5)找出到v1,v2,v5,v4最近的點(diǎn)（第1,2,4,5行去掉第1,2,4,5列后，在此范圍找）v3，插入回路：17v424v2v1v5v318272310

2.6最短路徑

1.

最短路問(wèn)題在一個(gè)賦權(quán)圖中，將權(quán)視為邊長(zhǎng)，求指定兩結(jié)點(diǎn)之間的最短路長(zhǎng)及路線(xiàn)。正權(quán)圖中V1到各點(diǎn)的最短路徑

對(duì)于正權(quán)圖G，若L是點(diǎn)vs到點(diǎn)vt的最短路，且L經(jīng)過(guò)點(diǎn)vj，記L中從vj到vt的那部分路線(xiàn)為L(zhǎng)’，則L’就是vj到vt的一條最短路。vsvjvtL’L”(否則路線(xiàn)(vs→vj)+L”比L更短,矛盾)11

Dijkstra

算法：

1)

讓d(1):=0,S:={1},k:=1,E:=Φ;d(i)=w1i,i=2,3,…,n.(若圖中邊(vi,vj)不存在，則記wij

=∞)

2)

在S以外的所有點(diǎn)中找標(biāo)號(hào)最小的點(diǎn)：d(k0)=min{d(j):vj不在S中};

3)S:=S∪{k0},k:=k0,E:=E∪{ek0}(為取到值d(k0)的邊),并修改與vk0相鄰的點(diǎn)的標(biāo)號(hào)：d(j):=min{d(j),d(k)+wkj},jS.若|S|=n，則終止迭代；否則回到第2步。(注意理解jS時(shí)標(biāo)號(hào)d(j)的含義)13對(duì)本算法的理解及算法正確性的證明：(實(shí)線(xiàn)表示圖中一條邊，虛線(xiàn)表示若干條邊組成的一條路)v1Svk0S14例求v1到其它各點(diǎn)的最短路。v1v6v3v5v4v27316453721令d(v1)=0,則(紅點(diǎn)集合表示S):viv1v2v3v4v5v6d(vi)061838viv1v2v3v4v5v6d(vi)071∞∞∞viv1v2v3v4v5v6d(vi)061837viv1v2v3v4v5v6d(vi)061838viv1v2v3v4v5v6d(vi)071∞3815v1v6v3v5v4v21111111111例求v1到其它各點(diǎn)的最短路。令d(v1)=0,則(紅點(diǎn)集合表示S):viv1v2v3v4v5v6d(vi)011∞∞∞viv1v2v3v4v5v6d(vi)011222viv1v2v3v4v5v6d(vi)011222172.權(quán)有負(fù)數(shù)時(shí)最短路問(wèn)題的求解

——Ford算法權(quán)有負(fù)數(shù)時(shí)Dijkstra算法失效。(為什么?)

若圖中不含負(fù)回路時(shí)最短路問(wèn)題可解。Ford算法采用迭代的辦法，逐步逼近并最終得到最優(yōu)解。算法中第k次迭代后，d(i)表示從起點(diǎn)v1到點(diǎn)vi的一條路的長(zhǎng)度，且d(i)小于或等于邊數(shù)不超過(guò)k的最短路的長(zhǎng)度。因此，算法的迭代次數(shù)不超過(guò)n。18Ford算法1)令d(1):=0,d(i):=∞,i=2,3,…,n;p:=1;2)對(duì)i=2,3,…,n,修改vi的標(biāo)號(hào)：d(i):=min(d(i),min(d(k)+wki)).p:=p+1;kvivk…3)若全部d(i)沒(méi)有變化則結(jié)束;否則,當(dāng)p<n時(shí)轉(zhuǎn)向2)，當(dāng)p≥n時(shí)存在負(fù)回路問(wèn)題無(wú)解.19改進(jìn)

Ford算法工作量由迭代次數(shù)確定。為減小迭代次數(shù)，先刪除權(quán)為負(fù)數(shù)的邊，使用Dijkstra算法，所得解為近似最優(yōu)解。按計(jì)算所得路長(zhǎng)對(duì)各結(jié)點(diǎn)從低到高排隊(duì)，重新編號(hào)。再添上負(fù)數(shù)邊，將Dijkstra算法得到的路長(zhǎng)作為路長(zhǎng)的初值，可有效提高算法的效率。212.7

關(guān)鍵路徑1.PT圖一個(gè)結(jié)點(diǎn)表示一道工序。工序i完工后才能開(kāi)始工序j表示為一條有向邊(i,j),邊長(zhǎng)表示完成此工序所需時(shí)間。于是，一個(gè)工程可用一個(gè)有向圖表示，這就是PT圖。求最早完工時(shí)間，就是求PT圖的最長(zhǎng)路長(zhǎng)度，而最長(zhǎng)路即為完成工程的關(guān)鍵工序（關(guān)鍵路徑）。22

PT圖中不可能存在有向回路，故可對(duì)全部結(jié)點(diǎn)重新編號(hào)，使得每條有向邊總是由編號(hào)小的結(jié)點(diǎn)指向編號(hào)大的。最長(zhǎng)路的計(jì)算完全類(lèi)似于Dijkstra算法的過(guò)程。（求min改為求max）23PERT圖中不可能存在有向回路，故可對(duì)全部結(jié)點(diǎn)重新編號(hào)，使得每條有向邊總是由編號(hào)小的結(jié)點(diǎn)指向編號(hào)大的。

最長(zhǎng)路的計(jì)算完全類(lèi)似于Dijkstra算法的過(guò)程。（求min改為求max）252.8中國(guó)郵路問(wèn)題定義

例某郵遞員負(fù)責(zé)在若干街道投遞郵件。現(xiàn)從郵局出發(fā)，經(jīng)過(guò)每一條街道最后返郵局，問(wèn)如何行走，使得投遞線(xiàn)路最短。這就是“中國(guó)郵路”問(wèn)題。

中國(guó)郵路問(wèn)題:

設(shè)G是一個(gè)連通的正權(quán)簡(jiǎn)單圖，問(wèn)如何在G中添加重復(fù)邊，使G有歐拉回路，且重復(fù)邊的總長(zhǎng)最小。26算法

(1)適當(dāng)加邊，使所有結(jié)點(diǎn)成為偶點(diǎn)(度數(shù)為偶數(shù)的點(diǎn))，并且每邊的重復(fù)邊不超過(guò)一條。(2)檢查每個(gè)回路，若回路中重復(fù)邊長(zhǎng)之和大于整個(gè)回路長(zhǎng)的一半，則在該回路上作邊的刪增：使重復(fù)邊不重復(fù)，使不重復(fù)邊重復(fù)。

若所有回路都滿(mǎn)足要求(重復(fù)邊長(zhǎng)之和不大于整個(gè)回路長(zhǎng)的一半),則終止迭代。

例(p.33)293.有向圖的中國(guó)郵路問(wèn)題

對(duì)于有向圖來(lái)說(shuō),中國(guó)郵路問(wèn)題可能無(wú)解。其原因是G中可能含有出度(正度)或入度(負(fù)度)為0的結(jié)點(diǎn)，可能進(jìn)得去出不來(lái)或出得去回不來(lái)。如果各結(jié)點(diǎn)的正、負(fù)度相等，則G中存在有向Euler回路。它經(jīng)過(guò)每邊一次且僅一次，因此任一條Euler回路都是中國(guó)郵路。以下通過(guò)一個(gè)例，介紹它的求解方法。30v1v2v3v4v585123257(1)添加總發(fā)點(diǎn)vs總收點(diǎn)vt，求vs到vt的2條有向最短路，將它們添加到原圖中去。例求有向圖的中國(guó)郵路問(wèn)