在電腦科學中，有一個很經典的問題叫做「最小生成樹 (Minimal Spanning Tree)」。聽起來很深奧，但它的核心觀念其實就是：「如何用最少的材料，把所有人都連接起來？」
今天我們不寫程式，我們要進入一個剛下過大雨的「泥濘城市」。我們要邀請孩子擔任市長，解決市民的困擾，而且只要他能成功省下預算，城市裡就能多蓋一座游泳池！
第一階段：爛泥巴與游泳池的抉擇
首先，我們用故事創造情境，讓「最佳化 (Optimization)」變成一種迫切的需求。
- 情境設定：
- 拿出「泥濘城市」的地圖（圖上有許多房子和虛線道路）。
- 故事：「很久以前，有一個沒有鋪路的小城市。每次下過大雨，這裡就變成爛泥巴地，車子會卡住，大家的鞋子都會髒掉」。
- 任務：「你是新上任的市長。市民拜託你把路鋪好，讓每一個房子都可以通到其他任何一個房子」。
- 關鍵衝突：
- 「但是，鋪路的石頭很貴！市庫的錢本來是要拿來蓋一座大游泳池的」。
- 「如果你把每一條路都鋪滿，錢花光了，游泳池就沒了。你的挑戰是：用最少的石頭，把所有房子連起來，省下來的錢就拿去蓋泳池！」。
第二階段：視覺化的成本
我們要讓「長度」變成看得見的「數量」。
- 準備道具：
- 列印出上方的地圖，準備約 40 個黑色籌碼（或是圍棋子、小積木、真正的石頭）。
- 或利用下方的遊戲。
- 規則解說：
- 地圖上房子之間的方格子，代表那條路的長度。
- 鋪路方式：拿出籌碼把格子填滿，就代表這條路鋪好了。格子越多，代表路越長，要花的錢（石頭）就越多。
- 目標：請孩子試著在紙上擺放籌碼，直到所有房子都「連通」，並計算用了多少顆石頭。
第三階段：Kruskal 的鋪路魔法
孩子一開始可能會隨意亂連，或連成一個圓圈。這時我們要引導出電腦科學家的策略（Kruskal 演算法）。
- 直覺嘗試：
- 讓孩子先試一次。他們可能用了 25 顆石頭。
- 家長：「25 顆… 好像有點貴，游泳池只能蓋一半。我們能不能更節省一點？」
- 引導策略：
- 家長提問：「既然我們要省錢，我們應該先鋪『長的路』還是『短的路』？」
- 孩子：「短的！因為用的石頭少。」
- 執行魔法：
- 「好！我們現在眼睛掃描整張地圖，哪裡的路最短？」
- 孩子會找到那些只有 2 格或 3 格的路。
- 「把它鋪起來！」（放上籌碼）。
- 接著找「第二短」、「第三短」的路，依序鋪下去。
- 關鍵判斷：
- 當孩子想鋪某一條路時，請他暫停一下。
- 提問：「等等！這兩個房子，透過別條路已經可以通了嗎？」
- 觀察： 如果房子 A 和房子 B 早就連通了（繞遠路也能到），這條新路就是「浪費錢的捷徑」。
- 家長指令：「既然已經通了，這條路雖然短，但我們不鋪！省下來！」。
- 結果揭曉：
- 依照這個「先挑便宜的鋪、不鋪重複的路」的規則做到底。
- 最後算出石頭總數（最佳解通常會比孩子亂試的少很多）。
- 歡呼：「恭喜市長！你成功用最少的石頭連通了全城，游泳池經費有著落了！」
第四階段：概念連結
- 家長：「你剛剛用的這個超省錢策略，是一個叫 Kruskal 的人發明的（Kruskal 演算法）。你覺得除了鋪馬路，還有什麼東西也需要這樣『連在一起但越短越好』？」
- 引導思考：
- 電力公司：電線要連到每一家，電線越短越省錢。
- 自來水管：水管要接通全城，管子越少越不容易漏水。
- 網際網路：電腦網路的連線也要講究效率。
- 專有名詞：這個連出來的形狀，電腦科學家叫它「最小生成樹 (Minimal Spanning Tree)」。
- 最小：花費最少（長度最短）。
- 生成：連接了所有的點。
- 樹：因為沒有繞圈圈（迴路），看起來像樹枝一樣分岔出去。
第五階段：除錯與挑戰
在這個階段，我們要引入真實世界的挑戰。我們要讓孩子理解，有時候「省錢（最小生成樹）」不一定代表「方便」或「快速」。
- 挑戰一：窮遊背包客 vs. 轉機惡夢 (Travel Budget vs. Convenience)
- 情境：「假設有一家『小氣航空公司』，為了省油錢，他們決定照著我們剛剛畫的『最小生成樹』地圖來開飛機航線。因為這樣總飛行距離最短，最省油。」
- 提問：「如果你想從地圖最左邊的城市，飛到最右邊的城市去旅行，看著這張地圖，你會發現什麼問題？」
- 發現：孩子會發現可能要轉機很多次！因為為了省鋪路的錢，中間的捷徑都被我們「省」掉了，必須繞著樹枝狀的路線飛。
- 總結：對航空公司來說，這是成本最低的蓋法（最小生成樹）；但對趕時間的旅客來說，這不是最好的路線。這就是為什麼真實世界的機票和路線規劃，不能只看「總長度」，還要考慮「方不方便」。
- 挑戰二：披薩外送員的惡夢 (The Travelling Salesman Problem)
- 情境：「恭喜市長，你用最少的石頭把路鋪好了！現在，城市裡的披薩店開幕了。外送員騎著機車，要一次把披薩送到地圖上的每一戶人家，最後回到披薩店」。
- 實驗：「請你拿出你的手指頭當作機車，試著在我們剛剛鋪好的『省錢道路（最小生成樹）』上跑跑看。規則是：你要拜訪每一家，但盡量不要走回頭路。」
- 發現（衝突點）：孩子會發現非常困難！因為最小生成樹有很多「樹枝的末端（死巷子）」。
- 外送員騎進去送完披薩後，必須「原路折返」才能出來，再去送下一家。
- 這對鋪路來說很省石頭，但對外送員來說非常浪費油和時間！
- 總結與知識點：
- 定義問題：這個「如何規劃路線，才能拜訪每一個點再回到原點，而且路徑最短」的問題，電腦科學家稱之為「旅行推銷員問題 (Travelling Salesman Problem, TSP)」。
- 區分差異：
- 最小生成樹 (MST)：幫電力公司省電線、幫市長省鋪路費（只要連通就好，不用繞圈）。
- 旅行推銷員 (TSP)：幫物流司機、航空郵件省油錢（需要一個高效率的迴圈）。
- 未解之謎：你覺得 TSP 很難畫嗎？告訴你一個秘密，對於這個問題，電腦科學家到現在還沒找到一個「夠快又保證是最佳解」的超級公式！這可是電腦界最難的挑戰之一喔。
教學觀察重點表
| 觀察點 | ❌ 較無效的反應 (只看結果) | ✅ 較有效的引導 (工程師思維) |
| 當孩子連成一個圓圈時 | 「錯了，不能有圓圈。」 | 「看這裡，如果我已經可以從A家走到B家，再鋪這條路是不是就『多餘』了？市長，這條路的錢能不能省下來去買滑水道？」(強調避免迴路 Cycle) |
| 當孩子問為什麼不鋪捷徑 | 「因為那樣石頭會變多。」 | 「如果你是旅客，你會很想要這條捷徑。但你是市長，這條路要多花市民 5 億元。你現在要選擇『讓大家方便』還是『幫大家省稅金』？電腦科學就是在做這種取捨。」 |
| 解釋物流車為什麼不能用這張圖 | 「因為樹狀圖有死路。」 | 「你試著用手指當貨車開開看。你會發現一直要『倒車』出來對不對？所以送貨的路線（TSP）跟鋪路的路線（MST）是不一樣的數學問題喔！」 |