網(wǎng)路模型networkmodels-資料下載頁
2025-08-01 13:59本頁面
【正文】 小展開樹之問題 (Minimal Spanning Tree)昰一種網(wǎng)路架構(gòu)，此網(wǎng)路中之所有節(jié)點必須互相連結(jié)，並且無循環(huán) (loop)產(chǎn)生 ? 一個展開樹 (Spanning Tree)昰以 (n1)個弧來連接 n個節(jié)點的網(wǎng)路 ? 一個網(wǎng)路可以有非常多個展開樹，但只有一個最小展開樹 (Minimal Spanning Tree) 37 最小展開樹 ? 問題定義 (p. 280) – 有 n個節(jié)點 . – 由節(jié)點 i至節(jié)點 j弧的距離為 dij – 目標：找出一組弧 (Arcs)，能以最短距離將所有節(jié)點連接起來成一個展開樹 38 大都會捷運問題 THE METROPOLITAN TRANSIT DISTRICT 39 大都會捷運問題 THE METROPOLITAN TRANSIT DISTRICT ? 溫哥華城市計劃興建一捷運系統(tǒng)來連接八個住宅與商業(yè)中心 ? 捷運公司必須以最少成本將所有地點連接起來 40 大都會捷運問題 – 網(wǎng)路示意圖 ? 網(wǎng)路示意圖包含 : – 規(guī)劃可行路線 – 每條路線最低建築成本 41 5 2 6 4 7 8 1 3 West Side North Side University Business District East Side Shopping Center South Side City Center 50 34 35 39 45 41 42 SPANNING TREE NETWORK PRESENTATION 5 2 6 4 7 8 1 3 West Side North Side University Business District East Side Shopping Center South Side City Center 50 34 35 39 45 41 43 ? 求解 – 網(wǎng)路求解 (見光碟中補充講義 Supplement CD 5) ? 網(wǎng)路算則採用貪婪法 ”greedy procedure”. ? The algorithm – 第一種形式 (version 1) – 選取最短距離之弧，放入已選取弧之集合 (a set of selected arcs) – 每次反覆中 ， 將下一個最短距離之弧加入已選取弧之集合 ， 但避免產(chǎn)生 Cycle – 重複上列敘述 ， 直到所有節(jié)點都被連接起來為止 THE METROPOLITAN TRANSIT DISTRICT 44 ? The algorithm – 第二種形式 (version 2) – 選取最短距離之弧，放入已連結(jié)弧之集合 (a set of connected arcs) – 每次反覆中，自未選取之弧集合 (unselected arcs)中，加入與已連結(jié)集合有連結(jié)之最短弧，但要避免產(chǎn)生Cycle – 重複上列敘述 ， 直到所有節(jié)點都被連接起來為止 ? 請見第二種形式之展示 THE METROPOLITAN TRANSIT DISTRICT 45 Shopping Center Loop 2 6 4 7 8 West Side North Side University Business District East Side South Side City Center 50 34 35 39 45 41 Total Cost = $236 million OPTIMAL SOLUTION NETWORK REPRESENTATION 5 1 3 46 Shopping Center 4 7 8 West Side North Side University Business District East Side South Side City Center 50 34 35 39 45 41 Total Cost = $236 million OPTIMAL SOLUTION NETWORK REPRESENTATION 5 3 1 6 2
規(guī)章制度相關(guān)推薦
鄂ICP備17016276號-1