網(wǎng)絡(luò)模型課件

1、網(wǎng)絡(luò)模型的討論，本質(zhì)上屬于圖論用途極其廣泛（如：運輸系統(tǒng)設(shè)計、信息系統(tǒng)設(shè)計、項目計劃管理等）、實用性強，是網(wǎng)絡(luò)模型的特征之一，其解法的特殊，也是值得關(guān)注的地方需要重點掌握：各種網(wǎng)絡(luò)模型的算法。第八章 網(wǎng)絡(luò)模型一、問題及網(wǎng)絡(luò)圖表示1、什么是最短路問題在網(wǎng)絡(luò)中任意選擇某點為起點，求出從此起點到網(wǎng)絡(luò)中其余各點的最短路徑。如：Taxi 的調(diào)度問題2、例子Gorman 建筑公司承擔(dān)了散布在鄰近三個區(qū)域內(nèi)的一些建筑項目，公司總部與這些工地之間經(jīng)常有人員、設(shè)備、材料等的運輸往來。與運輸成本相關(guān)的最短路問題，就是很值得考慮的重要問題設(shè)公司總部與六個工地間的公路網(wǎng)絡(luò)如下頁所示：( 單位：km )。第一節(jié) 最短路

2、問題一、問題及網(wǎng)絡(luò)圖表示第一節(jié) 最短路問題二、最短路算法介紹Dijkstra 算法 (Dijkstra 于 1959 年提出，又稱加標(biāo)號法 labeling procedure )1、結(jié)點之標(biāo)號(給出：累計路程、路徑兩個指標(biāo))第一節(jié) 最短路問題二、最短路算法（Dijkstra 算法）2、結(jié)點標(biāo)號的分類1）有/無標(biāo)號結(jié)點有標(biāo)號結(jié)點已指定從起始結(jié)點到此結(jié)點的一條路徑無標(biāo)號結(jié)點未指定從起始結(jié)點到此結(jié)點的路徑2）永久/臨時標(biāo)號有永久標(biāo)號結(jié)點已求出從起始點到此結(jié)點的最短路徑有臨時標(biāo)號結(jié)點未求出從起始點到此結(jié)點的最短路徑。第一節(jié) 最短路問題二、最短路算法（Dijkstra 算法）3、例子的解1 ) 定起始

3、點，寫上永久標(biāo)號 0 ，S如：結(jié)點內(nèi)涂黑表示已有永久標(biāo)號2 ) ( 迭代 ) 反復(fù)以下步驟： (1) 為起始點能直達(dá)的結(jié)點寫上臨時標(biāo)號 (2) 比較臨時標(biāo)號內(nèi)第一個數(shù)，選擇小的一個 (3) 小者寫成永久標(biāo)號 ( 圈內(nèi)涂黑 ) (4) 有最新永久標(biāo)號的結(jié)點視為新的起始點。第一節(jié) 最短路問題二、最短路算法（Dijkstra 算法）4、求出最短路132 13 1354 1351356 135675、第二個例子在如下頁的網(wǎng)絡(luò)中，求結(jié)點 1 和結(jié)點 10 之間的最短路徑解答： 135810 total = 19。第一節(jié) 最短路問題二、最短路算法（Dijkstra 算法）第一節(jié) 最短路問題三、說明1、算法

4、中，起始結(jié)點可以任意選定, N 個結(jié)點問題，一般需要有 N1 次迭代2、“MS”軟件包只要先輸入網(wǎng)絡(luò)，可以解決此類問題3、其它用處：最小旅行時間問題、旅行成本問題、管道鋪設(shè)問題、線路安排問題、廠區(qū)布局問題、設(shè)備更新問題等等4、練習(xí)的第四題設(shè)備維護(hù)問題說明5、標(biāo)號法已發(fā)展到可以解決：(時間所限不展開討論) (1) 弧值為負(fù)數(shù)；(2) 有向網(wǎng)絡(luò) ( 如：單行道運輸問題 )。第一節(jié) 最短路問題一、概念1、樹不含圈的聯(lián)通圖2、什么是（網(wǎng)絡(luò)）最小支撐樹 1) 貫通網(wǎng)絡(luò)所有結(jié)點支撐 2) 分枝 (弧) 總長度最小最小3、用處：分子結(jié)構(gòu)問題、電網(wǎng)絡(luò)分析問題、計算機網(wǎng)絡(luò)設(shè)立問題、管道鋪設(shè)問題等等的解決。第二節(jié)

5、 最小支撐樹問題二、實例計算機中心欲使五家新用戶與中心聯(lián)機電話公司負(fù)責(zé)排線，由于價格昂貴，要尋求最小支撐樹由于計算機網(wǎng)絡(luò)的可聯(lián)通性能，得到：第二節(jié) 最小支撐樹問題三、算法一 ( Greedy algorithm )1、因為問題很特殊，就有：若每一步追求最優(yōu)，最后也能得到問題的最優(yōu)的解法貪心解法2、作法1) 對弧的長短按照升序排序2)任意結(jié)點開始，在保證不構(gòu)成圈的前提下3) 重復(fù)進(jìn)行：將最近的不聯(lián)通結(jié)點并入網(wǎng)絡(luò)的聯(lián)通段（可以雙線表示聯(lián)通）3、說明：最小支撐樹不唯一，但分枝總長度唯一4、例子的計算略。o.f.=110。第二節(jié) 最小支撐樹問題三、算法一 ( Greedy algorithm )第二個

6、例子（總長度28）第二節(jié) 最小支撐樹問題四、算法二（Prims algorithm）1、算法一的缺點：（1）需要先排序 （2）每一步都需要仔細(xì)確認(rèn)有沒有構(gòu)成圈故，不適合于復(fù)雜、大型的網(wǎng)絡(luò)模型2、算法二的步驟1）任意選擇一個起點；2）選擇與起點最近的頂點，將此頂點及其與起點相連接的弧一并加入樹；3）對已經(jīng)連接成樹的部分，仍然選擇與樹最近的頂點，然后連上；4）重復(fù)步驟三，直到所有的頂點都連接上。第二節(jié) 最小支撐樹問題一、概念1、什么是最大流問題有一個稱之為入口點 ( source node ) 結(jié)點和一個出口點 ( sink node ) 結(jié)點的網(wǎng)絡(luò)，在給定時期內(nèi)進(jìn) / 出最大流量是？2、用處交通

7、網(wǎng)絡(luò)之流量、計算機網(wǎng)絡(luò)之信息流量、金融系統(tǒng)中現(xiàn)金流量、物流流量、防洪系統(tǒng)設(shè)計、排水系統(tǒng)設(shè)計、供水系統(tǒng)等 .3、基本假定分枝 ( arc )有流量限制且講究方向結(jié)點 ( node )進(jìn)、出相等。第三節(jié) 最大流問題4、例子某國道自北向南方向計劃進(jìn)行大修，運輸部門擬以如下網(wǎng)絡(luò)的公路系統(tǒng)暫時替代之（單位：1000）問題：此網(wǎng)絡(luò)能否適應(yīng) 15000 輛機動車的最大流/小時？每小時最大流量是多少？每一條分枝分別有多大流通過？第三節(jié) 最大流問題二、最大流算法1、方法說明1）尋找從入口到出口的路徑 ( 要保證此路徑可以有流量0 的 flow 通過 )2) 將 1) 中所尋得的路徑盡可能多地增加流量3) 重復(fù)第

8、 1) 2) 步驟，其中用到虛構(gòu)流手段，直至找不到可使 flow 0 的路徑為止。第三節(jié) 最大流問題二、最大流算法2、虛構(gòu)流 ( fictitious flow ) 方法對如下路徑：若修改成為：表明 ： 1) 3 6 分枝上剩余可安排流量為 1000 2) 6 3 的 6000 單位實際上是所謂的虛構(gòu)流 3) 虛構(gòu)流簡明地表示 3 6 方向之流量應(yīng)下降或，簡明地表示若還要增加 3 6 方向之流量應(yīng)轉(zhuǎn)到其它分枝上去。第三節(jié) 最大流問題二、最大流算法3、實例計算可能的五次流量安排如下：1) 1367： pf = 62) 1257 pf = 33) 12357 pf = 24) 1467 pf =

9、15) 14657 pf = 1此時得到如下網(wǎng)絡(luò)流量圖：（見下頁）第三節(jié) 最大流問題二、最大流算法3、實例計算6) 146357 pf = 1故，最大流14，其中的虛構(gòu)流手段之說明見下頁。第三節(jié) 最大流問題二、最大流算法4、虛構(gòu)流說明說明：原始網(wǎng)絡(luò)中 63 之流量0，此處安排 1000 輛車在 63，實際是虛構(gòu)流，此處對 63 做 1000 的安排，實為將原先在 1) 中允許進(jìn)入 36 分枝的 1000 單位流轉(zhuǎn)入沿 35 分枝，則 67 可空 1000 單位流可供安排5、最優(yōu)解第三節(jié) 最大流問題二、最大流算法6、第二個例子求下列網(wǎng)絡(luò)之最大流 ( = 33 ) 第三節(jié) 最大流問題18 世紀(jì)，2

10、9 歲的歐拉解決了哥尼斯堡七橋問題：抽象出“圖”：結(jié)論：不是歐拉圖，亦非半歐拉圖，不論起點和終點在哪里都不可能找到一條經(jīng)過七座橋且每座橋只走一次的路線。第四節(jié) 路徑巡視問題ABCDDCAB路徑巡視問題，又稱中國郵遞員問題，1962 年首先由（山東大學(xué)）管梅谷先生提出抽象說就是：對給定的一個連通圖，在每條邊（弧）上賦予一個非負(fù)的權(quán)，要求一個回路，過每邊至少一次并使回路總權(quán)數(shù)最小商店在弧不在結(jié)點處首先介紹一、一筆畫問題1、問題網(wǎng)絡(luò)中，視路徑?jīng)]有方向，也不一定要求起點終點，但要求任意路徑（弧）僅經(jīng)過一次的問題，稱之為一筆畫問題。第四節(jié) 路徑巡視問題一、一筆畫問題2、有關(guān)的定義1）結(jié)點的價（Valen

11、cy）從某個結(jié)點可引出的 “路徑”（弧）之?dāng)?shù)量稱為該結(jié)點的價2）奇、偶結(jié)點由結(jié)點的價一意決定3）“價”的意義（注意：所有“弧”都必須經(jīng)歷）奇結(jié)點不是起點就是終點；偶結(jié)點只可能是經(jīng)過點；4）半歐拉圖定義連通圖中若：只有兩個相異同的奇結(jié)點，其余皆為偶結(jié)點。第四節(jié) 路徑巡視問題一、一筆畫問題2、有關(guān)的定義5）歐拉圖所有結(jié)點都是偶結(jié)點的連通圖3、（握手）定理連通圖中各結(jié)點價數(shù)之和 2（路徑數(shù)量）4、推論任意連通圖中，奇結(jié)點的個數(shù)總是偶數(shù)證明：由握手定理得： 奇結(jié)點價數(shù)之和偶結(jié)點價數(shù)之和偶數(shù)，所以 奇結(jié)點價數(shù)之和偶數(shù)。第四節(jié) 路徑巡視問題一、一筆畫問題5、定理連通圖是歐拉圖，當(dāng)且僅當(dāng)其中無奇結(jié)點定理的意

12、義：1）若連通圖是歐拉圖無奇結(jié)點，則可以任意結(jié)點為起點，一筆畫后仍然回到起點；2）若連通圖是半歐拉圖兩個奇結(jié)點，則從某奇結(jié)點出發(fā)，一筆畫后以另一個奇結(jié)點為終點；3）若連通圖有四或以上個奇結(jié)點巡視回路，不可能不走重復(fù)路經(jīng)問題：最小重復(fù)？。第四節(jié) 路徑巡視問題二、最短巡視路徑1、問題起點終點，無方向、任意路徑僅經(jīng)過一次、要求使得賦權(quán)的連通圖之總權(quán)數(shù)最小，可用于配送問題決策2、歐拉圖（所有節(jié)點皆為偶節(jié)點的連通圖）可以任意選擇起點，完成一筆畫后總能回到起點，且，總權(quán)數(shù)也最小3、非歐拉圖（奇結(jié)點個數(shù)總是偶數(shù)）的最小總權(quán)數(shù)先羅列出所有奇節(jié)點寫出所有可能的兩兩配對方案重復(fù)路徑分別計算各方案下的最短（附加）連

13、接路徑小中取小例子見下頁。第四節(jié) 路徑巡視問題8674553847WVUZYX3、非歐拉圖的最小總權(quán)數(shù)例子：從 V 開始，并在 V 結(jié)束進(jìn)行巡視，至少經(jīng)過每一弧一次，最短路徑是？ 第四節(jié) 路徑巡視問題8674553847WVUZYX二、最短巡視路徑3、非歐拉圖的最小總權(quán)數(shù)例子的解配對最短路期望的路徑之長度W和X Y和ZWX YZ5712W和Y X和ZWXY XUZ(5+4) + (5+3) = 17W和Z X和YWUZ XY(4+3) + 4 = 11因為第三種配對的路徑最短，連接后總巡視路徑長度 68故巡視路徑應(yīng)是： VWUWXYZVYXUZUV（詳見下頁）。第四節(jié) 路徑巡視問題雙線表示重復(fù)路徑 7 3 Z U 6 7Y 8V 5 4 4 8 XW 5第四節(jié) 路徑巡視問題補充練習(xí)：道路管理人員從 A 點出發(fā)，欲經(jīng)過他所管轄的所有道路。這些道路分布在九個點之間，所有各點之間的道路長度如下圖所示，請設(shè)計經(jīng)過所有道路的最短路線。第四節(jié) 路徑巡視問題IHGFEDC