短路問題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)中相應的位置換為 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ōu)化問題中的多階段決策問題 ,常可用動態(tài)規(guī)劃來處理 ,它的特點是先將一個復雜的問題分解成相互聯(lián)系的若干個階段 ,每個階段即為一個小問題 ,然后逐個處理 .一旦每一個階段的決策確定后 ,整個過程的決策也隨之確定 .但動態(tài)規(guī)劃不存在一種標準的數(shù)學形式 ,可以說動態(tài)規(guī)劃的使用是一種藝術 ,需要根據(jù)不同的實際問題列出相應的動態(tài)規(guī)劃遞推關系式 ,再求解遞推關系 ,而不同的遞推關系有不同的解法 ,沒有一個統(tǒng)一的程序 .對某些多階段決策 ? 問題 ,要寫出其動態(tài)規(guī)劃遞推關系難度很大 ,而圖論中的最短路問題是一個多階段決策問題 ,它可以用現(xiàn)成的 Dijkstra算法求解 .因此 ,對某些較復雜的多階段決策問題 ,可以通過構造適當?shù)膱D ,將它轉化成最短路問題 ,從而使問題變得清晰 ,直觀 .而一旦轉化成功 ,剩下的就只是用標準的 Dijkstra算法程序求解了 . ? 要將一個多階段決策問題化為最短路問題 ,關鍵在于對該問題構造出相應的圖 ,使圖的頂點 ,邊 ,權分別對應于該問題的某些要素 ,從而圖中某些頂點間的最短路就對應于該問題的解 .有時對同一問題可以構造出不同的圖 . ? 下面通過一個實例來說明構造圖的方法 . ? 例 4.(設備更新問題 )企業(yè)使用一臺設備 ,每年年初 ,企業(yè)領導就要確定是購置新的 ,還是繼續(xù)使用舊的 .若購置新設備 ,就要支付一定的購置費用 。若繼續(xù)使用舊的 ,則需要支付一定的維修費用 .現(xiàn)在要制定一個五年之內的設備更新計劃 ,使得五年內總的支付費用最少 . ? 已知該種設備在每年年初的價格為 :(元 ) ? 第一年 第二年 第三年 第四年 第五年 ? 11 11 12 12 13 ? 使用不同時間設備所需維修費為 :(元 ) ? 使用年限 :01 12 23 34 45 ? 維修費用 : 5 6 8 11 18 ? 解 :構造如下所示帶權有向圖 : ? (1)頂點集合 V={v1,v2,v3,v4,v5,v6},其中 :vi表示第i年 (i=1,2,3,4,5)初購置新設備的決策 ,v6表示第 5年底 ? (2)弧集合 E={(vi,vj)|i=1,2,3,4,5。ij≤6},弧 (vi,vj)表示第 i年初購進一臺設備一直使用到第 j年初的決策 ,其權 w(vi,vj)表示由這一決策在第 i年初到第 j年初的總費用 .如 :w(v1,v4)=11+5+6+8=30 ? (3)問題轉化為求 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
教學課件相關推薦
鄂ICP備17016276號-1