某理工大學機電工程學院IE案例分析(PPT 84頁)

案例一：旅遊線路規劃
有如下問題需要解決：
現在要在以上各地方中的某一處修建一所會議中心，已知各個景點的員工分別是40,25,45,30,20,35,50，那麼會議中心應建在何處，能使各個景點的員工走的總路程最短？
為了保護園區野生生態環境，現在規定每條線路上觀光旅遊車的數量是一定的，見下圖，其中每條弧上的數字為通行車輛容量，那麼如何在不違背每條線路旅遊車輛數目限製下尋求最多的車輛通行？
電信公司需要安裝電話線路，聯通各個景點和進出口，則最小線路安裝是什麼？
顯然，第一個問題屬於最小樹生成問題，采用避圈法。
任選點S開始，離點S最近未連通是點Ａ，連通ＳＡ．
離點Ｓ或者點A最近未連通是點B（和點Ａ相連通），連通ＡB
離點Ｓ，Ａ或點B最近未連通是點C（和點Ｂ連通），連通ＢＣ
離點S，Ａ，B或者點C最近未連通是Ｅ（和點B連通），連通BE

..............................