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

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

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

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

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

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

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

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

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

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

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

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

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

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