網(wǎng)絡優(yōu)化第5章最短路問題-文庫吧
2025-04-23 04:41 本頁面
【正文】 ijijxtsitisixxtsxw思考：為什么 xij 可以不限定為 {0， 1}？ 最短路問題的數(shù)學描述 9 Bellman方程 對偶問題為 )(.0)39。(,0,1,1..)(m i n),(:),(:),(????????????? ??????ijAijjjiAjijijAjiijijxtsitisixxtsxw)(.),(,..)()m a x(Ajiwuutsuuijijst?????根據(jù)互補松弛條件 , 當 x和 u分別為原問題和對偶問題的最優(yōu)解時 : )(.),(,0)( Ajiwuux ijijij ?????10 Bellman方程 當某弧 (i,j)位于最短路上時 ， 即變量 xij0時 , 一定有 如果 u為對偶問題最優(yōu)解 ,易知 u+c (c為任意實數(shù) )仍為最優(yōu)解 . 不妨令 us=0 ， 則 u的具體數(shù)值就可以唯一確定了 . Bellman方程 (最短路方程 、 動態(tài)規(guī)劃基本方程 ) 相當于對節(jié)點 j賦予的一個實數(shù)值 uj（ 通常稱為 “ 標號 ” ） ， 在us=0時表示的正好是節(jié)點 s到節(jié)點 j的最短路的長度 . ijij wuu ???????????)(}.{m i n)(,0ijijijswuuu一般情況下直接求解最短路方程是相當困難的 . 11 定理 對于只含正有向圈的連通有向網(wǎng)絡 ， 從起點 s到任一頂點 j都存在最短路 ， 它們構成以起點 s為根的樹形圖 （ 稱為 最短路樹 （ Tree of Shortest Paths） 或 最短路樹形圖 （ Shortest Path Arborescence）） ， 最短路的長度可以由 Bellman方程唯一確定 . 前一部分實際上是 Bellman最優(yōu)化原理的直接結果； 后一部分中 Bellman方程解的唯一性可以用反證法證明 （ 略 ） 最短路樹（樹形圖） A F 5 6 6 7 4 4 5 1 3 B E D C 12 如果將定理中的條件 “ 只含正有向圈 ” 改為 “ 不含負有向圈 ” ： ?上述最短路仍然存在； ?Bellman方程的解的唯一性可能不成立 . 起點 s到頂點的最短路長度分別是 us=u1=0， u2 =10， u3 =11 但此時只要 u3 = u2+1 ? 11 (us=u1=0)就可以滿足 Bellman方程 . 如 us=u1=0， u2 =8， u3 =9 等 最短路樹（樹形圖） 1 2 3 10 1 1 s 對于一般的網(wǎng)絡 ， Bellman方程只是最短路長度必須滿足的 必要條件 ， 而不是充分條件； 對于只含正有向圈 (或無圈 )的連通有向網(wǎng)絡 ， 它才是 充要條件 . 13 最短路算法 如果采用鄰接表表示法，可首先計算各節(jié)點的入度； 然后找入度為零者編號； 去掉已編號節(jié)點及相關弧，同時修改相鄰節(jié)點入度（只需掃描該去掉的節(jié)點的出?。?； 依次類推。 如果采用鄰接矩陣表示法，可首先計算各節(jié)點的入度； 然后找入度為零者編號； 去掉已編號節(jié)點及相關弧，同時修改相鄰節(jié)點入度（只需掃描該去掉的節(jié)點的對應行） ； 依次類推。 無圈網(wǎng)絡 引理 (拓撲排序 , Topological Ordering) 設有向圖 D不含有向圈 ,則 D的頂點總可以重新編號 ,使得 . Ajiji ??? ),(,)( 2nO)( 2nO)(nO)(nO)(mO)( nmO ?)()( 2nOnnO ??該算法自然可以用來判斷有向圖是否無圈圖 . )(mO14 最短路算法 當網(wǎng)絡是無圈時，這一最短路算法的復雜度為 無圈網(wǎng)絡 當采用遞推計算求解上述方程時 , 每個頂點和每條弧均被考慮一次 . )( nmO ?這是求解最短路問題可能達到的最小的復雜度 , 因為任何算法都至少必須對每條弧考慮一次 ??????????)(}.{m i n)(,01ijijijswuuuu)()( mOnmO ??15 最短路算法 – 例 例 計算如下網(wǎng)絡 (圖 (a))中從節(jié)點 A到所有其它節(jié)點的最短路 . E A B C D 1 2 5 1 1 3 4 1 A B C D 1 1 1 E 2 E 2 1 3 5 4 1 5 1 3 4 1 2 計算過程 : =0, =min{0+1}=1, =min{0+(1)}=1, =min{0+5,1+(2),1+3}=1, =min{1+1, 1+4}=0. 1u}{m i n 222 iii wuu ?? ?}{m i n 333 iii wuu ?? ?}
環(huán)評公示相關推薦
鄂ICP備17016276號-1