短路問題ppt課件-資料下載頁
2025-05-01 22:13本頁面
【正文】 ? 解 : v1 v2 v3 v4 v5 9 3 2 2 4 7 ?????????????????????????04702342027209390)0(D?????????????????5432154321543215432154321)0(R? 插入 v1得 : ? 矩陣中帶下劃線的元素為經(jīng)迭代比較以后有變化的元素 ,即需要引入中間點 v1,從而 R(1)中相應(yīng)的位置換為 1. ?????????????????????????047021234202712209390)1(D???????????????????5432154311543215132154321)1(R? 插入 v2得 : ? 插入 v3得 : ???????????????????????019471619021234202117122091631190)2(D???????????????????????5232224311543225132124221)2(R?????????????????????????06461560243420211642091531190)3(D????????????????????????5333334331543223332134221)3(R? 插入 v4得 : ? 插入 v5得 :D(5)=D(4),R(5)=R(4) ? 從 D(5)中得各頂點間的最短路 ,從 R(5)中可追溯出最短路的路由 .例如 :從 D(5)中得 d51(5) =9,故從 v5到 v1的最短路為 9,從 R(5)中得 r51(5)= v4向v5追溯 : r54(5)=3, r53(5)=3。由 v4向 v1追溯 : r41(5)=1. ? 所以 :從 v5到 v1的最短路徑為 :5→3→4→1. ???????????????????????0646960243420256420793570)4(D???????????????????????5333434331543243332444441)4(R? 應(yīng)用：可化為最短路問題的多階段決策問題 : ? 對于最優(yōu)化問題中的多階段決策問題 ,?？捎脛討B(tài)規(guī)劃來處理 ,它的特點是先將一個復(fù)雜的問題分解成相互聯(lián)系的若干個階段 ,每個階段即為一個小問題 ,然后逐個處理 .一旦每一個階段的決策確定后 ,整個過程的決策也隨之確定 .但動態(tài)規(guī)劃不存在一種標(biāo)準(zhǔn)的數(shù)學(xué)形式 ,可以說動態(tài)規(guī)劃的使用是一種藝術(shù) ,需要根據(jù)不同的實際問題列出相應(yīng)的動態(tài)規(guī)劃遞推關(guān)系式 ,再求解遞推關(guān)系 ,而不同的遞推關(guān)系有不同的解法 ,沒有一個統(tǒng)一的程序 .對某些多階段決策 ? 問題 ,要寫出其動態(tài)規(guī)劃遞推關(guān)系難度很大 ,而圖論中的最短路問題是一個多階段決策問題 ,它可以用現(xiàn)成的 Dijkstra算法求解 .因此 ,對某些較復(fù)雜的多階段決策問題 ,可以通過構(gòu)造適當(dāng)?shù)膱D ,將它轉(zhuǎn)化成最短路問題 ,從而使問題變得清晰 ,直觀 .而一旦轉(zhuǎn)化成功 ,剩下的就只是用標(biāo)準(zhǔn)的 Dijkstra算法程序求解了 . ? 要將一個多階段決策問題化為最短路問題 ,關(guān)鍵在于對該問題構(gòu)造出相應(yīng)的圖 ,使圖的頂點 ,邊 ,權(quán)分別對應(yīng)于該問題的某些要素 ,從而圖中某些頂點間的最短路就對應(yīng)于該問題的解 .有時對同一問題可以構(gòu)造出不同的圖 . ? 下面通過一個實例來說明構(gòu)造圖的方法 . ? 例 4.(設(shè)備更新問題 )企業(yè)使用一臺設(shè)備 ,每年年初 ,企業(yè)領(lǐng)導(dǎo)就要確定是購置新的 ,還是繼續(xù)使用舊的 .若購置新設(shè)備 ,就要支付一定的購置費用 。若繼續(xù)使用舊的 ,則需要支付一定的維修費用 .現(xiàn)在要制定一個五年之內(nèi)的設(shè)備更新計劃 ,使得五年內(nèi)總的支付費用最少 . ? 已知該種設(shè)備在每年年初的價格為 :(元 ) ? 第一年 第二年 第三年 第四年 第五年 ? 11 11 12 12 13 ? 使用不同時間設(shè)備所需維修費為 :(元 ) ? 使用年限 :01 12 23 34 45 ? 維修費用 : 5 6 8 11 18 ? 解 :構(gòu)造如下所示帶權(quán)有向圖 : ? (1)頂點集合 V={v1,v2,v3,v4,v5,v6},其中 :vi表示第i年 (i=1,2,3,4,5)初購置新設(shè)備的決策 ,v6表示第 5年底 ? (2)弧集合 E={(vi,vj)|i=1,2,3,4,5。ij≤6},弧 (vi,vj)表示第 i年初購進(jìn)一臺設(shè)備一直使用到第 j年初的決策 ,其權(quán) w(vi,vj)表示由這一決策在第 i年初到第 j年初的總費用 .如 :w(v1,v4)=11+5+6+8=30 ? (3)問題轉(zhuǎn)化為求 v1到 v6的最短路問題 ,求得兩條最短路為 :v1→v 4 → v 6。v1 → v 3 → v :53. v6 v1 v2 v3 v4 v5 59 16 16 17 17 18 22 41 30 22 41 30 23 31 23
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1