企業(yè)運(yùn)籌學(xué)--圖與網(wǎng)絡(luò)理論講義-文庫(kù)吧資料
2025-03-11 19:59本頁(yè)面
【正文】 ?????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 10② 9③ ∞ )3(jd福德算法 11 }min{ )2()3( ijij ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 0 2 5 10 8③ 10⑤ )3(jd福德算法 12 }min{ )3()4( ijij ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 0 2 5 10 8③ 10⑤ )4(jd0 2 5 10 8③ 9⑤ )3(jd福德算法 13 }min{ )4()5( ijij ldd ?? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 ???????????????????????????????????013103930583503698302620654321??????L)1(jd0 2 6 ∞ ∞ ∞ )2(jd0 }min{ )()1( ijkikj ldd ???2 5② 10② 9③ ∞ 0 2 5 10 8③ 10⑤ )4(jd0 2 5 10 8③ 9⑤ )5(jd0 2 5 10 8 9 最大流問(wèn)題的概念 所謂最大流問(wèn)題就是在一定的條件下 ， 要求流過(guò)網(wǎng)絡(luò)的物流 、 能量流或信息流等流量為最大的問(wèn)題 ， 在最大流問(wèn)題中一般有如下規(guī)定： ① 網(wǎng)絡(luò)有一個(gè)起點(diǎn) υs和一個(gè)終點(diǎn) υt ② 網(wǎng)絡(luò)是有向網(wǎng)絡(luò) ， 即流有方向性 。 福德算法 2 適用于有負(fù)權(quán)，但無(wú)負(fù)回路的有向或無(wú)向網(wǎng)絡(luò)， 算法中 dj(k)為從 υ1到 υj的邊數(shù)不超過(guò) k的路線中距離最短的。 如果希望計(jì)算 v1到 v4的最短距離 ， 繼續(xù) })(),(min{ ijij lPT ????????????SjTPj )(0)( 1??)}({min jS Tj?? ? )()(kk TP ?? ? 10}39,10min{})(),(min{)( 64644 ????? lPTT ??? 10)()}({min 4 ??? ??? TT jSj 10)()( 44 ?? ?? TP v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 狄克斯拉算法 9 表格實(shí)現(xiàn) ???????????????????????????????????013103930583503698302620654321??????Lvj v1 v2 v3 v4 v5 v6 初始值 T( vj ) 0 ∞ ∞ ∞ ∞ ∞ v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 第一次 P( )+lij 0+2 0+6 0+∞ 0+∞ 0+∞ T( ) 2 6 ∞ ∞ ∞ 狄克斯拉算法 10 表格實(shí)現(xiàn) vj v1 v2 v3 v4 v5 v6 初始值 T( vj ) 0 ∞ ∞ ∞ ∞ ∞ 第一次 P( )+lij 0+2 0+6 0+∞ 0+∞ 0+∞ T( ) 2 6 ∞ ∞ ∞ 第二次 P( )+lij 2+3 2+8 2+9 2+∞ T( ) 5 10 11 ∞ 第三次 P( )+lij 5+5 5+3 5+∞ T( ) 10 8 ∞ 第四次 P( )+lij 8+ ∞ 8+1 T( ) 10 9 福德算法 1 適用于有負(fù)權(quán)，但無(wú)負(fù)回路的有向或無(wú)向網(wǎng)絡(luò)，其算法步驟如下： 令 jj ld 1)1( ? }min{ )()1(ijkikj ldd ???計(jì)算 若對(duì)所有 j )()1( kjkj dd ??則最優(yōu)，否則把 k的值加 1，繼續(xù)計(jì)算。 ③令 若 S=V， 則已找到最短樹(shù)，否則②， SS ji ?? ?? , }{1 jkk S ???? }{1 jkk SS ???? v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 網(wǎng)絡(luò)最短樹(shù) 生長(zhǎng)法 2 方法示例 取 S={v1}, 則 S到其余點(diǎn)的距離在距離矩陣中第一行 ???????????????????????????????????013103930583503698302620654321??????Lv2 v3 v4 v5 v6 S1 2 6 ∞ ∞ ∞ V2 3 8 9 ∞ S2 3 8 9 ∞ 網(wǎng)絡(luò)最短樹(shù) 生長(zhǎng)法 3 方法示例 ???????????????????????????????????013103930583503698302620654321??????Lv2 v3 v4 v5 v6 S1 2 6 ∞ ∞ ∞ V2 3 8 9 ∞ S2 3 8 9 ∞ V3 5 3 ∞ S3 5 3 ∞ V5 ∞ 1 S4 5 1 V6 3 S5 3 網(wǎng)絡(luò)最短樹(shù) 生長(zhǎng)法 4 v2 v3 v4 v5 v6 S1 2 6 ∞ ∞ ∞ V2 3 8 9 ∞ S2 3 8 9 ∞ V3 5 3 ∞ S3 5 3 ∞ V5 ∞ 1 S4 5 1 V6 3 S5 3 v1 1 3 9 5 3 8 3 6 2 v6 v5 v3 v4 v2 網(wǎng)絡(luò)最短路線問(wèn)題 最短路線問(wèn)題的一般提法是：欲尋找網(wǎng)絡(luò)中從起點(diǎn) υ1到終點(diǎn) υn的最短路線 ， 即尋求連接這兩點(diǎn)的邊的總長(zhǎng)度為最小的通路 ， 最短路線中的網(wǎng)絡(luò)大都是有向網(wǎng)絡(luò) ， 也可以是無(wú)向網(wǎng)絡(luò) 。 由于在每次生長(zhǎng)時(shí)都采用就近生長(zhǎng)的方法 ，生成的樹(shù)一定是最短樹(shù) 。 如果原網(wǎng)絡(luò)不連通 ， 則在生長(zhǎng)過(guò)程中會(huì)出現(xiàn)某些點(diǎn)不能被生長(zhǎng) ， 則結(jié)束 。 方法示例： 例 5－ 4 對(duì)圖中的網(wǎng)絡(luò)， 用破圈法求最短樹(shù)。 ② 在圈中選取權(quán)數(shù)最大的邊 ， 從網(wǎng)絡(luò)圖中截去該邊 ， 對(duì)新的網(wǎng)絡(luò) ， 轉(zhuǎn) ① 。 網(wǎng)絡(luò)最短樹(shù) 破圈法原理 方法原理 如果網(wǎng)絡(luò)圖中無(wú)圈并且 q=p1， 則已經(jīng)是樹(shù)； 如果網(wǎng)絡(luò)圖中有圈 ， 則截去該圈中權(quán)數(shù)最大的邊；這樣 ， 并不影響網(wǎng)絡(luò)圖的連通性 ， 且能使邊數(shù)減少一個(gè)； 經(jīng)過(guò)一定次數(shù)的截邊 ， 網(wǎng)絡(luò)圖中將再也沒(méi)有圈 ，成為無(wú)圈圖； 如果此時(shí)的網(wǎng)絡(luò)滿(mǎn)足 q=p1， 則已經(jīng)是樹(shù)； 由于每次截去的邊在圈中具有最大的權(quán)數(shù) ， 因此獲得的樹(shù)也是最短的樹(shù) 。 ⑤ 連通 ， 但若舍棄一條邊 ， 圖便不連通 。 ③ 連通 ， q=p1。 定理 以下關(guān)于樹(shù)的六種不同描述是等價(jià)的： ① 無(wú)圈連通圖 。 求最短樹(shù)的方法 ， 依據(jù)的是樹(shù)的特
醫(yī)療健康相關(guān)推薦
鄂ICP備17016276號(hào)-1