前幾篇，我們一路從 dependency、propagation 談到 Graph 本身也可能隨著系統執行而改變。
到這裡，我們已經不只是在描述資料結構，也開始面對更接近現實系統的問題。
而接下來要換一個角度：
當可以做的選擇不只一個時，我們到底該選哪一個？
前面的搜尋問題裡，我們經常是在找：
但很多現實問題不只要求「找到一個答案」。
我們還希望：
這個答案夠好
今天先從一個非常生活化的例子開始：
找零錢
假設現在要找 67 元，手上可以使用的硬幣面額是：
50、10、5、1
如果問題只是：
能不能湊出 67 元？
其實答案非常多。
例如：
50 + 10 + 5 + 1 + 1
可以。
但：
10 + 10 + 10 + 10 + 10 + 10 + 5 + 1 + 1
也可以。
甚至全部使用 1 元：
1 + 1 + 1 + ... + 1
一共 67 枚，也能完成。
所以我們想解的通常不是怎麼湊出 67 元，而是：
在可以湊出 67 元的前提下，盡可能減少使用的硬幣數量
這時，問題裡就多了一個東西：
最佳化目標（objective）
也就是：
我們到底想讓什麼變得更好？
在這個問題裡：
如果你真的拿著：
50、10、5、1
這些面額，要湊出 67 元，你大概不會先把所有可能的找零方式全部寫在紙上。
我們很自然會這樣想：
67 元
先拿一枚不超過 67 的最大硬幣：
50
剩下 17。
接著，在不超過 17 的硬幣裡選最大的：
10
剩下 7。
再選：
5
剩下 2。
接著就是：
1
1
整個過程變成：
剩下 67 → 選 50
剩下 17 → 選 10
剩下 7 → 選 5
剩下 2 → 選 1
剩下 1 → 選 1
剩下 0 → 完成
最後得到：
50 + 10 + 5 + 1 + 1
總共 5 枚硬幣，這種思考方式非常自然。
因為我們每一步都只問一個很簡單的問題：
現在看起來，哪個選擇最好？
這類策略通常稱為：
Greedy Algorithm，貪婪演算法
Greedy 的核心想法其實非常直白：
每一步，都做目前看起來最好的選擇
在找零問題裡目前最好可以理解成：
在不超過剩餘金額的前提下，先拿最大的硬幣。
所以：
67 → 50
17 → 10
7 → 5
2 → 1
1 → 1
我們沒有先知道完整答案。
也沒有先列出所有可能的硬幣組合，再從裡面挑最好的。
我們只是：
做一個選擇
↓
問題變小
↓
再做下一個選擇
↓
問題再變小
直到問題被解完。
Greedy 裡有一個非常重要的概念：
局部選擇（local choice）
也就是：
只根據目前的狀態，選擇眼前最好的選項
例如現在剩下 17，我們不會先思考後面所有可能：
10 + 5 + 1 + 1
5 + 5 + 5 + 1 + 1
10 + 1 + 1 + 1 + 1 + 1 + 1 + 1
...
而是直接說：
目前最大的可用硬幣是
10
所以選 10，接著再處理剩下的 7，這就是所謂的局部選擇：
現在的狀態
↓
選現在最好的
↓
進入下一個狀態
Greedy 並不是站在終點把整條路全部看完，再決定第一步。
它比較像是：
一路往前做看起來最划算的決定
因為我們平常做決策時，其實很少真的把「所有可能」全部展開。
想像今天午餐附近有100 家餐廳。
理論上，你可以研究：
甚至把所有可能全部比較完再做決定。
但現實中很少有人真的這麼做。
我們更可能是：
不要太遠
↓
看起來不錯
↓
價格可以接受
↓
就這間
因為：
找出絕對最好的答案，本身也需要成本
這裡的午餐例子不是在說這就是 Greedy，Greedy 是在這個前提下，進一步給出一套明確規則：
每一步都按照某個局部標準，選擇目前最好的選項
假設有很多個選擇：
A
B
C
D
E
...
每做完一個選擇，又會產生下一層選擇。
如果我們真的試圖把所有可能全部列出來，可能會變成：
Start
/ | \
A B C
/|\ /|\ /|\
... ... ...
選擇越多，可能性也可能快速增加。
Greedy 的思考方式則完全不同，它不會把整棵可能性全部展開。
而是：
Start
↓
當下最好
↓
當下最好
↓
當下最好
↓
答案
因此 Greedy 最吸引人的地方就是：
我們不需要先把所有可能答案找出來，才開始做選擇。
每一步只需要處理目前的狀態。
以前面的找零問題來說：
// 假設硬幣已經按照面額由大到小排列
const coins = [50, 10, 5, 1];
function makeChange(amount) {
const result = [];
for (const coin of coins) {
while (amount >= coin) {
result.push(coin);
amount -= coin;
}
}
return result;
}
console.log(makeChange(67));
結果：
[50, 10, 5, 1, 1]
這段程式真正值得看的並不是語法。
而是它背後的決策規則：
從最大的硬幣開始
↓
能拿就拿
↓
再處理剩下的金額
我們甚至沒有建立 所有可能的找零方式 這份資料。
因為 Greedy 根本沒有打算比較所有完整答案。
當我們一開始拿下 50 面額之後，我們並沒有打算再回頭說：
等一下，也許剛剛不要拿
50比較好。
我們直接接受這個選擇，然後繼續解：
17
也就是說，典型的 Greedy 思路是：
做出眼前這一步的選擇
↓
接受這個選擇
↓
繼續處理剩下的問題
它不像某些搜尋策略會：
試一下
↓
發現不好
↓
退回去
↓
換另一條路
而是傾向於：
做完選擇，就繼續往前
這也是它為什麼簡單。
但這件事同時也埋下了一個很重要的問題。
看到找零問題之後，很容易把 Greedy 記成：
每次選最大的
但這並不精確，Greedy 真正的概念是：
每一步選擇目前看起來最符合目標的選項
在找零問題裡，我們希望：硬幣數量越少越好。
因此「優先拿大面額硬幣」看起來很合理。
但換一個問題，Greedy 每一步採用的選擇規則可能完全不同。
例如，如果我們希望：成本最低。
那可能每次選：目前最便宜的。
如果我們重視的是：越早完成越好。
可能優先選：最快能完成的。
如果我們想要：取得最大收益。
眼前這一步的選擇又可能變成：目前收益最高的。
所以 Greedy 不是某一個固定規則。
更準確地說，它是一種解題策略：
先定義什麼叫「更好」
↓
據此決定每一步要怎麼選
↓
每一步選當下最好的
到這裡，我們其實已經慢慢離開前幾篇主要討論的世界了。
前面的問題，很多時候是在問：
但接下來，我們會越來越常遇到另一類問題：
有很多可行答案
↓
但它們並不是一樣好
↓
那我們應該怎麼選？
這時候，問題的重點開始從 找到答案 走向 根據某個目標選擇答案。
因為它有幾個非常實際的優點。
有些問題甚至真的可以靠一連串當下看起來最好的選擇，得到整體最好的答案。
所以 Greedy 的核心精神是：
如果問題的結構允許我們只看眼前，就沒有必要把所有可能性全部找出來
真正困難的是去判斷：
我們怎麼知道這個問題允不允許？
現在回到我們找零的過程：
67 → 50
17 → 10
7 → 5
2 → 1
1 → 1
每一步看起來都非常合理。
因為當下最大的硬幣，似乎都能讓剩餘金額下降得最快。
也就是：
每一步，我們都做了當下最好的選擇
但是我們真正想達成的整體目標是：
最後使用的硬幣總數最少
這是最後用來衡量整個答案好壞的標準。
於是 Greedy 最核心的問題也出現了：
當下最佳
↓
當下最佳
↓
當下最佳
↓
?
整體最佳
我們現在其實偷偷做了一個很大的假設：
如果每一步都選得最好，最後的答案應該也會最好。
聽起來非常合理，甚至合理到我們平常根本不會懷疑它。
但演算法真正有趣的地方，往往就是從這些「看起來理所當然」的地方開始。
找零只是讓 Greedy 的直覺非常容易被看見。
真正重要的是這個思考模式：
有很多可能答案
↓
先定義什麼叫「更好」
↓
不想把所有答案全部列出來
↓
所以每一步選目前最好的
↓
繼續處理剩下的問題
這就是 Greedy 最核心的精神：
透過一連串當下看起來最好的選擇，希望得到一個好的整體結果
它之所以重要，就是因為：
簡單、快速，而且非常符合人的決策直覺
但也正因如此，我們很容易忽略那個最重要的問題：
每一步都選眼前最好的，看起來很合理；但這樣得到的結果，真的永遠是整體最好嗎？
iThome鐵人賽
看影片追技術