ie案例分析培訓(xùn)教材(ppt84頁)-展示頁
2025-03-18 21:38本頁面
【正文】 點(diǎn)和進(jìn)出口，則最小線路安裝是什么？ ? 顯然，第一個(gè)問題屬于最小樹生成問題，采用避圈法。IE案例分析 王曉光 武漢理工大學(xué)機(jī)電工程學(xué)院 案例一：旅游線路規(guī)劃 某風(fēng)景區(qū)有五個(gè)景點(diǎn)見圖所示， S為景區(qū)入口， T為景區(qū)出口， A， B， C， D， E為五個(gè)景點(diǎn)。其中各個(gè)景點(diǎn)距離見圖標(biāo)。 ? 任選點(diǎn) S開始，離點(diǎn) S最近未連通是點(diǎn)Ａ，連通ＳＡ． ? 離點(diǎn)Ｓ或者點(diǎn) A最近未連通是點(diǎn) B（和點(diǎn)Ａ相連通），連通Ａ B ? 離點(diǎn)Ｓ，Ａ或點(diǎn) B最近未連通是點(diǎn) C（和點(diǎn)Ｂ連通），連通ＢＣ ? 離點(diǎn) S，Ａ， B或者點(diǎn) C最近未連通是Ｅ（和點(diǎn) B連通 ），連通 BE 案例一：旅游線路規(guī)劃 ? 離點(diǎn)Ｓ， A， B， C或者點(diǎn) E最近未連通是點(diǎn) D（和點(diǎn) E連通），連通 ED ? 未連通的只有點(diǎn)Ｔ（和點(diǎn)Ｄ最近連通），連通 DT。 對于上述問題 ， 在此模塊中新建一個(gè)最小樹的生成文件 。 點(diǎn)擊 “ Solve and Analyze” 求解。下面介紹采用迪克斯托標(biāo)號(hào)法進(jìn)行求解 。 例如如果Ｖ１ → Ｖ４ →Ｖ６ → Ｖ７是從Ｖ１到Ｖ７的最短路徑 ， 那么從Ｖ１到這條線路的任何一點(diǎn)都應(yīng)該是最短的 ， 不然就還存在其他最短路 。 ? 第二次迭代：計(jì)算與 A接近的各個(gè)點(diǎn)的臨時(shí)標(biāo)號(hào) ? T(D)=min[T(D),P(A)+W(AD)]=min[∞,9]=9 ? T(B)=min[T(B),P(A)+W(AB)]=min[5,4]=4 案例一：旅游線路規(guī)劃 ? 在以上 T標(biāo)號(hào)中， T(B)=4為最小，故將 B的永久標(biāo)號(hào)改為 P(B)=4 ? 第三次迭代：計(jì)算與 B接近的各個(gè)點(diǎn)的臨時(shí)標(biāo)號(hào) ? T(D)=min[T(D),P(B)+W(BD)]=min[9,8]=8 ? T(E)=min[T(E),P(B)+W(BE)]=min[∞,7]=7 ? T(C)=min[T(C),P(S)+W(BC)]=min[4,5]=4 案例一：旅游線路規(guī)劃 ? 在以上 T標(biāo)號(hào)中， T(C)=4為最小，故 P(C)=4； ? 第四次迭代：計(jì)算與 C想接近的 E的臨時(shí)標(biāo)號(hào) ? T(E)=min[T(E),P(C)+W(CE)]=min[7,8]=7 ? 所以 E的永久標(biāo)號(hào)為 P(E)=7； 案例一：旅游線路規(guī)劃 ? 第五次迭代：計(jì)算與 E接近的各點(diǎn)的臨時(shí)標(biāo)號(hào) ? T(D)=min[T(D),P(E)+W(ED)]=min[8,8]=8 ? T(T)=min[T(T),P(E)+W(ET)]=min[∞,14]=14 ? 故以上 T標(biāo)號(hào)中 T(D)=8為最小，故 P(D)=8 案例一：旅游線路規(guī)劃 ? 第六次迭代：計(jì)算出口點(diǎn) T的標(biāo)號(hào) ? T(T)= min[T(T),P(D)+W(DT)]=min[14,13]=13 ? 根據(jù)以上步驟，我們便可以知道最短路徑為： ? S→A→B→E→D→T 或者 ? S→A→B→D→T 案例一：旅游線路規(guī)劃 軟件實(shí)現(xiàn) ? 在 Ｗ inQSB軟件的 “ Net Problem Specification”模塊中 ， 新建一個(gè)最短路模型： 案例一：旅游線路規(guī)劃 案例一：旅游線路規(guī)劃 點(diǎn)擊 “ OK”后可以輸入數(shù)據(jù)。 案例一：旅游線路規(guī)劃 點(diǎn)擊 “ Solve” 求解。 案例一：旅游線路規(guī)劃 3. 現(xiàn)在要在風(fēng)景區(qū)中的某一處修建一所醫(yī)務(wù)中心，問應(yīng)建在何處，能使各個(gè)景點(diǎn)都離他最近？ ? 第三個(gè)問題屬于一個(gè)中心布點(diǎn)問題 。 分別求個(gè)點(diǎn)的最短路： 案例一：旅游線路規(guī)劃 點(diǎn)擊 “ Solve and Analyze” 求解。 案例一：旅游線路規(guī)劃 點(diǎn)擊 “ Solve and Analyze” 求解。 案例一：旅游線路規(guī)劃 點(diǎn)擊 “ Solve and Analyze” 求解。 案例一：旅游線路規(guī)劃 D=(dij) dij=max S A B C D E T S 0 2 4 4 8 7 13 13 A 2 0 2 3 6 5 11 11 B 4 2 0 1 4 3 9 9 C 4 3 1 0 5 4 10 10 D 8 6 4 5 0 1 5 8 E 7 5 3 4 1 0 6 7(min) T 13 11 9 10 5 6 0 13 案例一：旅游線路規(guī)劃 4. 現(xiàn)在要在風(fēng)景區(qū)中的某一處修建一所會(huì)議中心，已知各個(gè)景點(diǎn)的員工分別是40,25,45,30,20,35,50，那么會(huì)議中心應(yīng)建在何處，能使各個(gè)景點(diǎn)的員工走的總路程最短？ ? 該問題屬于求解網(wǎng)絡(luò)的重心問題。 ??ni 1qidi j案例一：旅游線路規(guī)劃 qidij S A B C D E T
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1