數(shù)學(xué)建模～最短路問題(課件ppt)

1、最短路問題最短路問題二、最小生成樹問題及其解法二、最小生成樹問題及其解法三、最短路問題及其解法三、最短路問題及其解法一、圖論的基本概念一、圖論的基本概念圖圖 論論 的的 基基 本本 概概 念念一、一、 圖圖 的的 概概 念念1 1圖的定義圖的定義2 2頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù) 3 3子圖子圖二、二、 圖圖 的的 矩矩 陣陣 表表 示示1 1 關(guān)聯(lián)矩陣關(guān)聯(lián)矩陣2 2 鄰接矩陣鄰接矩陣返回返回定義定義有序三元組有序三元組G=(V,E, )稱為一個(gè)圖稱為一個(gè)圖,如果：如果：圖的定義圖的定義定義定義定義定義返回返回頂點(diǎn)的次數(shù)頂點(diǎn)的次數(shù)4()4dv5)(3)(2)(444vdvdvd例例2 2 在一次聚會(huì)中

2、，史密斯先生和他太太邀請(qǐng)四對(duì)夫妻在一次聚會(huì)中，史密斯先生和他太太邀請(qǐng)四對(duì)夫妻參加晚會(huì)。每個(gè)人到的時(shí)候，房間里的一些人都要與別的參加晚會(huì)。每個(gè)人到的時(shí)候，房間里的一些人都要與別的一些人握手。當(dāng)然，每個(gè)人都不會(huì)與自己的配偶握手，也一些人握手。當(dāng)然，每個(gè)人都不會(huì)與自己的配偶握手，也不會(huì)跟同一個(gè)人握手兩次。不會(huì)跟同一個(gè)人握手兩次。之后，史密斯先生問每個(gè)人和別人握了幾次手，他們的答之后，史密斯先生問每個(gè)人和別人握了幾次手，他們的答案都不一樣。那么史密斯太太和別人握了幾次手呢？案都不一樣。那么史密斯太太和別人握了幾次手呢？返回返回例例1 1 在一次聚會(huì)中，認(rèn)識(shí)奇數(shù)個(gè)人的人數(shù)一定是偶數(shù)。在一次聚會(huì)中，認(rèn)識(shí)奇

3、數(shù)個(gè)人的人數(shù)一定是偶數(shù)。由圖可知，由圖可知，8 8號(hào)的配偶是號(hào)的配偶是0 0號(hào)。號(hào)。7號(hào)的配偶是號(hào)的配偶是1號(hào)。號(hào)。6號(hào)的配偶是號(hào)的配偶是2號(hào)。號(hào)。5號(hào)的配偶是號(hào)的配偶是3號(hào)。號(hào)。史密斯太太是史密斯太太是4號(hào)，所以史密斯太太和別人握了號(hào)，所以史密斯太太和別人握了4次手。次手。返回返回鄰接矩陣鄰接矩陣注：假設(shè)圖為簡單圖注：假設(shè)圖為簡單圖返回返回最最 短短 路路 問問 題題 及及 其其 算算 法法一、一、 基基 本本 概概 念念二、固二、固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路三、每三、每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路返回返回基基 本本 概概 念念返回返回返回返回求圖的

4、最小生成樹最常用的兩種算法：求圖的最小生成樹最常用的兩種算法：（1）Prim算法算法（2）Kruskal算法算法注意：在一個(gè)加權(quán)連通圖注意：在一個(gè)加權(quán)連通圖G中，權(quán)最小的那棵中，權(quán)最小的那棵生成樹稱為圖生成樹稱為圖G的最小生成樹。的最小生成樹。返回返回Prim算法思想：算法思想：輸入加權(quán)圖的帶權(quán)鄰接矩陣輸入加權(quán)圖的帶權(quán)鄰接矩陣（1）建立初始候選邊集）建立初始候選邊集B， ；（2）從候選邊中選取最短邊（）從候選邊中選取最短邊（u,v），）， ；（3）調(diào)整候選邊集）調(diào)整候選邊集B；（4）重復(fù)（）重復(fù)（2）、（）、（3）直到）直到T含有含有n-1條邊。條邊。nnjia),(T),(vuTTPrim算

5、法的實(shí)現(xiàn)過程算法的實(shí)現(xiàn)過程45231 1 1 12 3 4 58 inf 1 5439453527236實(shí)現(xiàn)實(shí)現(xiàn)Prim算法的算法的MATLAB程序：程序：a=0 8 inf 1 5;8 0 6 inf 7;inf 6 0 9 10;1 inf 9 0 3; 5 7 10 3 0;T= ;e=0; v=1; n=5; sb=2:n; %1代表第一個(gè)紅點(diǎn)，代表第一個(gè)紅點(diǎn)，sb代表白代表白點(diǎn)集。點(diǎn)集。for j=2:n %構(gòu)造初始候選邊的集合構(gòu)造初始候選邊的集合 b(1,j-1)=1; b(2,j-1)=j; b(3,j-1)=a(1,j);endwhile size(T,2) n-1 min,i

6、=min(b(3,:); %在候選邊中找最短邊。在候選邊中找最短邊。 T(:,size(T,2)+1)=b(:,i); e = e + b(3,i); v = b(2,i); v表示新涂的紅點(diǎn)。表示新涂的紅點(diǎn)。 temp = find(sb = b(2,i); sb(temp) = ; b(:,i) = ; for j =1:length(sb) %調(diào)整候選邊調(diào)整候選邊 d = a(v,b(2,j); if db(3,j) b(1,j) = v; b(3,j) = d; end endendKruskal算法思想：算法思想：假設(shè)給定了一個(gè)加權(quán)連通圖假設(shè)給定了一個(gè)加權(quán)連通圖G，G的邊集合為的邊集

7、合為E，頂點(diǎn)，頂點(diǎn)個(gè)數(shù)個(gè)數(shù)n，則假設(shè)最小生成樹，則假設(shè)最小生成樹T中的邊和頂點(diǎn)均涂為紅色，中的邊和頂點(diǎn)均涂為紅色，其余為白色。初始時(shí)其余為白色。初始時(shí)G中的邊均為白色。中的邊均為白色。（1）將所有的頂點(diǎn)涂成紅色；）將所有的頂點(diǎn)涂成紅色；（2）在白色邊中，挑選一條權(quán)最小的邊，使其與紅色）在白色邊中，挑選一條權(quán)最小的邊，使其與紅色邊不形成圈，將該白色邊涂紅。邊不形成圈，將該白色邊涂紅。（3）重復(fù)（）重復(fù)（2）直到）直到n-1條紅色邊，這條紅色邊，這n-1條紅色邊就條紅色邊就構(gòu)成了最小生成樹構(gòu)成了最小生成樹T的邊集合。的邊集合。注意：在用注意：在用Kruskal算法求最小生成樹時(shí)，在第（算法求最小生

8、成樹時(shí)，在第（2）步判斷是否形成圈在程序?qū)崿F(xiàn)時(shí)比較麻煩。步判斷是否形成圈在程序?qū)崿F(xiàn)時(shí)比較麻煩。實(shí)現(xiàn)實(shí)現(xiàn)Kruskal算法的算法的MATLAB程序：程序：%加權(quán)圖的存儲(chǔ)結(jié)構(gòu)采用邊權(quán)矩陣加權(quán)圖的存儲(chǔ)結(jié)構(gòu)采用邊權(quán)矩陣b(i,j)m3b=1 1 1 2 2 3 3 4 2 4 5 3 5 4 5 5 8 1 5 6 7 9 10 3;B,I=sortrows(b,3); B=B;m =size(b,2); n=5;t=1:n; k=0; T= ; c = 0;for i= 1:m if t(B(1,i)=t(B(2,i) %判斷第判斷第i條邊是否與樹中的邊形條邊是否與樹中的邊形成圈。成圈。 k=k+1

9、; T(k,1:2) = B(1:2,i); c=c+B(3,i); tmin = min(t(B(1,i),t(B(2,i); tmax = max(t(B(1,i),t(B(2,i); for j=1:n if t(j) = tmax t(j)= tmin; end end end if k=n-1 break; endendT,cKruskal實(shí)現(xiàn)過程：實(shí)現(xiàn)過程：初始化后排序：初始化后排序：B=1 4 1 2 2 1 3 3 4 5 5 3 5 2 4 5 1 3 5 6 7 8 9 10；第一輪：第一輪：tmin=1;tmax=4;t=1 2 3 1 5;第二輪：第二輪：tmin=4;

10、tmax=5;t=1 2 3 1 1;第三輪：第三輪：t(1)=t(5)直接進(jìn)入下一輪直接進(jìn)入下一輪第四輪：第四輪：tmin=2;tmax=3;t=1 2 2 1 1;第五輪：第五輪：tmin=1;tmax=2;t=1 1 1 1 1;求最短路徑的最常用的兩種算法：求最短路徑的最常用的兩種算法：（1）Dijkstra算法算法（2）Floyd算法算法注意：普通路徑長度定義為該路徑所包含的全體邊注意：普通路徑長度定義為該路徑所包含的全體邊的長度之和。的長度之和。最短路徑是指在圖中，從頂點(diǎn)最短路徑是指在圖中，從頂點(diǎn)u到頂點(diǎn)到頂點(diǎn)v的路徑中普的路徑中普通路徑長度最短的路徑稱為通路徑長度最短的路徑稱為u

11、到到v的最短路徑。的最短路徑。固固 定定 起起 點(diǎn)點(diǎn) 的的 最最 短短 路路最短路是一條路徑，且最短路的任一段也是最短路最短路是一條路徑，且最短路的任一段也是最短路 假設(shè)在假設(shè)在u0-v0的最短路中只取一條，則從的最短路中只取一條，則從u0到其到其余頂點(diǎn)的最短路將構(gòu)成一棵以余頂點(diǎn)的最短路將構(gòu)成一棵以u(píng)0為根的樹為根的樹 因此因此, 可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)可采用樹生長的過程來求指定頂點(diǎn)到其余頂點(diǎn)的最短路的最短路算法步驟：算法步驟： TO MATLAB(road1) 1 2 34 5 6 7 8返回返回uuuuuuuuDijkstra算法的算法的MATLAB實(shí)現(xiàn)：實(shí)現(xiàn)：w=0 2

12、 1 8 inf inf inf inf;2 0 inf 6 1 inf inf inf;1 inf 0 7 inf inf 9 inf;. 8 6 7 0 5 1 2 inf;inf 1 inf 5 0 3 inf 9;inf inf inf 1 3 0 4 6;. inf inf 9 2 inf 4 0 3;inf inf inf inf 9 6 3 0 n=size(w,1); w1=w(1,:); %賦初值賦初值 for i=1:n l(i)=w1(i); z(i)=1; end s=; s(1)=1; u=s(1); k=1； while kl(u)+w(u,i) l(i)=l(u)

13、+w(u,i); z(i)=u; end end end end l,z %求求v* ll=l; for i=1:n for j=1:k if i=s(j) ll(i)=ll(i); else ll(i)=inf; end end endlv=inf; for i=1:n if ll(i)lv lv=ll(i); v=i; end end lv, v s(k+1)=v k=k+1 u=s(k) endl,z每每 對(duì)對(duì) 頂頂 點(diǎn)點(diǎn) 之之 間間 的的 最最 短短 路路1求距離矩陣的方法求距離矩陣的方法2求路徑矩陣的方法求路徑矩陣的方法3查找最短路路徑的方法查找最短路路徑的方法（一）算法的基本思想（

14、一）算法的基本思想（三）算法步驟（三）算法步驟返回返回（二）算法原（二）算法原理理算法的基本思想算法的基本思想返回返回算法原理算法原理 求距離矩陣的方法求距離矩陣的方法返回返回算法原理算法原理 求路徑矩陣的方法求路徑矩陣的方法)()0()0(ijrR, jrij)0(在建立距離矩陣的同時(shí)可建立路徑矩陣在建立距離矩陣的同時(shí)可建立路徑矩陣R 即當(dāng)即當(dāng)k被插入任何兩點(diǎn)間的最被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在短路徑時(shí)，被記錄在R(k)中，依中，依次求次求 時(shí)求得時(shí)求得 ，可由，可由 來查來查找任何點(diǎn)對(duì)之間最短路的路徑找任何點(diǎn)對(duì)之間最短路的路徑)(D)(R返回返回)( Rvi j算法原理算法原理 查

15、找最短路路徑的方法查找最短路路徑的方法pkp2p1p3q1q2qm則由點(diǎn)則由點(diǎn)i到到j(luò)的最短路的路徑為：的最短路的路徑為：jqqqpppimk,21, 12返回返回算法步驟算法步驟 TOMATLAB(road2(floyd)5333434331543243332344441,0646960243420256420793570RD返回返回Folyd算法的算法的MATLAB實(shí)現(xiàn)：實(shí)現(xiàn)：functionD,R=floyd(a) n=size(a,1);D=afor i=1:n for j=1:n R(i,j)=j; endendfor k=1:n for i=1:n for j=1:n if D(i

16、,k)+D(k,j)D(i,j) D(i,j)=D(i,k)+D(k,j); R(i,j)=R(i,k); end end end k, D, Rend 在命令窗口中輸入：在命令窗口中輸入： a=0 9 inf 3 inf;9 0 2 inf 7;inf 2 0 2 4;3 inf 2 0 inf;inf 7 4 inf 0;floyd(a)最最 短短 路路 的的 應(yīng)應(yīng) 用用一、一、 可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題二、二、 選選 址址 問問 題題1 中心問題中心問題2 重心問題重心問題返回返回可化為最短路問題的多階段決策問題可化為最短路問題的多階段決策問題 例

17、例 1 設(shè)備更新問題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的.若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用.現(xiàn)要制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少. 已知該種設(shè)備在每年年初的價(jià)格為：第一年第二年第三年第四年第五年1111121213 使用不同時(shí)間設(shè)備所需維修費(fèi)為：使用年限0112233445維修費(fèi)5681118（3）問題轉(zhuǎn)化為頂點(diǎn)Xb1到Xrk6( )的最短路問題.五年的最優(yōu)購置費(fèi)為 kbrkd XX1 2 3 4 516, , , ,( )min (,)其中 d(Xb1,Xrk6( )為頂點(diǎn)Xb1到Xrk6

18、( )的最短路的權(quán).返回返回 選址問題選址問題-中心問題中心問題則kv就是要求的建立消防站的地點(diǎn)此點(diǎn)稱為圖的中中心心點(diǎn)點(diǎn) TO MATLAB(road3(floyd)05 .15 .55 .86475 .10475 .45 .25 .55 .54032475 .8730571065 .42502545 .24720375 .5710530DS(v1)=10, S(v2)=7, S(v3)=6, S(v4)=8.5, S(v5)=7, S(v6)=7, S(v7)=8.5S(v3)=6,故應(yīng)將消防站設(shè)在v3處. 返回返回 選址問題選址問題-重心問題重心問題返回返回實(shí)驗(yàn)作業(yè)實(shí)驗(yàn)作業(yè) 生產(chǎn)策略問題生產(chǎn)策略問題：現(xiàn)代化生產(chǎn)過程中，生產(chǎn)部門面臨的突出問題之一，便是