數(shù)模最短路與最優(yōu)問題(編輯修改稿)
2025-06-18 17:36 本頁面
【文章內(nèi)容簡介】 算法原理 —— 求距離矩陣的方法 把帶權(quán)鄰接矩陣 W 作為距離矩陣的初值，即 D ( 0 ) = ?? ?)( )0(ijd = W （１） D ( 1 ) = ?? ?)( )1(ijd，其中 )0(1)0()1( ,m i n { iijij ddd ? })0(1 jd? )1(ijd 是從 v i 到 v j 的只允許以 v 1 作為中間點(diǎn)的路徑中最短路的長度． （ 2 ） D ( 2 ) = ?? ?)( )2(ijd，其中 )1(2)1()2( ,m i n { iijij ddd ? })1(2 jd? )2(ijd是從 v i 到 v j 的只允許以 v 1 、 v 2 作為中間點(diǎn)的路徑中最短路的長度． … （ 3 ） D ( ν ) =??? ?)( )(ijd，其中 )1()1()( ,m i n{ ??? ???? iijij ddd })1( ?? ?? jd )(?ijd 是從 v i 到 v j 的只允許以 v 1 、 v 2 、 … 、 ?v 作為中間點(diǎn)的路徑中最短路 的長度．即是從 v i 到 v j 中間可插入任何頂點(diǎn)的路徑中最短路的長，因此 D ( ν ) 即是距離矩陣． 返回 算法原理 —— 求路徑矩陣的方法 R = ?? ?)( ijr , r ij 的含義是從 v i 到 v j 的最短路要經(jīng)過點(diǎn)號(hào)為 r ij 的點(diǎn)． ?? ?? )( )0()0( ijrR , jr ij ?)0(每求得一個(gè) D ( k ) 時(shí)，按下列方式產(chǎn)生相應(yīng)的新的 R ( k )否則若 )1()1()1()1()(?????????? kkjkikkijkijkijdddrkr在建立距離矩陣的同時(shí)可建立路徑矩陣 R． 即當(dāng) k被插入任何兩點(diǎn)間的最短路徑時(shí)，被記錄在 R(k)中，依次求 時(shí)求得 ，可由 來查找任何點(diǎn)對(duì)之間最短路的路徑． )(?D )(?R返回 ) ( ? R vi j 算法原理 —— 查找最短路路徑的方法 若 1)( pr ij ?? ，則點(diǎn) p 1 是點(diǎn) i 到點(diǎn) j 的最短路的中間點(diǎn) .然后用同樣的方法再分頭查找．若： （１） 向點(diǎn) i 追溯 得：2)( 1 pr ip ??,3)( 2 pr ip ??, … ,kip pr k ?)( ? （２） 向點(diǎn) j 追溯 得：1)( 1 qr jp ??,2)( 1 qr jq ??, … , jrjq m ?)( ? pk p2 p1 p3 q1 q2 qm 則由點(diǎn) i到 j的最短路的路徑為： jqqqpppi mk ,, 21,12 ??返回 算法步驟 F l o y d 算法： 求任意兩點(diǎn)間的最短路． D( i ,j ) ： i 到 j 的距離 ． R(i ,j ) ： i 到 j 之間的插入點(diǎn)． 輸入 : 帶權(quán)鄰接矩陣 w ( i ,j ) （１） 賦初值： 對(duì)所有 i ,j , d ( i ,j ) ? w ( i ,j ) , r ( i ,j ) ? j , k ? 1 ( 2 ) 更新 d ( i ,j ) , r ( i ,j ) 對(duì)所有 i ,j ，若 d ( i ,k ) +d ( k ,j ) d ( i ,j ) ，則 d ( i ,j ) ? d ( i ,k ) +d ( k ,j ) , r ( i ,j ) ? k ( 3 ) 若 k = ? ，停止．否則 k ? k +1 ，轉(zhuǎn)（２）． 例 求下圖中加權(quán)圖的任意兩點(diǎn)間的距離與路徑． TO MATLAB (road2(floyd)) ??????????????????????????????????5333434331543243332344441,0646960243420256420793570RD951 ?d ，故從 v 5 到 v 1 的最短路為９．51r ＝４．由 v 4 向 v 5 追溯 ： 3,3 5354 ?? rr 。 由 v 4 向 v 1 追溯 ： 141 ?r 所以從 v 5 到 v 1 的最短路徑為： 1435 ??? .返回 最 短 路 的 應(yīng) 用 一、 可化為最短路問題的多階段決策問題 二、 選 址 問 題 1． 中心問題 2． 重心問題 返回 可化為最短路問題的多階段決策問題 例 1 設(shè)備更新問題：企業(yè)使用一臺(tái)設(shè)備，每年年初，企業(yè)領(lǐng)導(dǎo)就要確定是購置新的，還是繼續(xù)使用舊的 . 若購置新設(shè)備，就要支付一定的購置費(fèi)用；若繼續(xù)使用，則需支付一定的維修費(fèi)用 . 現(xiàn)要制定一個(gè)五年之內(nèi)的設(shè)備更新計(jì)劃，使得五年內(nèi)總的支付費(fèi)用最少 . 已知該種設(shè)備在每年年初的價(jià)格為： 第一年 第二年 第三年 第四年 第五年 11 11 12 12 13 使用不同時(shí)間設(shè)備所需維修費(fèi)為： 使用年限 0 － 1 1 － 2 2 － 3 3 － 4 4 － 5 維修費(fèi) 5 6 8 11 18 構(gòu)造加權(quán)有向圖 G 1( V , E ) （ 1 ）頂點(diǎn)集 V ＝ { Xib , i =1,2, 3,4, 5} ∪ { X ir k( ) , i =2,3, 4,5, 6。 k =1, 2, … , i 1} , 每個(gè)頂點(diǎn)代表年初的一種決策，其中頂點(diǎn) Xib代表第 i 年初購置新設(shè)備的決策，頂點(diǎn) X ir k( ) 代表第 i 年初修理用過 k 年的舊設(shè)備的決策 （ 2 ） 弧集 E ={( , ), ( , ), ( ) ,X X X Xib i b ir k i b? ?1 1i= 1,2,3,4。 k= 1,2, … , i 1} ∪ {( , ),( )X Xib i r? 11, i =1,2,3,4 ,5} ∪ {( , )( ) ,( )X Xir k i rk? ?1 1, i= 1,2,3,4,5 。 k = 1,2 ,i 1} 若第 i 年初作了決策X i后，第 i+ 1 年初可以作決策X i ? 1，則頂點(diǎn)X i與 X i ? 1之間有弧 (X i,X i ? 1) ，其權(quán) W(X i,X i ? 1) 代表第 i 年初到第 i+ 1 年 初之間的費(fèi)用 . 例如，弧( , )( )X Xb r3 4 1代表第 三 年初買新設(shè)備，第四年初 決定用第三年買的用過一年的舊設(shè)備，其權(quán)則為第三年初的購置費(fèi)與 第 三、 第 四年間的維修費(fèi)之和， 即 為 12 ＋ 5 ＝ 17 . （ 3 ）問題轉(zhuǎn)化為頂點(diǎn) Xb1到 Xrk6( )的最短路問題 . 五年的最優(yōu)購置費(fèi)為 k b rkd X X? 1 2 3 4 5 1 6, , , ,( )m in { ( , )} 其中 d( Xb1, Xrk6( )) 為頂點(diǎn) Xb1到 Xrk6( )的最短路的權(quán) . 求得最短路的權(quán)為 53 ，而兩條最短路分別為 X X X X X Xb r r b r r1 2 1 3 2 4 5 1 6 2? ? ? ? ?( ) ( ) ( ) ( )。 X X X X X Xb r b r r r1 2 1 3 4 1 5 2 6 3? ? ? ? ?( ) ( ) ( ) ( ) 因此，計(jì)劃為第一、第三年初購置新設(shè)備，或第一、第四年初購置新設(shè)備， 五年費(fèi)用均最省，為 53 . 也可構(gòu)造加權(quán)有向圖 G 2( V , E ) . （ 1 ）頂點(diǎn)集 V ={ V V V V V V1 2 3 4 5 6, , , , ,} ，V i 表第 i 年初購置新設(shè)備的決策， V 6 表第五年底 . （ 2 ）弧集 E ={( , )V Vi j， i = 1,2,3,4, 5。 i j ≤ 6} ,弧( , )V Vi j表第 i 年初購進(jìn)一臺(tái)設(shè)備一直使用到第 j 年初的決策，其權(quán) W( , )V Vi j表由這一決策在第 i 年初到第 j 年初的總費(fèi)用，如W ( , )V V1 4=1 1 +5 +6 +8 =30 . （ 3 ）問題轉(zhuǎn)化為求 V 1 到 V 6 的最短路問題，求得兩條最短路為V V V1 4 6– – ， V V V1 3 6– – ，權(quán)為 53 ，與圖 G1( V , E) 的解相同． 返回 （ 2 ） 計(jì)算在各點(diǎn)iv設(shè)立服務(wù)設(shè)施的最大服務(wù)距離)( ivS． }{max)(1 ijjidvS???? 1 , 2 , ,i ?? 選址問題 中心問題 例 2 某城 市要建立一個(gè)消防站，為該市所屬的七個(gè)區(qū)服務(wù)，如圖所示．問應(yīng)設(shè)在 哪 個(gè)區(qū)，才能使它至最遠(yuǎn)區(qū)的路徑最短． （ 1 ）用
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1