地特三等申論題
114年
[工業工程] 作業研究
第 三 題
三、某新設大學欲在主要建築物間鋪設光纖網路，以使主要建築物間網路能夠通連。下圖結點為需通連光纖網路的各建築物，圖中各結點間弧上之數字為各建築物間鋪設光纖網路所需之距離。請求解應如何鋪設光纖網路方可使鋪設總距離最短？（最終答案需寫出那些結點必須相連及其總距離）。（15 分）
📝 此題為申論題
思路引導 VIP
本題為網路流模型中的「最小生成樹（Minimum Spanning Tree, MST）」問題。題目要求以最短總距離使所有結點（建築物 1 至 8）相連（通連）。可使用 Kruskal 演算法或 Prim 演算法求解。因本題圖形較單純，推薦使用 Kruskal 演算法：將所有邊按距離（權重）從小到大排序，依序挑選不會形成「環路（Cycle）」的邊，直到選滿 $n-1$ 條邊為止（本題 $n=8$，故需選 7 條邊）。
🤖
AI 詳解
AI 專屬家教
【考點分析】 最小生成樹（Minimum Spanning Tree, MST）之求解、Kruskal 演算法。 【理論/法規依據】
▼ 還有更多解析內容