圖論模型：最短路ppt課件(參考版)
2025-05-09 23:19本頁面
【正文】 ? 例 5 在例 4中，若七個區(qū)的學(xué)生人數(shù)分別為 24 3 50人，試問教育部門應(yīng)將學(xué)校建在哪個居民區(qū)，才能使大家都方便？ .),()}({m i n),2,1()(),(211,為網(wǎng)絡(luò)的重心則稱點若令點的權(quán)為：設(shè)定義kkininjjiiiiiivvhvhnidfvhvffv????????? ? ? 所以應(yīng)選擇 E作為新建學(xué)校的地址。七個居民區(qū)之間的道路如下圖所示 . ? 學(xué)校應(yīng)建在哪個居民區(qū)， ? 才能使大家都方便？ ? （圖中距離單位：百米） ? 解：由狄克斯特拉（ Dijkstra） ? 算法計算得各居民之間的最短距離列表如下 : 7234 324615724ABDCEFGA B C D E F G d (vi) ∑di,j A 0 3 4 5 7 8 10 10 37 B 3 0 3 2 4 5 7 7 24 C 4 3 0 5 5 6 8 8 31 D 5 2 5 0 2 3 5 5(min) 22(min) E 7 4 5 2 0 1 3 7 22(min) F 8 5 6 3 1 0 2 8 25 G 10 7 8 5 3 2 0 10 35 ? 從上表來看，應(yīng)選擇 D作為學(xué)校的地址，這樣最遠的居民區(qū)離學(xué)校的距離也只有 500米 . ? 在現(xiàn)實生活中，同一網(wǎng)絡(luò)中的各點要求提供的服務(wù)的數(shù)量也不盡 相同。應(yīng)此，我們引入兩個定義。為了提高服務(wù)效率，自然的想法是將 這些設(shè)施建立在中心地點。所謂中心選址問題就是在一個網(wǎng)絡(luò)中選擇一點，建立公用服務(wù)設(shè)施，為該網(wǎng)絡(luò)中的客戶提供服務(wù)，使得服務(wù)效率最高。試問 S到 T估計至少要行駛多少小時？并寫出最短路徑。即第 1年、第 3年個購買一臺新設(shè)備，或第 1年、第 4年各購買一臺新設(shè)備為最優(yōu)決策。 設(shè)備年齡 0— 1 1— 2 2－ 3 3— 4 4— 5 維修費 5 6 8 11 18 165941161722231718302341302231v1v2v3v4v6v5 ? 賦權(quán)圖如上圖所示，這樣設(shè)備更新問題就變?yōu)椋簭?v1到 v6的最短路問題。7)(P)(TT)11( 22 ?vv 最小，所以令標(biāo)號，比較所有7}16,8m i n {})(),(m i n {)( 52522 ????? fvPvTvT10}46,10m i n {})(),(m i n {)( 56566 ????? fvPvTvT11}66,11m i n {})(),(m i n {)( 57577 ????? fvPvTvT:,P)12( 6622 vvvv 的端點考察邊標(biāo)號的點為剛得到9}27,10m i n {})(),(m i n {)( 26266 ????? fvPvTvT11)( 7 ?vT11}39,11m i n {})(),(m i n {)( )13( 67677 ????? fvPvTvT11)( 7 ?? vP 9)( 6 ?? vP 迭代次數(shù) T(v0) T(v1) T(v2) T(v3) T(v4) T(v5) T(v6) T(v7)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1