數(shù)學(xué)建模-第十章網(wǎng)絡(luò)規(guī)劃

1、 第十章第十章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 Combinatorial Optimization Theory第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 我們生活在一個(gè)網(wǎng)絡(luò)世界中，從某種意義上說現(xiàn)我們生活在一個(gè)網(wǎng)絡(luò)世界中，從某種意義上說現(xiàn)代社會(huì)是一個(gè)由計(jì)算機(jī)信息網(wǎng)絡(luò)、電話通訊網(wǎng)絡(luò)、運(yùn)代社會(huì)是一個(gè)由計(jì)算機(jī)信息網(wǎng)絡(luò)、電話通訊網(wǎng)絡(luò)、運(yùn)輸服務(wù)網(wǎng)絡(luò)、能源和物質(zhì)分派網(wǎng)絡(luò)等各種網(wǎng)絡(luò)所組成輸服務(wù)網(wǎng)絡(luò)、能源和物質(zhì)分派網(wǎng)絡(luò)等各種網(wǎng)絡(luò)所組成的復(fù)雜的網(wǎng)絡(luò)系統(tǒng)的復(fù)雜的網(wǎng)絡(luò)系統(tǒng). . 網(wǎng)絡(luò)規(guī)劃就是研究如何有效地計(jì)網(wǎng)絡(luò)規(guī)劃就是研究如何有效地計(jì)劃、管理和控制這個(gè)網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會(huì)劃、管理和控制這個(gè)網(wǎng)絡(luò)系統(tǒng)，使之發(fā)揮最大的社會(huì)和經(jīng)濟(jì)效益和

2、經(jīng)濟(jì)效益 . 由于圖的結(jié)構(gòu)的直觀性，運(yùn)用圖論的方法更有助由于圖的結(jié)構(gòu)的直觀性，運(yùn)用圖論的方法更有助于我們分析問題、描述問題、解決問題于我們分析問題、描述問題、解決問題 . 網(wǎng)絡(luò)規(guī)劃是運(yùn)籌學(xué)（組合優(yōu)化）的一個(gè)經(jīng)典又重網(wǎng)絡(luò)規(guī)劃是運(yùn)籌學(xué)（組合優(yōu)化）的一個(gè)經(jīng)典又重要分支，所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交要分支，所研究的問題涉及經(jīng)濟(jì)管理、工業(yè)工程、交通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等通運(yùn)輸、計(jì)算機(jī)科學(xué)與信息技術(shù)、通訊與網(wǎng)絡(luò)技術(shù)等諸多領(lǐng)域諸多領(lǐng)域 . .第十章第十章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃1 最小生成樹問題最小生成樹問題2 最短路問題最短路問題3 最大流問題最大流問題4 中國(guó)郵遞員問題中國(guó)郵遞

3、員問題0 圖的基本概念圖的基本概念第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Example 1七橋問題七橋問題 18世紀(jì)的德國(guó)有個(gè)哥尼斯堡城，在流貫全城的普世紀(jì)的德國(guó)有個(gè)哥尼斯堡城，在流貫全城的普雷爾河兩岸和河中兩個(gè)島之間架設(shè)了七座橋，把河的雷爾河兩岸和河中兩個(gè)島之間架設(shè)了七座橋，把河的兩岸和兩島連接起來，能否有這樣一種走法，它通過兩岸和兩島連接起來，能否有這樣一種走法，它通過每座橋一次且僅一次每座橋一次且僅一次 .該問題由該問題由Euler在在1736年解決年解決ABCD 則七橋問題就成為無向圖中是否存在通過每一邊則七橋問題就成為無向圖中是否存在通過每一邊一次且僅一次的路（即一筆畫）問題一次且僅一次的路

4、（即一筆畫）問題 . .Example 2人、狼、羊、菜渡河問題人、狼、羊、菜渡河問題 一一個(gè)擺渡人希望用一條小船把一只狼、一頭羊和個(gè)擺渡人希望用一條小船把一只狼、一頭羊和一籃白菜一籃白菜 從一條河的南岸渡到北岸去，而船小只能容從一條河的南岸渡到北岸去，而船小只能容納納人、狼、羊、菜人、狼、羊、菜中中的兩個(gè)，決不能在無人看守的情的兩個(gè)，決不能在無人看守的情況下，留下狼和羊在一起或羊和白菜在一起，應(yīng)怎樣況下，留下狼和羊在一起或羊和白菜在一起，應(yīng)怎樣渡河才能將狼、羊、白菜都運(yùn)過河？渡河才能將狼、羊、白菜都運(yùn)過河？狀態(tài)轉(zhuǎn)移問題狀態(tài)轉(zhuǎn)移問題人人 狼狼 羊羊 菜菜F W G C 考慮渡河過程中河南岸的變

5、化情況，最初的狀態(tài)考慮渡河過程中河南岸的變化情況，最初的狀態(tài)是人、狼、羊、菜，最終狀態(tài)成空狀態(tài)，中間的狀態(tài)是人、狼、羊、菜，最終狀態(tài)成空狀態(tài)，中間的狀態(tài)為人、狼、羊、菜的不同組合為人、狼、羊、菜的不同組合 .共有共有 16 種狀態(tài)種狀態(tài)，但有但有 6 種狀態(tài)是不允許的，如狼、羊、菜等種狀態(tài)是不允許的，如狼、羊、菜等.FWGCFWGOFWCFGCFGWCWGC 則渡河問題歸結(jié)為尋找從頂點(diǎn)則渡河問題歸結(jié)為尋找從頂點(diǎn) “FWGC” 到頂?shù)巾旤c(diǎn)點(diǎn)“O” 的路線的路線 . 第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Definition 圖：圖： 有序三元組有序三元組 G = ( V，E，R ) 稱為一個(gè)圖，其中稱為

6、一個(gè)圖，其中GraphVertexEdge V = v1，v2,，vn 是有窮非空集，稱為頂點(diǎn)集是有窮非空集，稱為頂點(diǎn)集； E 稱為邊集，其中的元素叫做邊；稱為邊集，其中的元素叫做邊； R 是從邊集是從邊集 E 到到 V 中的有序或無序的元素偶對(duì)應(yīng)中的有序或無序的元素偶對(duì)應(yīng) 的集合的映射，稱為關(guān)聯(lián)函數(shù)的集合的映射，稱為關(guān)聯(lián)函數(shù) . 關(guān)系關(guān)系Relation無向圖：無向圖：在圖在圖 G = (V，E) 中，中，圖簡(jiǎn)記為圖簡(jiǎn)記為G = （V，E）與與 V 中的無序偶對(duì)應(yīng)的邊中的無序偶對(duì)應(yīng)的邊 e , 稱稱為圖為圖 G 的無向邊，每條邊都是的無向邊，每條邊都是無向邊的圖，稱為無向邊的圖，稱為無向圖無

7、向圖 .v1v3v4v5v2e1e8e7e6e5e4e3e2 E 中任一條邊中任一條邊 e 若連接頂點(diǎn)若連接頂點(diǎn) u 和和 v ，則記為，則記為 e = (u，v), 并稱并稱 u 與與 v 為無向邊的兩個(gè)為無向邊的兩個(gè)端點(diǎn)端點(diǎn)；邊；邊 e 與與頂點(diǎn)頂點(diǎn) u 及及 v 關(guān)聯(lián)關(guān)聯(lián)，頂點(diǎn)，頂點(diǎn) u 與頂點(diǎn)與頂點(diǎn) v 相鄰相鄰 . 與同一個(gè)頂與同一個(gè)頂點(diǎn)關(guān)聯(lián)的若干條邊稱為是點(diǎn)關(guān)聯(lián)的若干條邊稱為是相鄰相鄰的的 .若若 e = ( vi , vj )簡(jiǎn)記為簡(jiǎn)記為 eij自環(huán)：自環(huán)： 兩個(gè)端點(diǎn)重合為一個(gè)頂點(diǎn)的邊兩個(gè)端點(diǎn)重合為一個(gè)頂點(diǎn)的邊；平行邊：平行邊： 關(guān)聯(lián)于同一對(duì)頂點(diǎn)的兩條邊關(guān)聯(lián)于同一對(duì)頂點(diǎn)的兩條邊；

8、沒有自環(huán)和平行邊的圖；沒有自環(huán)和平行邊的圖；簡(jiǎn)單圖：簡(jiǎn)單圖：完備圖：完備圖：任兩個(gè)頂點(diǎn)之間恰有一條邊相關(guān)聯(lián)任兩個(gè)頂點(diǎn)之間恰有一條邊相關(guān)聯(lián)；v1v3v4v2e1e5e6e2e4e3子圖：子圖： 設(shè)設(shè) G = (V, E)，G1 = (V1, E1) 都是圖，且都是圖，且V1 V, E1 E, 則稱圖則稱圖 G1 為圖為圖 G 的子圖；的子圖；v1v3v4v2e1e3e4e2e5e6v1v3v4v2e1e3e4e2e5e6Note : 是圖是圖第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃生成生成(支撐支撐)子圖：子圖： 若圖若圖 G1 是圖是圖 G 的子圖，且的子圖，且 V1 = V，則稱則稱 G1 是是 G

9、的生成子圖；的生成子圖；鏈（道路）：鏈（道路）： 圖圖 G 中一個(gè)由頂點(diǎn)和邊交錯(cuò)而成的非空中一個(gè)由頂點(diǎn)和邊交錯(cuò)而成的非空有限序列：有限序列：W = v0e1v1e2ekvk，ei E，i = 1,2,k，vj V，j =0,1,2,k, 且且 ei = (vi-1，vi), 則稱則稱 W 是是 G的一的一條鏈（道路）；條鏈（道路）； v0、vk 稱為稱為 W 的的起終點(diǎn)起終點(diǎn)，k為為路長(zhǎng)路長(zhǎng)；初等鏈：初等鏈： 各頂點(diǎn)相異的鏈；各頂點(diǎn)相異的鏈；回路：回路：起點(diǎn)與終點(diǎn)重合的鏈；起點(diǎn)與終點(diǎn)重合的鏈；圈：圈：起點(diǎn)與終點(diǎn)重合的初等鏈；起點(diǎn)與終點(diǎn)重合的初等鏈；連通圖：連通圖：圖圖 G 中任意兩點(diǎn)中任意兩點(diǎn)

10、 u 和和 v 存在一條鏈存在一條鏈；線度：線度：與頂點(diǎn)與頂點(diǎn) v 關(guān)聯(lián)的邊數(shù)關(guān)聯(lián)的邊數(shù)(環(huán)算兩次環(huán)算兩次)稱為稱為 v 的線度的線度;記為記為 d(v) .v1v3v4v5v2e1e8e7e6e5e4e3e2d(v2) = 3，d(v3) = 4割邊：割邊： 若去掉邊若去掉邊 e 將使連通圖將使連通圖 G 不再連通，則稱不再連通，則稱 e 為為 G 的割邊；的割邊；有向圖：有向圖： 在圖在圖 G = (V，E) 中，與中，與 V 中的有序偶對(duì)應(yīng)中的有序偶對(duì)應(yīng) 的邊的邊 e , 稱為圖稱為圖 G 的有向邊（?。?，每條邊都是的有向邊（?。?，每條邊都是 有向邊的圖，稱為有向邊的圖，稱為有向圖有向圖

11、 . 記為記為 G =(，)Arc對(duì)有向圖有類似無向圖的概念，如對(duì)有向圖有類似無向圖的概念，如 d+(vi)，d-(vi) .賦賦(加加)權(quán)圖權(quán)圖：圖圖 G 的每條邊的每條邊 e = (vi，vj) 與一實(shí)數(shù)與一實(shí)數(shù) w(e) = wij 對(duì)應(yīng)對(duì)應(yīng). w(e) = wij 稱為邊稱為邊 e 的權(quán)的權(quán) .割集割集：邊的集合，從連通圖：邊的集合，從連通圖 G 中移去這些邊，則中移去這些邊，則 G 不連通，且不存在這些邊的真子集使圖不連通不連通，且不存在這些邊的真子集使圖不連通 . 記為記為v1v3v4v5v2e1e8e7e6e5e4e3e2,S SS 為一個(gè)連通分支的頂點(diǎn)集為一個(gè)連通分支的頂點(diǎn)集.

12、 .圖的矩陣表示：圖的矩陣表示：第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃關(guān)聯(lián)矩陣：關(guān)聯(lián)矩陣： 對(duì)無向圖對(duì)無向圖 G = (V, E)，其中，其中 V = v1, ,vn , E = e1, e2,em . 構(gòu)造構(gòu)造 nm 矩陣矩陣 A =( aij ) nm 其中其中10ijijvea與 關(guān)聯(lián)否則12345678123451110000010000101001100110101100000001110eeeeeeeevvAvvv則稱矩陣則稱矩陣 A 是圖是圖 G 的關(guān)聯(lián)矩陣的關(guān)聯(lián)矩陣 .v1v3v4v5v2e1e8e7e6e5e4e3e2v5鄰接矩陣：鄰接矩陣： 對(duì)無向圖對(duì)無向圖 G = (V, E)，

13、其中，其中 V = v1, ,vn ,構(gòu)造構(gòu)造 nn 矩陣矩陣 B =( bij ) nn 其中其中1( ,)0ijijv vEb否則則稱矩陣則稱矩陣 B 是圖是圖 G 的鄰接矩陣的鄰接矩陣 .12345123450111010101110111010101110vvvvvvvBvvvv1v3v4v5v2e1e8e7e6e5e4e3e2對(duì)稱矩陣對(duì)稱矩陣對(duì)有向圖可類似定義關(guān)聯(lián)矩陣、鄰接矩陣對(duì)有向圖可類似定義關(guān)聯(lián)矩陣、鄰接矩陣 .Go back第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Definition 10.1 一個(gè)無圈且連通的無向圖一個(gè)無圈且連通的無向圖 G 稱為稱為樹樹 .不連通不連通,稱為稱為森林森

14、林樹通常記為樹通常記為 T .v1v3v4v5v2e1e5e4e3e2v5如如 群試問題群試問題( Group Testing ) 設(shè)有設(shè)有 25 枚硬幣，已知其中枚硬幣，已知其中一枚是假的且偏輕，問如何用一枚是假的且偏輕，問如何用天平稱最少的次數(shù)找到假幣？天平稱最少的次數(shù)找到假幣？結(jié)論結(jié)論：3 k 個(gè)硬幣，只需稱個(gè)硬幣，只需稱 k 次即可次即可 .不知道假硬幣是偏輕還是偏重，如何？不知道假硬幣是偏輕還是偏重，如何？ 如如 12 枚枚一、樹、生成樹一、樹、生成樹關(guān)于樹有以下性質(zhì)：關(guān)于樹有以下性質(zhì)：v1v3v4v5v2e1e5e4e3e2v53、在樹在樹 T 中，任意兩頂點(diǎn)間有且僅有一條道路中，

15、任意兩頂點(diǎn)間有且僅有一條道路；1、在樹在樹 T 中，任意兩個(gè)不相鄰中，任意兩個(gè)不相鄰 頂點(diǎn)加上一條邊，則恰好得到頂點(diǎn)加上一條邊，則恰好得到 一個(gè)圈；一個(gè)圈；2、在樹在樹 T 中，去掉任意一條邊中，去掉任意一條邊, 則樹為不連通的；則樹為不連通的；4、在樹、在樹 T 中，頂點(diǎn)數(shù)比邊數(shù)多中，頂點(diǎn)數(shù)比邊數(shù)多 1 . 如果樹如果樹 T 是圖是圖 G 的生成的生成 子圖，則稱子圖，則稱 T 是是 G 的一棵生成（支撐）樹的一棵生成（支撐）樹 .Definition 10.2第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Note:圖圖 G 的生成樹一般不是唯一的的生成樹一般不是唯一的 .v1v3v2v4v1v3v2v4v

16、1v3v2v4v1v3v2v4v1v3v2v4v1v3v2v4 共有多少？共有多少？16 棵棵Example 3 擬建造一個(gè)連接若干城鎮(zhèn)的通訊網(wǎng)絡(luò)，擬建造一個(gè)連接若干城鎮(zhèn)的通訊網(wǎng)絡(luò)，已知城鎮(zhèn)已知城鎮(zhèn) vi，vj 之間直接拉線的造價(jià)為之間直接拉線的造價(jià)為 cij ，試設(shè)計(jì)一，試設(shè)計(jì)一個(gè)總造價(jià)最小的通訊網(wǎng)絡(luò)個(gè)總造價(jià)最小的通訊網(wǎng)絡(luò) .如如 7 個(gè)城鎮(zhèn)個(gè)城鎮(zhèn)：v3v2v7v6v4v5v1112223344567 顯然，該通訊網(wǎng)絡(luò)必須包顯然，該通訊網(wǎng)絡(luò)必須包含所有頂點(diǎn)，連通、無圈，且含所有頂點(diǎn)，連通、無圈，且權(quán)和最小權(quán)和最小.生成子圖生成子圖生成樹生成樹最小生成樹最小生成樹Definition 10.3

17、二、最小生成樹二、最小生成樹 若若 T 為為 G 的生成樹，的生成樹，T 中中的邊的邊 e 記為記為 eT，則，則T 的權(quán)的權(quán) ( )( )e Tw Tw e若若 T *為為 G 的生成樹，且有的生成樹，且有( *)min( )w Tw T TG為 的生成樹則稱則稱T *為為 G 的最小生成樹的最小生成樹.第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Theorem 10.1 若若 T * 是圖是圖 G 的生成樹，則它是最小生的生成樹，則它是最小生成樹的充要條件是對(duì)成樹的充要條件是對(duì) T * 外外 G 的每一條邊的每一條邊 加入加入 T * 中中后形成的圈中，該邊權(quán)最大后形成的圈中，該邊權(quán)最大 .Proof

18、Theorem 10.2 若若 T * 是圖是圖 G 的生成樹，則它是最小生的生成樹，則它是最小生成樹的充要條件是對(duì)成樹的充要條件是對(duì) T * 中的任何一條邊中的任何一條邊, 將該邊從將該邊從T *中刪去后形成的割集中，該邊權(quán)最小中刪去后形成的割集中，該邊權(quán)最小 .證略證略v1v3v4v5v228641233圈圈最優(yōu)條件最優(yōu)條件割割最優(yōu)條件最優(yōu)條件Theorem 10.1 的證明的證明Proof :反證法反證法設(shè)設(shè) T * 是最小生成樹，對(duì)是最小生成樹，對(duì)T * 外外G 的任一條邊的任一條邊 e ，加入，加入 T *中后形成的圈中，如果該邊中后形成的圈中，如果該邊的權(quán)不是最大，設(shè)最大邊為的權(quán)不

19、是最大，設(shè)最大邊為 e*. 此時(shí)，此時(shí)，T *+ e e* 也是也是生成樹，但它的權(quán)比生成樹，但它的權(quán)比 T *更小，這與更小，這與 T * 是最小生成樹是最小生成樹矛盾矛盾 . 設(shè)設(shè) T * 是生成樹并滿足定理?xiàng)l件，但不是最小的是生成樹并滿足定理?xiàng)l件，但不是最小的.設(shè)最小生成樹為設(shè)最小生成樹為 T0，則則 T * 中至少有一條邊中至少有一條邊 (i, j) T0,將將 (i, j) 加入加入 T0 后必產(chǎn)生一個(gè)圈，且圈上至少有一條邊后必產(chǎn)生一個(gè)圈，且圈上至少有一條邊 (k, l) T * , 由定理?xiàng)l件由定理?xiàng)l件 wijwkl , 又又T0為最小生成樹為最小生成樹,所以所以, wijwkl

20、, 于是于是 wij = wkl . 因此因此, T0 + (i, j) (k, l) 也也是最小生成樹，并與是最小生成樹，并與T *有更多的公共邊，重復(fù)該過程有更多的公共邊，重復(fù)該過程,最后，可以將最后，可以將 T0變?yōu)樽優(yōu)門 *，因此，因此，T * 是最小生成樹是最小生成樹.三、求最小生成樹的算法三、求最小生成樹的算法 求最小生成樹的方法很多且很簡(jiǎn)單，理論基礎(chǔ)主要求最小生成樹的方法很多且很簡(jiǎn)單，理論基礎(chǔ)主要是定理是定理 10.1（圈最優(yōu)條件）、定理（圈最優(yōu)條件）、定理 10.2（割最優(yōu)條件）（割最優(yōu)條件）.A、 避圈法避圈法 1、Kruskal 算法（逐邊生成）算法（逐邊生成） 2、Pri

21、m 算法算法 （逐點(diǎn)生成）（逐點(diǎn)生成）B、 破圈法破圈法 1、Kruskal 算法算法 （1956年）年）Step 0 把把 G 的邊按權(quán)由小到大的順序排列，即的邊按權(quán)由小到大的順序排列，即w(e1) w(em) ; 令令 i = 1，j = 0，T = . Step 1 判斷判斷 Tei 是否含圈是否含圈, Y 轉(zhuǎn)轉(zhuǎn)Step 2, N 轉(zhuǎn)轉(zhuǎn)Step 3 .Step 2 令令 i = i+1. 若若 im 轉(zhuǎn)轉(zhuǎn) Step 1; 否則結(jié)束，此時(shí)否則結(jié)束，此時(shí) G 不連通，所以沒有最小生成樹不連通，所以沒有最小生成樹 .Step 3令令 T = Tei ，j = j+1 . 若若 j = n-1，

22、結(jié)束，結(jié)束，T 是最是最小生成樹；否則，轉(zhuǎn)小生成樹；否則，轉(zhuǎn) Strp 2 .第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Example 4v3v2v7v6v4v5v1112223344567用用 Kruskal 算法求算法求右圖的最小生成樹右圖的最小生成樹 .Solution: 首先，對(duì)所有邊按權(quán)首先，對(duì)所有邊按權(quán)由小到大順序排列由小到大順序排列：(2, 7)，(2, 3) .(1, 7)，(4, 5)，(5, 7)，(1, 6)，(4, 7)，(1, 2)，(3, 7)，(3, 4)(6, 7)，(5, 6)然后，按順序?qū)⑦@些邊加入然后，按順序?qū)⑦@些邊加入 T 中，中，如圖，得到最小生成樹如圖，得到最小

23、生成樹 T *，w(T *) = 14如何判斷如何判斷Tei 含圈？含圈？通過增加一個(gè)標(biāo)號(hào)通過增加一個(gè)標(biāo)號(hào) 給每個(gè)頂點(diǎn)一個(gè)互不相同的標(biāo)號(hào)，不妨為頂點(diǎn)的下標(biāo)給每個(gè)頂點(diǎn)一個(gè)互不相同的標(biāo)號(hào)，不妨為頂點(diǎn)的下標(biāo). 當(dāng)加入一條邊時(shí)當(dāng)加入一條邊時(shí), ,判斷兩個(gè)頂點(diǎn)的標(biāo)號(hào)判斷兩個(gè)頂點(diǎn)的標(biāo)號(hào), ,若相同若相同, ,則產(chǎn)生圈；否則產(chǎn)生圈；否則，將與標(biāo)號(hào)大的相同的標(biāo)號(hào)均改為與標(biāo)號(hào)小的相同的標(biāo)號(hào)則，將與標(biāo)號(hào)大的相同的標(biāo)號(hào)均改為與標(biāo)號(hào)小的相同的標(biāo)號(hào). .32764511122233445676 55 在算法進(jìn)行過程中，在算法進(jìn)行過程中，T 始終不含圈始終不含圈. 因此算法結(jié)束因此算法結(jié)束時(shí)，若時(shí)，若 T 含含 n-1

24、條邊，則條邊，則 T 為生成樹；否則，原圖不為生成樹；否則，原圖不連通，不存在生成樹連通，不存在生成樹 . 由于邊已按權(quán)由小到大排序，而不加入由于邊已按權(quán)由小到大排序，而不加入 T 的邊，的邊，必為產(chǎn)生圈中的最大權(quán)邊，由定理必為產(chǎn)生圈中的最大權(quán)邊，由定理 10.1 知，知， T 為生成為生成樹則必為最小生成樹樹則必為最小生成樹 . 這說明這說明Kruskal 算法的正確性算法的正確性 . 該算法始終試圖把權(quán)盡可能小的邊加到該算法始終試圖把權(quán)盡可能小的邊加到 T 中，僅中，僅當(dāng)加入后使當(dāng)加入后使 T 不是樹才放棄，對(duì)邊的選取，不必瞻前不是樹才放棄，對(duì)邊的選取，不必瞻前顧后，只看眼前利益顧后，只看

25、眼前利益 . 這就是簡(jiǎn)單且重要的這就是簡(jiǎn)單且重要的貪婪算法貪婪算法（Greedy）.第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃2、Prim 算法算法 （1957年）年）Step 0Step 1Step 2令令 S = Sv2，E0 = E0 e*,轉(zhuǎn)轉(zhuǎn) Strp 1 .設(shè)設(shè) v 為為 G 的任一頂點(diǎn)，令的任一頂點(diǎn)，令 S = v，E0 = ,S S , ( *)min( )eS Sw ew e若若 S = V，結(jié)束，結(jié)束，T = (S , E0) 為最小生成樹；為最小生成樹；否則否則 轉(zhuǎn)轉(zhuǎn) Step 2 .1212*( ,),.ev vvS vS若若 ，則，則 G 不連通，結(jié)束；不連通，結(jié)束； 否則，設(shè)否

26、則，設(shè) , 其中其中 v3v2v7v6v4v5v1112223344567Prim 算法的正確性由定理算法的正確性由定理10.2 不難得到不難得到.3、破圈法破圈法 （1967年）年）v3v2v7v6v4v5v1112223344567四、應(yīng)用舉例四、應(yīng)用舉例 最小生成樹的理論和計(jì)算，最小生成樹的理論和計(jì)算，在很多工程或技術(shù)領(lǐng)域中得到應(yīng)用在很多工程或技術(shù)領(lǐng)域中得到應(yīng)用 . 如要在若干城市之間架設(shè)通訊線路、鋪設(shè)公路鐵路或如要在若干城市之間架設(shè)通訊線路、鋪設(shè)公路鐵路或各種管道，要求總的線路長(zhǎng)度最短，材料最省，成本各種管道，要求總的線路長(zhǎng)度最短，材料最省，成本最低等最低等. 在實(shí)際的應(yīng)用中，又提出了

27、最小生成樹問題的各在實(shí)際的應(yīng)用中，又提出了最小生成樹問題的各種推廣，其中較典型的問題多是在可行解的結(jié)構(gòu)上增種推廣，其中較典型的問題多是在可行解的結(jié)構(gòu)上增加一些約束加一些約束 .第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃1、最大生成樹問題最大生成樹問題v3v2v7v6v4v5v1112223344567在最小生成樹上，在最小生成樹上，v1至至v4路的特點(diǎn)路的特點(diǎn)Example 5 設(shè)某工廠運(yùn)輸一很重的設(shè)備，需由設(shè)備庫(kù)設(shè)某工廠運(yùn)輸一很重的設(shè)備，需由設(shè)備庫(kù) v1 運(yùn)至施工現(xiàn)場(chǎng)運(yùn)至施工現(xiàn)場(chǎng) v4，中間需經(jīng)過一些橋梁（如圖），中間需經(jīng)過一些橋梁（如圖），已知這些橋梁的堅(jiān)固程度不同，經(jīng)專家測(cè)定其安全系已知這些橋梁的堅(jiān)

28、固程度不同，經(jīng)專家測(cè)定其安全系數(shù)如示，試問應(yīng)如何安排運(yùn)輸路線最安全？數(shù)如示，試問應(yīng)如何安排運(yùn)輸路線最安全？最大值最小最大值最小v6v5v4施工現(xiàn)場(chǎng)施工現(xiàn)場(chǎng)v3v2v1設(shè)備庫(kù)設(shè)備庫(kù)Solution:v6v5v4v3v1v 最大生成樹上的路是最小者最大最大生成樹上的路是最小者最大.先求得最大生成樹，如圖先求得最大生成樹，如圖所以，所以，v1至至v4的最安全的路線為的最安全的路線為 v1 v6 v5 v3 v4最不安全處最安全最不安全處最安全最不安全處系數(shù)為最不安全處系數(shù)為 0.42、容量約

29、束最小生成樹問題容量約束最小生成樹問題 在遠(yuǎn)程信息處理網(wǎng)絡(luò)的設(shè)計(jì)中涉及這樣的問題：在遠(yuǎn)程信息處理網(wǎng)絡(luò)的設(shè)計(jì)中涉及這樣的問題：已給一個(gè)無向圖已給一個(gè)無向圖 G = (V，E) , 每條邊每條邊 (vi , vj) 具有費(fèi)用具有費(fèi)用 w (vi , vj) 以及容量以及容量 c (vi , vj) ，一個(gè)頂點(diǎn)為信息接收站，一個(gè)頂點(diǎn)為信息接收站. 尋求一個(gè)生成樹，使所有信息沿樹的邊送到接收尋求一個(gè)生成樹，使所有信息沿樹的邊送到接收站，滿足容量約束，即每邊上所傳的信息量不超過容站，滿足容量約束，即每邊上所傳的信息量不超過容量費(fèi)用最且小量費(fèi)用最且小 . 稱為容量約束的最小生成樹問題，是稱為容量約束的最小

30、生成樹問題，是 NP-C問題問題.第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃3、度數(shù)約束最小生成樹問題度數(shù)約束最小生成樹問題 生成樹在計(jì)算機(jī)和通訊網(wǎng)絡(luò)中有許多應(yīng)用，其中生成樹在計(jì)算機(jī)和通訊網(wǎng)絡(luò)中有許多應(yīng)用，其中的大多數(shù)問題對(duì)某些頂點(diǎn)的度數(shù)有限制的大多數(shù)問題對(duì)某些頂點(diǎn)的度數(shù)有限制 . 如一個(gè)頂點(diǎn)如一個(gè)頂點(diǎn)代表一個(gè)中央計(jì)算設(shè)備，其他頂點(diǎn)代表終端，它們必代表一個(gè)中央計(jì)算設(shè)備，其他頂點(diǎn)代表終端，它們必須靠電纜與中央設(shè)備連接，若現(xiàn)在中央機(jī)的度數(shù)為須靠電纜與中央設(shè)備連接，若現(xiàn)在中央機(jī)的度數(shù)為 b ,這可保證計(jì)算機(jī)的負(fù)荷分散在這可保證計(jì)算機(jī)的負(fù)荷分散在 b 個(gè)端口，求中央機(jī)度個(gè)端口，求中央機(jī)度數(shù)為數(shù)為 b 的最小生成樹

31、，使所用電纜盡可能少的最小生成樹，使所用電纜盡可能少 . 若只有一個(gè)頂點(diǎn)受約束，是一個(gè)若只有一個(gè)頂點(diǎn)受約束，是一個(gè) P 問題問題 .1、Steiner 樹樹（在歐氏距離下）（在歐氏距離下）補(bǔ)充：補(bǔ)充：Example 6 假設(shè)電話剛發(fā)明，郵電部的第一個(gè)任務(wù)假設(shè)電話剛發(fā)明，郵電部的第一個(gè)任務(wù)是要使北京、上海、蘭州三個(gè)城市間有線路相通是要使北京、上海、蘭州三個(gè)城市間有線路相通 . 你你是總工程師，如何設(shè)計(jì)路線呢？是總工程師，如何設(shè)計(jì)路線呢？ 當(dāng)然線路越短越好，由最小生成樹：當(dāng)然線路越短越好，由最小生成樹：北京北京蘭州、蘭州、北京北京上海上海 為最佳為最佳 .北京北京蘭州蘭州上海上海真的沒辦法更短了嗎

32、？真的沒辦法更短了嗎？鄭州鄭州 但你的發(fā)現(xiàn)并沒有使舉世的科學(xué)家震動(dòng)，因?yàn)檫@一但你的發(fā)現(xiàn)并沒有使舉世的科學(xué)家震動(dòng)，因?yàn)檫@一事實(shí)早已被無數(shù)的數(shù)學(xué)書籍記載，這就是事實(shí)早已被無數(shù)的數(shù)學(xué)書籍記載，這就是 Steiner 樹樹 . 你發(fā)現(xiàn)：你發(fā)現(xiàn)：北京北京鄭州、上海鄭州、上海鄭州、蘭州鄭州、蘭州鄭州鄭州 也滿足也滿足要求且總長(zhǎng)度比最小生成樹更短要求且總長(zhǎng)度比最小生成樹更短 . 通過增加一些點(diǎn)（通過增加一些點(diǎn)（Steiner 點(diǎn)）使保存原來的所有點(diǎn)）使保存原來的所有點(diǎn)且連通，而總長(zhǎng)度最短點(diǎn)且連通，而總長(zhǎng)度最短 .第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃v4v3v2v1如右圖：最小生成樹如右圖：最小生成樹 z min

33、= 31111但加上但加上 v5，則，則 z min = 2 = 2.8282問題：?jiǎn)栴}：1、對(duì)于怎樣放置的對(duì)于怎樣放置的 n 個(gè)點(diǎn)，需要引進(jìn)個(gè)點(diǎn)，需要引進(jìn) S 點(diǎn)；點(diǎn)；v1v3v2如：如：是不需要加點(diǎn)的是不需要加點(diǎn)的. .2、如何確定如何確定 S 點(diǎn)的位置點(diǎn)的位置；3、引進(jìn)幾個(gè)引進(jìn)幾個(gè) S 點(diǎn)最佳點(diǎn)最佳 .n = 1、2 是平凡的是平凡的 . n = 3 已解決，一般是已解決，一般是 NP-C 的的 .Theorem 10.3 設(shè)有設(shè)有 A、B、C 三點(diǎn)，若三點(diǎn)，若ABC 的任一的任一內(nèi)角都小于內(nèi)角都小于 120o ，則必存在內(nèi)部一點(diǎn)，則必存在內(nèi)部一點(diǎn) P 使使 PA、PB、PC 的兩兩夾角

34、均是的兩兩夾角均是 120o ，且此時(shí)，且此時(shí) PA + PB + PC ABC 的任兩邊之和的任兩邊之和 . 不可能有另一點(diǎn)不可能有另一點(diǎn) D 比比 P 的效果的效果更好更好 .v5而當(dāng)而當(dāng)A 120o 則則 z min = AB+ACTheorem 10.4三個(gè)點(diǎn)時(shí)，如何確定三個(gè)點(diǎn)時(shí)，如何確定S - -點(diǎn)位置點(diǎn)位置ABCS120o120oD 能否再加點(diǎn)，能否再加點(diǎn)， 使之更短呢？使之更短呢？ 對(duì)于對(duì)于 n 個(gè)點(diǎn)個(gè)點(diǎn)的網(wǎng)絡(luò)，至多可加入的網(wǎng)絡(luò)，至多可加入 n 2 個(gè)個(gè) Steiner 點(diǎn)點(diǎn) .v4v3v2v11111v5最小生成樹最小生成樹 z min = 3但加上但加上 v5，則，則 z m

35、in = 2 = 2.8282120o120o此時(shí)此時(shí)， z min = 1+ = 2.7323問：?jiǎn)枺篠teiner 樹能使總樹能使總長(zhǎng)度比最小生成樹減少長(zhǎng)度比最小生成樹減少的最大比例是多少？的最大比例是多少？ 1968年兩位美國(guó)數(shù)學(xué)家提出該比例為年兩位美國(guó)數(shù)學(xué)家提出該比例為 13.4% 的猜想，上世紀(jì)的猜想，上世紀(jì)90年代初，被中國(guó)年代初，被中國(guó)青年數(shù)學(xué)家堵丁柱解決，且方法很有價(jià)值青年數(shù)學(xué)家堵丁柱解決，且方法很有價(jià)值.第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃2、擬陣擬陣 （Matroid）問：怎樣的結(jié)構(gòu)的組合問：怎樣的結(jié)構(gòu)的組合優(yōu)化問題可用優(yōu)化問題可用 Greedy 算法得到最優(yōu)解？算法得到最優(yōu)解？

36、Definition 10.4 子集系統(tǒng)子集系統(tǒng) S = (E , l) 是由有限集是由有限集 E 及及 E 的一個(gè)子集族的一個(gè)子集族 l 組成，在集合的包含關(guān)系下，組成，在集合的包含關(guān)系下， l 是封是封閉的閉的. l 中的成員，稱為獨(dú)立集中的成員，稱為獨(dú)立集 .即若即若,AlAAAl則參照參照：E 為圖為圖 G 的邊的集合，的邊的集合，l 是是E 的無圈子集的無圈子集. 關(guān)于子集系統(tǒng)關(guān)于子集系統(tǒng) S = (E , l) 的組合優(yōu)化問題是對(duì)每一的組合優(yōu)化問題是對(duì)每一個(gè)個(gè) e E 給定一個(gè)權(quán)給定一個(gè)權(quán) w(e) 0 ，求一個(gè)最大獨(dú)立集，求一個(gè)最大獨(dú)立集，使其權(quán)和最大（小）使其權(quán)和最大（?。?D

37、efinition 10.5 設(shè)設(shè) S = (E , l) 是一子集系統(tǒng)，如果對(duì)是一子集系統(tǒng)，如果對(duì) S的任意兩個(gè)極大獨(dú)立集的任意兩個(gè)極大獨(dú)立集 則稱則稱 S 是擬陣是擬陣.,A AAA有顯然，對(duì)顯然，對(duì)G = (E , V) , S = (E , l) , l 是無圈子圖，則是無圈子圖，則 S 是擬陣是擬陣 .Theorem 10.5 S 是擬陣，則關(guān)于是擬陣，則關(guān)于 S 的組合優(yōu)化問題的組合優(yōu)化問題中每個(gè)例子，都可用中每個(gè)例子，都可用 Greedy 算法得到最優(yōu)解算法得到最優(yōu)解 . 婚姻問題婚姻問題 (matching ) 可以看成一個(gè)子集系統(tǒng)可以看成一個(gè)子集系統(tǒng) S = ( E , l)

38、 , l 所有匹配，但不是擬陣所有匹配，但不是擬陣.x3x1x2y2y1y3我們還學(xué)過其他我們還學(xué)過其他擬陣結(jié)構(gòu)嗎？擬陣結(jié)構(gòu)嗎？ S = ( E , l) , E 一組向量一組向量 l 所有線性無關(guān)子所有線性無關(guān)子集，它是擬陣集，它是擬陣. 因?yàn)榫€性無關(guān)組的子集因?yàn)榫€性無關(guān)組的子集仍線性無關(guān)；極大線性無關(guān)仍線性無關(guān)；極大線性無關(guān)組的所含向量個(gè)數(shù)相同組的所含向量個(gè)數(shù)相同 . . 則對(duì)每個(gè)向量加權(quán)，要求一個(gè)極大則對(duì)每個(gè)向量加權(quán)，要求一個(gè)極大線性無關(guān)組，使其權(quán)和最大（?。?，可線性無關(guān)組，使其權(quán)和最大（?。?，可用用 Greedy 算法算法.Go back第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 最短路問題是網(wǎng)絡(luò)

39、優(yōu)化中的一個(gè)相對(duì)基本而又非最短路問題是網(wǎng)絡(luò)優(yōu)化中的一個(gè)相對(duì)基本而又非常重要的課題常重要的課題. . 許多網(wǎng)絡(luò)優(yōu)化問題或者可以化為最短許多網(wǎng)絡(luò)優(yōu)化問題或者可以化為最短路問題，或者可用最短路的算法作為其子程序路問題，或者可用最短路的算法作為其子程序. . 如：如：通訊網(wǎng)絡(luò)中的最可靠路問題、物資的運(yùn)輸路線、各種通訊網(wǎng)絡(luò)中的最可靠路問題、物資的運(yùn)輸路線、各種工藝路線的安排、廠區(qū)及貨場(chǎng)的布局、管道線網(wǎng)的鋪工藝路線的安排、廠區(qū)及貨場(chǎng)的布局、管道線網(wǎng)的鋪設(shè)以及設(shè)備的更新等問題都可化為最短路問題；而網(wǎng)設(shè)以及設(shè)備的更新等問題都可化為最短路問題；而網(wǎng)絡(luò)流問題和中國(guó)郵遞員問題都要用最短路算法作為子絡(luò)流問題和中國(guó)郵遞

40、員問題都要用最短路算法作為子程序程序 . . 設(shè)有向網(wǎng)絡(luò)設(shè)有向網(wǎng)絡(luò) D = (V , A , w)，其中弧，其中弧 ( vi , vj) A對(duì)對(duì)應(yīng)的權(quán)應(yīng)的權(quán) wij 又稱為弧長(zhǎng)或費(fèi)用，對(duì)于其中的兩個(gè)頂點(diǎn)又稱為弧長(zhǎng)或費(fèi)用，對(duì)于其中的兩個(gè)頂點(diǎn) v1、vt V, 以以v1為起點(diǎn)為起點(diǎn) vt 為終點(diǎn)的有向路稱為為終點(diǎn)的有向路稱為 v1 vt 有向路有向路 P , 其所經(jīng)過的所有弧上的權(quán)之和為該有向路的其所經(jīng)過的所有弧上的權(quán)之和為該有向路的權(quán)權(quán) (,)( )ijijv vPw Pw 所有所有 v1 vt 有向路中權(quán)和最小的一條稱為有向路中權(quán)和最小的一條稱為 v1 vt 最短路最短路 P*.求最短路的方法

41、的基本思想很樸素求最短路的方法的基本思想很樸素： 設(shè)設(shè) v1 vl 的最短路是的最短路是 v1 vi vk vl , 則則 v1 vk 的最短路是的最短路是 v1 vi vk 第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Example 7 利用前述思想求如利用前述思想求如下網(wǎng)絡(luò)中，下網(wǎng)絡(luò)中，v1 至至 v4 的的最短路最短路 .Solution:v1v2v3v4v5v6362423311從從 v1 逐步向外生長(zhǎng)逐步向外生長(zhǎng) 目前目前 v1 可達(dá)可達(dá) v2、v3 路長(zhǎng)分路長(zhǎng)分別為別為6、3，這時(shí)求得了這時(shí)求得了v1至至 v3 的最短路，長(zhǎng)度為的最短路，長(zhǎng)度為 3 .v1不可能通過其他頂不可能通過其他頂點(diǎn)到達(dá)點(diǎn)

42、到達(dá)v3 距離更短，距離更短，因?yàn)橐驗(yàn)?wij 0 再求再求 v1或通過或通過 v3 可達(dá)的所有路的最短距離，可達(dá)的所有路的最短距離，v1 v2;v1 v3 v2; v1 v3 v4 路長(zhǎng)分別為路長(zhǎng)分別為6、5、7. 這時(shí)求這時(shí)求得了得了 v1 至至v2的最短路，路長(zhǎng)為的最短路，路長(zhǎng)為 5 . 再求再求 v1 v3 v2 v4; v1 v3 v2 v5; v1 v3 v4 路長(zhǎng)分別為路長(zhǎng)分別為 7、6、7. 這時(shí)得這時(shí)得 v1 至至v2的最短路的最短路, 路長(zhǎng)為路長(zhǎng)為 5 .這時(shí)求得這時(shí)求得 v1至至v4 的最短路的最短路 ，路長(zhǎng)為，路長(zhǎng)為 6 . 介紹了基本思想和方法，但有兩個(gè)需彌補(bǔ)的地方：

43、介紹了基本思想和方法，但有兩個(gè)需彌補(bǔ)的地方：1、計(jì)算量大、計(jì)算量大 O(n3);2、如何記錄最短路的走法、如何記錄最短路的走法 .一、正費(fèi)用網(wǎng)絡(luò)一、正費(fèi)用網(wǎng)絡(luò)(wij0) 1959年，年，Dijkstra 提出通過提出通過標(biāo)號(hào)標(biāo)號(hào)解決了上述問題解決了上述問題 .這是網(wǎng)絡(luò)規(guī)劃中這是網(wǎng)絡(luò)規(guī)劃中常用手段常用手段該算法是目前公認(rèn)的求正費(fèi)用網(wǎng)絡(luò)最短路的較好的算法該算法是目前公認(rèn)的求正費(fèi)用網(wǎng)絡(luò)最短路的較好的算法之一之一 . 基本如前（逐點(diǎn)生成），但在執(zhí)行過程中，對(duì)未基本如前（逐點(diǎn)生成），但在執(zhí)行過程中，對(duì)未達(dá)到最短路的頂點(diǎn)，記錄目前達(dá)到最短路的頂點(diǎn)，記錄目前 v1 至該點(diǎn)的最短路長(zhǎng)度至該點(diǎn)的最短路長(zhǎng)度.一

44、旦有新的頂點(diǎn)被確定已達(dá)最短，則下一步其余（對(duì)未一旦有新的頂點(diǎn)被確定已達(dá)最短，則下一步其余（對(duì)未達(dá)到最短路的頂點(diǎn)）的頂點(diǎn)只需與它比較，來確定新的達(dá)到最短路的頂點(diǎn)）的頂點(diǎn)只需與它比較，來確定新的目前目前 v1至這些點(diǎn)的最短路長(zhǎng)度至這些點(diǎn)的最短路長(zhǎng)度 .ui 表示表示 v1 至至vi 的最短路長(zhǎng)度；（是永久性的）的最短路長(zhǎng)度；（是永久性的）t(vi)表示目前表示目前 v1 至至vi 的最短路長(zhǎng)度；（是臨時(shí)性的）的最短路長(zhǎng)度；（是臨時(shí)性的）l(vi)表示表示v1 至至vi 的目前最短路上的目前最短路上 vi 的前一個(gè)頂點(diǎn)的下標(biāo)的前一個(gè)頂點(diǎn)的下標(biāo)如：如：l(vi) = j 即即 v1 vj vi第十第十

45、章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃Dijkstr 算法算法（求（求v1至個(gè)頂點(diǎn)或至至個(gè)頂點(diǎn)或至vh 的最短路）的最短路）Step 0令令 i = 1 , Si =v1 , u1 = 0 , l(v1) = 0 , 對(duì)每個(gè)對(duì)每個(gè) jivS()jivS11()min()ijiijijvStvtv令令 t1(vj) = M , l1(vj) = M (M 為充分大的正數(shù)為充分大的正數(shù))，k = 1Step 1如果如果 Si = V (或或 k = h 即即 v1至至vh的最短路的最短路) 結(jié)束結(jié)束否則否則 , 轉(zhuǎn)轉(zhuǎn) Step 2Step 2 對(duì)每條從對(duì)每條從 vk 出發(fā)的弧出發(fā)的弧 (vk , vj) A ,

46、ti+1(vj) = min ti(vj) , uk + wkj 若若 ti+1(vj) = ti(vj) ，則，則 li+1(vj) = li(vj) , 否則否則 li+1(vj) = kStep 3令令如果如果 ti+1(vji) M則則 11()()()iiiijijjijutvl vlv令令 Si+1 = Si vji , k = ji , i = i+1 轉(zhuǎn)轉(zhuǎn) Step 2 否則否則 結(jié)束結(jié)束. 當(dāng)算法結(jié)束時(shí)，如果當(dāng)算法結(jié)束時(shí)，如果 vj Si , 則則 v1 可達(dá)可達(dá) vj , uj 表表示示 v1至至vj 的最短路的長(zhǎng)度，且通過的最短路的長(zhǎng)度，且通過 l(vj)，可得其最短，可

47、得其最短路路 . 如果如果 , 則則vi至至vj 不存在路不存在路 .jivSExample 8 用用 Dijkstra 算法求如下網(wǎng)絡(luò)中，算法求如下網(wǎng)絡(luò)中，v1 至各頂至各頂點(diǎn)的最短路點(diǎn)的最短路 .v1v2v3v4v5v61624253117Solution:i = 1 , 令令 S1 = v1u1 = 0 , l(v1) = 0 , t1(v2) = t1(v3) = t1(v4) = t1(v5) = t1(v6) = Ml1(v2) = l1(v3) = l1(v4) = l1(v5) = l1(v6) = Mk = 1t2(v2) = min M , u1 +6 = 6 l2(v2)

48、 = 1t2(v3) = min M , u1 +3 = 3 l2(v3) = 1t2(v4) = min M , u1 + M = M l2(v4) = Mt2(v5) , t2(v6) 均不變均不變 .所以，所以， 則則 u2 = t2(v3) = 3 , l(v3) = 1 , S = v1 , v31232()min ()jjvSt vt vk = 2 , i = 2 Go on過程可由如下表格給出，打過程可由如下表格給出，打“*”者為者為 uj . v1v2v3v4v5v6 10* 0M MM MM MM MM M 26 13* 1M MM MM M 36 14* 3M M10 3

49、45* 46 49 4 56* 49 4 67* 5ti(vj) li(vj)ivj第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃二、一般費(fèi)用網(wǎng)絡(luò)二、一般費(fèi)用網(wǎng)絡(luò) 對(duì)于對(duì)于 wij0 的情形，的情形，Dijkstra 算法是行不通的算法是行不通的 . 如圖如圖:v1v2v3-221v1v2v3-22-1 在沒有負(fù)圈的情況下，在沒有負(fù)圈的情況下，v1 至多通過至多通過 n-2 頂點(diǎn)到達(dá)頂點(diǎn)到達(dá) vj , 與與 wij0 不同，可逐點(diǎn)進(jìn)入不同，可逐點(diǎn)進(jìn)入 Si ，但在這里，目前是最，但在這里，目前是最短的但完全可能通過其它點(diǎn)會(huì)更短短的但完全可能通過其它點(diǎn)會(huì)更短 .但求最短路方法的基本思想還是成立的但求最短路方法的

50、基本思想還是成立的： 設(shè)設(shè) v1 vl 的最短路是的最短路是 v1 vi vk vl , 則則 v1 vk 的最短路是的最短路是 v1 vi vk 想法是這樣，從步數(shù)著手，一步可達(dá)、兩步、三想法是這樣，從步數(shù)著手，一步可達(dá)、兩步、三步，步，至多，至多 n-1 步步 . 即如下遞推公式：即如下遞推公式：1(1)1( )(1)0min2,3,.,2,3,.,1jjttjiijiuuwuuwjn tn( ) tju其中其中 表示表示 t 步內(nèi)步內(nèi) v1 至至 vj 的最短路長(zhǎng)度的最短路長(zhǎng)度.為加快速度，可用為加快速度，可用已計(jì)算的已計(jì)算的 替換替換.( ) tju當(dāng)進(jìn)行到某一步，如第當(dāng)進(jìn)行到某一步，

51、如第 k 步，對(duì)所有的步，對(duì)所有的 j = 2,3,n 有有( )(1)kkjjuu( )2,3,.,kjjuujn則則如果如果 當(dāng)當(dāng) k n-1, 仍不出現(xiàn)仍不出現(xiàn)( )(1)2,3,.,kkjjuujn則網(wǎng)絡(luò)中含有負(fù)圈則網(wǎng)絡(luò)中含有負(fù)圈 .這算法是由這算法是由 Ford 1956年給出年給出 .第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 ；0110101010010110abcdabAcd2(2)():ijAa(2)321010011 00 1201a cabcdb(2)322a 一般地，一般地， 的值表示從城市的值表示從城市 i 到城市到城市 j 經(jīng)兩次航經(jīng)兩次航行到達(dá)行到達(dá) j 的線路數(shù)；若記的線路

52、數(shù)；若記 ，則，則 (2)ija( )()kkijAa( )kija=從城市從城市 i 到城市到城市 j 經(jīng)經(jīng) k 次航行到達(dá)次航行到達(dá) j 的線路數(shù)的線路數(shù).22011111102202011A31331223140221331A46253535326626253A 于是，從于是，從 d 出發(fā)經(jīng)出發(fā)經(jīng) 3 次航行到達(dá)次航行到達(dá) c 的線路數(shù)為的線路數(shù)為 條，條，(3)433a;.dcdcdbacdcac 從從 d 出發(fā)經(jīng)出發(fā)經(jīng) 4 次航行回到次航行回到 d 的線路數(shù)為的線路數(shù)為 條條(4)443a;.dcdcddbacddcacd ( )23().kkijCcAAAA =從頂點(diǎn)從頂點(diǎn) i 到

53、頂點(diǎn)到頂點(diǎn) j 經(jīng)少于經(jīng)少于 k +1步到達(dá)步到達(dá) j 的道路數(shù)的道路數(shù) ( )kijc第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 用用 Ford 算法求如下網(wǎng)絡(luò)中算法求如下網(wǎng)絡(luò)中 v1至各頂點(diǎn)至各頂點(diǎn)的最短路的最短路 .v1v2v3v4v5v6-26-182-5311v7v821-5-3-3-17-10123602305180210101710350mmmmmmmmmmmmmmmmmmAmmmmmmmmmmmmmmmmmmmmm(1)(1)(1)(1)1281.uuuuA121288.AABBBA得鄰接矩陣得鄰接矩陣(2)(1)(1)(1)128128.*.uuuuBBB定義定義 Ai * Bj =11

54、8miniijiab ( )(1)(1)(1)128128.*.ttttuuuuBBBv1v2v3v4v5v6-2682-5311v7v821-5-3-3-17-10123602305180210101710350mmmmmmmmmmmmmmmmmmAmmmmmmmmmmmmmmmmmmmmmv1v2v3v4v5v6v7v8t=10-1-23mmmmt=2t=3t=4定義定義 Ai * Bj =118miniijiab ( ) tju0-5-2-71-15m0-5-2-76-1-5-30-5-2-76-1-5-3 當(dāng)當(dāng) t = 3 和和 t = 4v1 至各頂點(diǎn)路長(zhǎng)不至各頂點(diǎn)路長(zhǎng)不變（步數(shù)增加

55、也不變（步數(shù)增加也不會(huì)變）會(huì)變）. 此時(shí)，已得此時(shí)，已得所求所求 .-1第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 求網(wǎng)絡(luò)中所有頂點(diǎn)之間的最短路求網(wǎng)絡(luò)中所有頂點(diǎn)之間的最短路 . 當(dāng)然，可以通過當(dāng)然，可以通過 n 次調(diào)用次調(diào)用 Ford算法來完成，但計(jì)算法來完成，但計(jì)算量為算量為 O(n2m) . 1962年年 Floyd- -Warshall 提出的算法計(jì)提出的算法計(jì)算量為算量為 O(n3) . (1)(1)(1)( )( )( )0min, ,1,2,.,iiijijttttijijittjuuwijuuuui j tn 算法可用如下遞推公式表示算法可用如下遞推公式表示：(1)(1)(1),0,()ij

56、iiijijPjuuwij( )( )( )tttijittjuuu(1)( )(1)( )( )tttttijitijittjPPuuuFloyd- -Warshall 算法算法Step 0( 1)( )ttijijPP(1)( )ttijijuut = 0 , 對(duì)于所有頂點(diǎn)對(duì)于所有頂點(diǎn) vi , vj令令Step 1對(duì)于所有頂點(diǎn)對(duì)于所有頂點(diǎn) vi , vj若若令令否則否則, , 令令Step 2如果如果 t = n , 則結(jié)束則結(jié)束 ; 否則否則 令令 t = t+1 轉(zhuǎn)轉(zhuǎn)Step 1.第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃 用用 Floyd-Warshall 算法求如下網(wǎng)絡(luò)中所算法求如下網(wǎng)絡(luò)中所

57、有頂點(diǎn)之間的最短路有頂點(diǎn)之間的最短路 .v1v2v3v464-73105-3-36記最短路長(zhǎng)度記最短路長(zhǎng)度矩陣為矩陣為 U, 最短路矩陣為最短路矩陣為 P初始值為初始值為(1)(1)043123430712341003123456601234mmUPm(2)(2)043123430712341003123456201214mmUPm(3)(3)0431234307123471003223436102224mmUP第一次迭代后得到第一次迭代后得到第二次迭代后得到第二次迭代后得到(4)(4)043012333074123371003223436102224UP第三次迭代后得到第三次迭代后得到(5)

58、(5)04301233307412336903443436102224UP第四次迭代后得到第四次迭代后得到 終終 點(diǎn)點(diǎn) v1 v2 v3 v4 起起 點(diǎn)點(diǎn) v1 (v1 , v2) (v1 , v3)(v1 , v3) (v3 , v4) v2 (v2 , v1) (v2 , v3) (v2 , v3) (v3 , v4)v3(v3 , v4) (v4 , v2) (v2 , v1)(v3 , v4) (v4 , v2) (v3 , v4)v4 (v4 , v2) (v2 , v1) (v4 , v2)(v4 , v2) (v2 , v3) 最短路長(zhǎng)度可直接由最短路長(zhǎng)度可直接由U(5)得到得到

59、, 根據(jù)根據(jù) P(5)最最后得到的最短路為后得到的最短路為第十第十章章 網(wǎng)絡(luò)規(guī)劃網(wǎng)絡(luò)規(guī)劃三、應(yīng)用舉例三、應(yīng)用舉例 選址問題選址問題或設(shè)點(diǎn)問題是指為一個(gè)或幾個(gè)服務(wù)設(shè)施或設(shè)點(diǎn)問題是指為一個(gè)或幾個(gè)服務(wù)設(shè)施在一定區(qū)域內(nèi)選定它的位置在一定區(qū)域內(nèi)選定它的位置, , 使某一指標(biāo)達(dá)到最使某一指標(biāo)達(dá)到最優(yōu)優(yōu) . 選址問題的數(shù)學(xué)模型依賴于設(shè)施可能的區(qū)域和評(píng)選址問題的數(shù)學(xué)模型依賴于設(shè)施可能的區(qū)域和評(píng)判位置優(yōu)劣的標(biāo)準(zhǔn)判位置優(yōu)劣的標(biāo)準(zhǔn), ,有許多不同種類的選址問題有許多不同種類的選址問題 .(1) 中心問題中心問題 對(duì)一些緊急服務(wù)型的設(shè)施對(duì)一些緊急服務(wù)型的設(shè)施( (如急救中心、消防站如急救中心、消防站等等) )，要求距

60、網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)距離盡可能小，要求距網(wǎng)絡(luò)中最遠(yuǎn)的被服務(wù)點(diǎn)距離盡可能小 .可以在點(diǎn)上、邊可以在點(diǎn)上、邊上、區(qū)域內(nèi)上、區(qū)域內(nèi)Example 12 現(xiàn)準(zhǔn)備在現(xiàn)準(zhǔn)備在 v1, v2, ,v7 七個(gè)居民點(diǎn)中設(shè)置七個(gè)居民點(diǎn)中設(shè)置醫(yī)院醫(yī)院 . 各點(diǎn)之間的距離如圖各點(diǎn)之間的距離如圖, 問設(shè)一個(gè)醫(yī)院在哪個(gè)居民問設(shè)一個(gè)醫(yī)院在哪個(gè)居民點(diǎn)點(diǎn),可使最大服務(wù)距離為最小可使最大服務(wù)距離為最小 ; 若設(shè)兩個(gè)若設(shè)兩個(gè),問應(yīng)設(shè)在哪兩問應(yīng)設(shè)在哪兩個(gè)居民點(diǎn)個(gè)居民點(diǎn) ?v1v2v3v4v5v662.531.81.5v721.534 求出任意兩點(diǎn)的最短路求出任意兩點(diǎn)的最短路長(zhǎng)度長(zhǎng)度, 得矩陣得矩陣 D = (dij) :0356.3