上一篇，我們看到一個很現實的問題：

理論上存在答案，不代表我們能在現實時間內找到答案

像 Knapsack、Scheduling、Routing 這些問題，真正困難的地方是：

可能的答案實在太多了

當資料量增加，可能組合有時會快速成長，最後甚至出現 Combinatorial Explosion。

這時我們就會遇到一個很工程的問題：

如果找到「完美答案」需要一個小時，但十秒內其實可以找到一個非常不錯的答案，我們應該選哪一個？

這也是今天要談的主題：

為什麼工程師常常願意接受「夠好的答案」？

理論上的最好，可能不是現實中的最好

假設今天你要從台北開車到高雄，導航系統必須替你找到一條路。
我們可能會想：

那當然就是找最快的路啊

但「最快」其實沒有想像中簡單，因為道路上可能同時存在：

• 目前車流
• 事故
• 施工
• 紅綠燈
• 收費
• 道路限制
• 預測中的壅塞
• 使用者是否願意走高速公路
• 是否避開收費道路

如果真的想找到一條「絕對完美」的路線，理論上可能要考慮大量可能路徑，以及各種未來可能發生的變化。

但你打開 Google Maps 時，不可能接受這樣的體驗：

正在計算最佳路線...

預計剩餘時間：17 小時

你真正需要的是：

幾秒鐘後，給我一條合理的路

這裡開始出現了一個非常重要的工程 trade-off：

答案品質
    ↕
計算成本

我們當然希望答案越好越好，但答案本身並不是唯一成本。

Exact Algorithm：真的把最佳答案找出來

有些演算法可以保證：

找到符合定義的正確答案，甚至是最佳答案

這類方法可以稱為 Exact Algorithm。
例如前面介紹 BFS 時，在一張沒有權重的 Graph 中：

從 A 到 F 最少經過幾條 edge？

BFS 可以保證找到 shortest path。
Dijkstra 在 edge weight 都是非負的情況下，也可以找到最低 cost 的路徑。

這些情況非常理想：

問題規模可負擔
+
有明確演算法
+
演算法可以在合理時間完成

那我們當然沒有理由故意接受比較差的答案。

所以：

「接受夠好」不代表工程師不在乎正確

影響我們的問題是：

當精確解的計算成本開始高到無法接受時，怎麼辦？

Exact 不只是「會不會算」，還要問「多久算完」

假設現在有 30 個工作，要安排給不同機器。
每個工作都有：

• 執行時間
• 機器限制
• 到期時間
• 優先級

我們希望找到：

所有可能安排中，整體完成時間最短的方案

最直接的方法之一，就是把所有可能安排都試過一次。
如果只有三個工作，可能還沒什麼。
但工作數量增加後，可能組合會快速膨脹。

於是我們得到一個很奇怪的情況：

• 演算法是正確的
• 答案也是最佳的

可是它算不完。
更精準一點說，不一定是真的「永遠算不完」，可能只是三天後會算完。
但如果這是一個每五分鐘都要重新安排工作的系統，那三天後得到答案，跟沒有答案其實差不多。
這就是 計算成本 Computational Cost

它可能包括：

• CPU time
• memory
• network
• energy
• money
• latency

演算法不是活在紙上的，它最後必須跑在真正的機器上。

一個晚到兩小時的完美答案，還是好答案嗎？

想像你正在叫外送，平台要決定：

這張訂單應該交給哪一個外送員？

如果平台希望找到數學上最完美的 global assignment，它可能需要同時考慮：

• 幾千名外送員
• 幾千張訂單
• 每個人的位置
• 道路狀況
• 餐點準備時間
• 目前工作量
• 未來可能出現的新訂單

假設經過大量計算後，系統真的找到了一個完美分配。

但計算花了 20 分鐘，問題是這 20 分鐘裡：

• 外送員已經移動了
• 新的訂單進來了
• 舊訂單取消了
• 餐廳出餐了
• 道路開始塞車了

於是那個「完美答案」算出來的瞬間，可能已經不再適用。
這時真正合理的目標反而可能是：

在 200 ms 內找出一個足夠好的安排

因為在這種系統裡答案品質不是唯一的最佳化目標，還有回應的時間要考量。

Heuristic：不要把所有可能都看完

當我們無法負擔 exhaustive search 時，其中一種常見做法就是使用：

Heuristic 啟發式

啟發式可以先理解成：

根據問題特性設計一套規則，快速找到一個看起來合理的答案

我們其實在 Day 22 的 Bin Packing 已經看過類似概念。
例如貨物依序送進來時。
可以使用 First Fit：

從第一個箱子開始找，只要裝得下就放進去

或者 Best Fit：

找目前裝得下，而且剩餘空間最小的箱子

它們都沒有：

列出所有可能分法
→ 比較全部答案
→ 證明自己是最佳

而是利用一套規則，快速做決策。
這也是啟發式很重要的特徵：

我們犧牲某些 optimality guarantee，換取更低的計算成本

Heuristic 不等於「隨便猜」

看到這裡，很容易產生一個誤解：

• Exact Algorithm → 嚴謹
• Heuristic Algorithm → 憑感覺亂猜

其實不是，一個好的 heuristic 通常仍然建立在這些基礎之上：

• 問題結構
• domain knowledge
• 經驗資料
• 統計特徵

例如導航系統可能知道：

• 這條道路目前塞車
• 這條高速公路通常比較穩定
• 某些小路雖然距離短，但實際速度很慢

這些資訊都可以幫助搜尋系統：

不要浪費時間探索那些明顯不值得的方向

所以 heuristic 的核心並不是隨便猜，而是：

我知道完整搜尋成本太高，因此利用問題特性，把計算資源集中在比較有希望的地方

Approximation 又是什麼？

除了 heuristic 之外，還有另一個常出現的詞：

Approximation Algorithm 近似演算法

兩者有點相似，因為都可能不追求 exact optimum。
但可以先用一個非常簡化的方式理解差異。
Heuristic 比較像：

我有一套方法，可以很快找到通常不錯的答案

Approximation Algorithm 則更強調：

我雖然不一定找到最佳答案，但我可以對答案離最佳有多遠提供某種保證

例如假設真正最佳成本是 100，某個 approximation algorithm 可能保證：

我找到的答案，不會比最佳答案差超過某個比例

這比單純說通常表現不錯，多了一層理論上的保證。
不過這個系列不需要深入 approximation ratio 或相關證明。

現在只需要先抓住這個差別：

• Exact → 我要最佳答案
• Approximation → 我接受不是最佳，但希望知道最差會差多少
• Heuristic → 我利用經驗或結構快速找到實務上不錯的答案

它們沒有誰比較高級，也不用踩一捧一：

不同問題條件下，選擇不同程度的保證

Google Maps 真的需要證明這是「唯一完美路線」嗎？

回到導航，假設系統告訴你：

• 路線 A：2 小時 03 分
• 路線 B：2 小時 05 分

即使某個龐大的最佳化程序最後可以證明：

在目前模型、所有可能路線與所有已知條件下，A 是全域最佳解

對使用者來說，這個證明真的很重要嗎？

很多時候未必，你在乎的可能是：

• 不要繞太遠
• 不要塞得太誇張
• 不要算太久
• 最好能隨路況重新調整

也就是：

Google Maps 不需要證明這是全世界所有可能條件下的唯一完美路線，只需要在合理時間內，給你一條夠好的路

這裡的「夠好」其實非常重要。
因為它不是偷懶，是問題定義的一部分。

「夠好」必須先回答：多好才算夠？

工程師會受不了需求方說：

差不多就好

真正的工程問題通常會變成：

• 答案最多可以差多少？
• 計算最多可以花多久？
• 多少 memory 可以接受？
• 結果多久必須更新一次？

例如推薦系統可能接受：

不是理論上最完美的推薦組合，但必須在 100 ms 內回傳

排班系統可能接受：

不保證總成本最低，但不能違反任何勞動限制

物流系統可能接受：

路線可以比最佳路線多 3%，但計算時間必須控制在數秒內

你會發現連「演算法本身」都開始受到限制條件影響。

限制條件不只決定答案，也限制我們找答案的方法

前面 Day 26 談限制滿足問題時，我們主要把限制條件放在答案上。

例如：

• 同一間實驗室不能重複借用
• 實驗室安全容量必須足夠
• 共同修課的學生不能撞堂
• 教師、助教與實驗室的時段都必須允許

但今天可以再深入一點。
真實系統還有另一組限制條件：

• 服務不能卡住 30 秒
• 記憶體不能無限使用
• 雲端運算不能無限花錢
• 裝置的電量有限

所以一個工程系統其實同時存在兩層問題：

• 問題本身的限制條件：限制什麼答案可以成立
• 計算資源的限制條件：限制我們用什麼方式尋找答案

這就是為什麼：

在紙上可以解的問題，到了 production system 裡可能要完全換一種思考方式

「最好的演算法」本身也需要最佳化目標

一路講到這裡，我們其實又回到了 Day 11。

當時我們問：

DFS 和 BFS 到底哪個比較好？

答案是：

你到底想找到什麼？

後來 Day 27 又看到：

推薦系統的「最好」取決於最佳化目標

現在這個問題可以再往上一層：

演算法本身，什麼叫最好？

是答案最接近 optimum？
還是執行最快？
還是最省記憶體？
還是最容易維護？
還是結果雖然差一點，但每次都可以在 50 ms 內完成？

很多時候，我們真正想最佳化的是：

答案品質
+
Latency
+
Resource Usage
+
Maintainability
+
Reliability

而不是單獨其中一項。

所以工程師是在放棄最佳答案嗎？

不是。

更精確的說法是：

工程師必須先判斷「最佳」到底值不值得付出它的成本

如果 exact algorithm 可以 10 ms 內找到最佳答案，那當然使用精確解。
但如果資料規模增加後變成：10 小時。
而 heuristic 可以：在 200 ms 得到 98% 品質的答案，那麼真正要考量的是：

剩下那 2% 的改善，值不值得多花將近 10 小時？

這才是實際系統必須回答的問題。

工程是在限制下做合理選擇

我們一路從資料結構走到演算法，表面上似乎一直在問：

怎麼找到答案？

但真正貫穿整個系列的，其實是另一個問題：

在目前的條件下，我們應該怎麼描述問題，並選擇一個合理的方法？

Queue 不是永遠比 Array 好。
Hash Map 不是永遠比 Array 好。
BFS 不是永遠比 DFS 好。
Greedy 不是永遠正確。
Exact Algorithm 也不是永遠值得使用。

因為每一種選擇背後，都存在：

• 限制條件
• 最佳化目標
• 成本
• trade-off

所以真正的系統除了問「最佳解是什麼」，還必須考慮：

• 多久要得到答案？
• 有多少計算資源？
• 資料會不會繼續改變？
• 答案過多久就失效？
• 多一點準確度值不值得多十倍成本？

工程問題通常沒有永遠最好的資料結構、演算法或架構。真正有意義的問題是：

在目前的限制條件下，哪一種選擇比較合理？

有時候合理的選擇是 exact。
有時候是 approximation。
有時候是 heuristic。
有時候甚至只是：

先給出目前最合理的答案，等世界改變後再重新計算

而這最後一點，也讓我們準備回到整個系列一開始埋下的另一條線。
前面我們看過：

• Graph
• dependency
• propagation
• dynamic relationship

也看過現實世界中的資料與條件並不會永遠保持不變。

如果一個系統不是：

收到輸入
→ 算一次答案
→ 結束

而是：

資料改變
→ 找出受影響的部分
→ 重新計算
→ 再次等待下一次改變

那麼我們面對的，就不再只是一個單次執行的演算法問題。

而是一個：

持續對變化做出反應的系統