冰淇淋車大作戰！用「旅遊小鎮」挑戰電腦也算不出來的難題(Dominating Sets)

在炎熱的夏天，沒有什麼比一支冰淇淋更棒了！

但對於「旅遊小鎮」的鎮長來說，這是一個頭痛的大問題。鎮上的街道錯綜複雜，他想在路口設置冰淇淋車，但他經費有限，買不起太多輛車。

他的目標是：用最少的冰淇淋車，讓每一個路口的居民，只要走一小段路（最多經過一條街道），就能買到冰淇淋。

這在電腦科學中被稱為「支配集 (Dominating Sets)」問題。這不是簡單的算數，而是一個連超級電腦都覺得棘手的「最佳化挑戰」。準備好你的籌碼，我們來幫鎮長省錢吧！

第一階段：製造衝突—— 貪心會吃虧？

首先，讓孩子憑直覺去解決問題，並體驗「直覺失效」的時刻。

第二階段：遊戲佈置 —— 視覺化的覆蓋範圍

為了讓「支配」的概念更具體，我們用顏色或籌碼來標記。

1. 準備道具：
   • 列印出地圖。
   • 準備約 20 個籌碼（或硬幣）代表冰淇淋車。
   • 準備另一種顏色的標記（如透明片或小積木）代表「被服務到的居民」。
2. 操作定義：
   • 當你把車放在路口 A，請把路口 A 以及所有連著 A 的路口都放上「被服務」的標記。
   • 目標是：地圖上不能有任何一個空白的路口。

第三階段：打破直覺，找到最佳解

這一步是引導孩子「反直覺思考」的關鍵。

1. 引導思考：
   • 「剛剛我們試過先搶『大路口』，結果失敗了。這次我們試試看別的策略。」
   • 「有沒有哪一個路口是『孤單又難搞』的？如果不專門為了它放一輛車，或是把車放在它隔壁，它就永遠吃不到冰淇淋？」
2. 尋找關鍵點：
   • 引導孩子觀察地圖邊緣那些連接數很少的路口。
   • 試著不要把車放在正中央，而是分散在四周的關鍵位置。
3. 成功時刻：
   • 經過反覆移動和調整，孩子最終會拼湊出一組「6 輛車」的完美解答。
   • 歡呼： 「哇！你辦到了！原本以為一定要佔領大路口，結果反而避開大路口才最省錢！」

第四階段：概念連結 —— 為什麼電腦覺得這很難？

• 家長：「你剛剛做的事情，就是電腦科學家在找的『最小支配集 (Minimum Dominating Set)』。這在真實世界超級有用！」
  • 手機基地台： 電信公司要設基地台，希望用最少的塔台，讓全台灣都有訊號。
  • 網紅行銷： 廠商想找幾個網紅宣傳產品，希望這幾個人的粉絲加起來能覆蓋所有年輕人。
• 深奧的理論 (NP-Complete)：
  • 「這張地圖只有幾十個路口，你花了 10 分鐘才找到答案。如果是全台灣的路口呢？」
  • 「這類問題最可怕的地方在於：要檢查你的答案對不對很簡單（算一下是不是 6 輛），但要『找到』這個最少數量的答案，卻超級無敵難！」這就是著名的 「NP 完全問題(NP-Complete) 」。
  • 這一類的問題，範圍從邏輯，鋸狀排列問題到地圖著色問題，在地圖上找最佳路徑，還有調度流程問題等等，問題可以說成千上萬。但令人驚訝的是，所有的這些問題已被證明是相同的：如果其中一個問題找到了多項式時間的演算法，那其他所有的問題就可以經由此演算法做轉換而一起解決—「要嘛就全部有解，要嘛就全部無解。」

第五階段：除錯與挑戰 —— 設計你的謎題

• 逆向工程 (One-way Function)：
  • 提問： 「解謎很難，但出題很簡單喔！你想不想考考爸爸媽媽？」
  • 做法：
    1. 先在白紙上畫 5 個紅點（對比冰淇淋車）。
    2. 隨意畫很多其他的黑點（對比路口）。
    3. 開始連線：確保每一個黑點都至少連到一個紅點。
    4. 最後，把紅點塗黑，變成一張普通的謎題地圖。
  • 挑戰： 把這張地圖交給別人，請他找出那 5 個紅點在哪裡。
  • 發現： 孩子會發現，自己「加密（出題）」只花 1 分鐘，但對方「解密（解題）」可能要花 1 小時！這就是現代密碼學的基礎概念。

教學觀察重點表

這張表幫助您觀察孩子是否跳脫了「貪婪」的直覺。

觀察點	❌ 較無效的反應 (只看結果)	✅ 較有效的引導 (探究思考)
當孩子堅持放在最大路口時	「那個位置不好，換一個。」	「這個位置看起來很棒，連到很多路。但你放了之後，剩下的那些角落好不好處理？你要不要試試看先處理難搞的角落？」
當孩子找不到 6 輛車的解法時	「答案是放在這幾個點…」	「如果我告訴你，這張地圖真的只需要 6 輛車，你覺得你是哪裡『浪費』了？有沒有兩輛車照顧到了同一群人？」
解釋為什麼這很難	「這叫 NP 問題，很複雜。」	「這就像是一個超難的數獨。電腦也沒有聰明的公式可以直接算出答案，它也只能像你一樣，一種一種慢慢試（暴力破解），試到天荒地老。」

後記

關於冰淇淋車問題，一件有趣的事情是，沒有人知道是否有一個尋找一組最佳解的演算法比暴力法明顯更快！暴力法花費的時間隨著交叉路口的數目呈指數增長—因此它又被稱為「指數時間演算法」（exponentialtime algorithm）。而相對於指數時間演算法，「多項式時間演算法」（polynomial-time algorithm）是指演算法的執行時間會隨著變數的平方、立方、十七次方或其他數目次方而增長。

多項式時間演算法，即使是十七次方，只要是夠大的地圖，也會比暴力法更快。因為指數級成長在它的參數大到一個程度時，一定會超過任何多項式級的成長（比方說，n¹⁷跟2ⁿ來比較，哪個比較大？在n大於117之後，後者就會超越前者）。那麼，是否有一個多項式時間演算法可以來尋找最少需要在哪些位置？目前還沒有人知道，但大家已經很努力的在找了。而對於一個比較容易的問題：檢查一組特定的位置是否是最佳解也是一樣，使用暴力法所花費的時間是呈指數成長，而針對此問題的多項式時間演算法，既沒有被發現，也沒有被證明不存在。

參考來源：CS Unplugged: Dominating Sets Teacher’s Supplement