運籌學(xué)-第3版-課件-最短路和匹配

1、第三節(jié) 最短路問題,最短路問題是網(wǎng)絡(luò)理論中應(yīng)用最廣的問題之一。許多優(yōu)化問題可以使這個模型，如設(shè)備更新、管道鋪設(shè)、線路安排、廠區(qū)布局等。圖論方法比較有效。最短路問題的一般提法如下：設(shè)G=（V，E）為連通圖，圖中各邊 為圖中任意兩點，求一條道路 ，使他是從 的所有道路中總權(quán)最小的道路。即： 最小.,,,,,,有些

2、最短問題也可以使球網(wǎng)絡(luò)中某指定點到其余所有結(jié)點的最短路，過求網(wǎng)絡(luò)中任意兩點間的最短路。下面我們介紹三種算法，可分別用于求解這幾種最短路問題。一、Dijkstra算法 本算法由Dijkstra于1959年提出，可用于求解指定兩點 間的最短路，或從指定點 到其余各點的最短路，目前被認為是求無負權(quán)網(wǎng)絡(luò)最短路問題的最好方法。算法的基本思想基于以下原理：若序列 是從 的最短

3、路，則序列 必為從 的最短路。,,,,,,,基本步驟：,求出從a到z的最短路的長度是？,,,,,,,,,,,a,c,b,e,d,z,5,4,,2,10,1,8,2,6,3,,,,,,,解：0次迭代（初始化）L(a)=0,L(b)=L(c)=L(d)=L(e)=L(z)= ,S0= ;一次迭代：取u1=a,S1={a} L(a)+w

4、(a,b)=0+4=4<L(b) L(a)+w(a,c)=0+2=2<L(c) L(a)+w(a,d)=0+ = L(a)+w(a,e)=L(a)+w(a,z)=0+ = ; L(b)=4,L(c)=2,L(d)=L(e)=L(z)= 二次迭代：取u2=c,

5、 S2={a,c} L(c)+w(c,b)=2+1=3<L(b) L(c)+w(c,d)=2+8=10<L(d) L(c)+w(c,e)=2+10=12<L(e) L(c)+w(c,z)=2+ = L(b)=3,L(d)=10,L(e)=12,L(z)

6、=,三次迭代：取u3=b, S3={a,c,b} L(b)+w(b,d)=3+5=8<L(d) L(b)+w(b,e)=3+ = L(b)+w(b,z)=3+ = L(d)=8, L(e)=12, L(z)=四次迭代：取u4=d, S4={a,c,b,d} L(d)+w

7、(d,e)=8+2=10<L(e) L(d)+w(d,z)=8+6=14<L(z) L(e)=10, L(z)=14;五次迭代：取u5=e, S5={a,c,b,d,e} L(e)+w(e,z)=10+3=13<L(z) L(z)=13結(jié)束：u6=z, S6={a,c,b,d,e,z}從a到z 的最短路

8、的長度為13,最短路經(jīng)為{a,c,b,d,e,z},同樣可以利用Dijkstra算法計算有向網(wǎng)絡(luò)中最短有向路的長度，基本步驟如下：,求出點1到其余各頂點的最短有向路的長度？,1,,,,,,,,,5,4,3,2,,5,3,2,8,4,7,3,1,Dijkstra算法:,課堂練習1：利用Dijkstra算法，算出圖中，v1到v5的最短路的長度？,,,,,,,,,,,,,,,V1,V3,,V2,V4,V5,4,,3,2,7,5,8,10,1,

9、選址問題：已知某地區(qū)的交通網(wǎng)絡(luò)如圖5-39所示，其中點代表居民區(qū)，邊表示公路， 為小區(qū)間公路距離，問區(qū)中心醫(yī)院建在哪個小區(qū)，可使距離醫(yī)院最遠的小區(qū)居民就診時所走的路程最近?,,解：實際是要求出圖的中心，可以化為一系列求最短路問題。先求出 v1 到其他各頂點的最短路長dj,令D(v1)=max{d1,d2,…,d7},表示若醫(yī)院建在v1, 則離醫(yī)院最遠的小區(qū)距離為D(v1),再依次計算v2,v3,…,v7到其余各點的最短路，類似求出

10、D(v2),D(v3),…D(v7), D(vi)(i=1,2,…,7)中最小者即為所求，計算結(jié)果見表5-3。,由于 D(v6)=48最小，所以醫(yī)院健在v6，此時離醫(yī)院最遠的小區(qū) v5距離為48。,Floyd算法 某些問題中，要求網(wǎng)絡(luò)上任意兩點間的最短路，如例15就是這樣。這類問題可以用Dijkstra算法一次改變起點的辦法計算，但比較繁瑣。這里介紹的Floyd

11、方法（1962）可直接求出網(wǎng)絡(luò)中任意兩點間的最短路。為計算方便，令網(wǎng)絡(luò)的權(quán)矩陣為 。 其中 算法基本步驟為：,首先介紹矩陣的兩種運算：,求圖中任意兩點間的最短有向路的長度？,V1,V4,V5,V3,V2,V6,,,,,,,,,,1,2,2,1,7,3,1,3,,6,課堂

12、練習2：利用Floyd算法，算出圖中任意兩點之間的最短有向路的長度?,1,4,5,2,3,6,,,,,,,,,,,5,3,5,6,,4,2,3,7,2,1,最大匹配問題：考慮工作分配問題。有n個工人，m件工作，每個工人能力不同，各能勝任其中某幾項工作。假設(shè)每件工作只需要一人做，每人只做一件工作，怎樣分配才能盡量的工作有人做，更多的人有工作？這個問題可以用圖的語言描述，如圖5-47。其中x1,x2,…,xn表示工人,y1,y2,…,

13、ym表示工作，邊（xi,yj)表示第i個人能勝任第j項工作，這樣就得到了一個二部圖G，用點集X表示{x1,x2,…xn}，點集Y表示{y1,y2,…,ym} ,二部圖G=(X,Y,E)。上述的工作分配問題就是要在圖G中找一個邊集E的子集，使得集中任何兩條邊沒有公共端點，最好的方案就是要使此邊集的邊數(shù)盡可能多，這就是匹配問題。,定義23 二部圖 G=(X,Y,E) ，M是邊集E的子集，若M中的任意兩條邊都沒有公共端點，則稱M為圖G的一

14、個匹配（也稱對集）。M中任意一條邊的端點v稱為（關(guān)于M的）飽和點，G中其他定點稱為非飽和點。若不存在另一條匹配 ，則稱M為最大匹配。設(shè)M是G的一個匹配，P是G的一條道路，若P中的邊是M與E(G)-M中的邊交替出現(xiàn)的，則稱P為M交錯路；若起點和終點都是M非飽和點，則稱P為M可擴路。如何尋找二部圖中的最大匹配問題？最早是由匈牙利數(shù)學(xué)家Egervary給出的,稱為匈牙利算法：基本思想：尋找非飽和