高考申論題
114年
[工業工程] 作業研究
第 三 題
某新設大學欲在主要建築物間鋪設光纖網路，以使主要建築物間網路能夠通連。下圖結點為需通連光纖網路的各建築物，圖中各結點間弧上之數字為各建築物間鋪設光纖網路所需之距離。請求解應如何鋪設光纖網路方可使鋪設總距離最短？（最終答案需寫出那些結點必須相連及其總距離）。（15 分）
(圖形節點 1-8 及其弧權重如下：
1-2: 4, 1-3: 8, 1-4: 9
2-3: 5, 2-4: 4, 2-5: 7
3-5: 2, 3-6: 5
4-5: 6, 4-7: 10, 4-8: 11
5-6: 2, 5-7: 5
6-7: 2
7-8: 4)
📝 此題為申論題
思路引導 VIP
看到這類要求使所有節點連通且總距離最短的考題，應立刻聯想到網路模型中的「最小生成樹（Minimum Spanning Tree, MST）」問題。解題時可直接套用 Kruskal's 演算法（依權重由小到大排序選邊）或 Prim's 演算法（由節點出發逐步擴展），並留意在試卷上展示完整的挑選過程、確認不產生迴圈，最後加總邊長即可。
🤖
AI 詳解
AI 專屬家教
【解題思路】本題要求鋪設最短總距離使所有建築物網路連通，屬於求解「最小生成樹（Minimum Spanning Tree）」問題，可採用克魯斯克爾演算法（Kruskal's Algorithm）依權重逐步挑選邊來求解。 【詳解】 已知：圖中共有 8 個結點（$n=8$），要將所有結點連通且無迴圈，最小生成樹需挑選 $n-1=7$ 條邊。將圖中各邊的距離（權重）由小至大排序如下：2(3-5, 5-6, 6-7) < 4(1-2, 2-4, 7-8) < 5(2-3, 3-6, 5-7) < 6(4-5) ...等。
▼ 還有更多解析內容