前幾篇，我們遇到了很多看起來不太一樣的問題。

例如：

• Knapsack：行李只能帶 20 公斤，哪些東西最值得帶？
• Scheduling：一天只有有限時間，工作應該怎麼安排？
• Matching：這些人與工作，應該怎麼分配？
• Routing：有很多地點需要經過，怎麼走成本最低？

推薦系統甚至還會同時考慮：

• 相關性
• 多樣性
• 新穎性
• 使用者投入程度
• 營收

這些問題有一個共同點：

答案往往不只一個

我們需要從大量可能的答案中，找到既符合限制條件，又能讓最佳化目標表現足夠好的那一個。

問題是，如果我們真的把所有可能答案都算過一次，會發生什麼事？

最直覺的方法：全部試一次

假設今天有 5 件物品 A、B、C、D、E。
Knapsack 要做的事情，是決定：

哪些物品要帶，哪些不要帶？

每件物品都有兩種選擇：

• 帶
• 不帶

所以 5 件物品會有：

2 × 2 × 2 × 2 × 2
= 2⁵ = 32

32 種組合，看起來完全沒問題。
甚至我們真的可以把全部組合列出來，再逐一檢查：

• 重量有沒有超過限制？
• 總價值是多少？

最後挑出價值最高的答案。
這種方式很單純：

把所有可能答案找出來，再選最好的

這通常被稱為 Brute Force。
而且它有一個非常大的優點：

只要我們真的把所有可能都檢查完，就不容易漏掉最佳答案

5 件只有 32 種，那 50 件呢？

如果有 10 件物品：

2¹⁰ = 1,024

20 件：

2²⁰ = 1,048,576

30 件：

2³⁰ ≈ 10 億

到了 50 件：

2⁵⁰ ≈ 1,125,899,906,842,624

已經超過：

一千兆種組合

當你發現物品數量增加 1，組合直接乘以 2，這時候的對應關係就不再是單純：

10 件 → 10 種
20 件 → 20 種

是轉向指數增長：

10 件 → 約 1 千種
20 件 → 約 100 萬種
30 件 → 約 10 億種
40 件 → 約 1 兆種

這就是今天第一個重要概念：

Search Space

Search Space：我們到底要從多少答案裡面找？

Search Space 可以先很直覺地理解成：

一個問題所有可能候選答案所形成的空間

例如 Knapsack 的考量是：

每件物品帶 / 不帶

所以 n 件物品大約有 2ⁿ 種選擇。
但不同問題的 Search Space，增長方式可能完全不同。

假設今天不是選東西，而是安排 10 件工作的執行順序。
第一個位置有：10 種選擇。
選完之後，第二個位置剩：9 種。
接著：

8
7
6
...

最後可能的排列數量就是：

10!

稍微複習一下數學表示意思：

10 × 9 × 8 × ... × 1
= 3,628,800

光是 10 件工作，就有超過 360 萬種順序。

20 件呢？

20!
≈ 2.43 × 10¹⁸

這已經不是電腦算快一點就好了的問題了。

Routing 也有同樣的問題

想像物流公司今天要經過很多個配送地點。
我們已經知道每兩個地點之間的距離，也知道怎麼計算一條路線的總成本。

例如：

A → B → C → D

我們可以計算這條路線需要多少公里。

另一條：

A → C → B → D

也可以算，所以問題並不是：

我們不知道怎麼計算一條路線的成本

真正麻煩的是：

可能的路線太多了

如果我們想用最單純的方法找最佳路線：

列出所有可能路線
→ 計算每條路線成本
→ 選最小的

理論上完全合理。
但是當節點增加，可能排列也會快速增加。

於是問題開始從：

怎麼算這個答案？

變成：

我們真的有時間把所有答案都算過一次嗎？

這兩件事情考量完全不同。

「知道怎麼算」跟「算得完」是兩回事

假設一台電腦每秒可以檢查 1,000,000 個候選答案。
100 萬看起來很多。
如果總共有 10 億個答案，大概需要 1000 秒。
還算可以想像，但如果是 10¹⁵ 個答案呢？
即使每秒檢查 100 萬個，也需要 10⁹ 秒，也就是數十年。
如果 Search Space 再繼續增加，甚至可能需要幾千年、幾百萬年。
這時候演算法是正確的和這個演算法實際上能用，已經變成兩件不同考量的事情。

這就是 Combinatorial Explosion

這種情況通常會用一個很形象的詞來描述：

Combinatorial Explosion 組合爆炸

意思是：

當問題規模稍微增加，可能組合的數量卻以非常快的速度膨脹

例如：

2ⁿ 或 n! 這類增長速度，和我們前面常看到的：

n
n log n
n²

有很大的差距。
想像資料量增加一倍，如果成本大約是 O(n)，工作量大致增加一倍。
如果是 O(n²) 可能增加四倍。
但如果是 O(2ⁿ) 增加的級距就完全不同了。
因為每多一個元素，Search Space 都可能再次翻倍。

限制條件可以幫我們排除答案，但不一定能救我們

Day 26 的實驗課排程問題裡，我們談過限制條件。

例如：

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

這些條件可以幫我們排除大量不合法答案。

例如原本有 1,000,000 種安排，經過限制條件檢查之後，也許只有 5,000 種是真正的可行解。
看起來 Search Space 好像縮小很多。
但問題是：

我們怎麼知道哪 5,000 種是合法的？

如果最單純的方法仍然是：

先產生一百萬種可能 → 每一種都檢查限制條件

那前面的成本還是存在。
所以限制條件雖然能描述：

什麼答案可以接受

卻不代表：

我們一定可以很快找到它

找到答案，和驗證答案，也可能是不一樣的問題

這裡可以非常輕地碰一下電腦科學裡一組很有名的概念：

P
NP

這兩個詞背後其實有完整的 Complexity Theory，我們這個系列不會深入。
現在只需要理解有些問題，我們不只可以快速驗證答案，也可以快速找到答案。

可以把 P 很粗略地理解成：

存在有效率演算法，可以在問題規模增加時仍以 polynomial time 求解的問題

例如很多排序、最短路徑問題，都有我們實際可以使用的高效率演算法。

而 NP 可以先建立另一個理解：

如果有人先給我們一個候選答案，我們可以在 polynomial time 內驗證它是不是正確

一個簡單的直覺

假設有人告訴你：

我找到一個符合所有條件的實驗課表

我們可以檢查：

• 實驗室有沒有重複借用？
• 共同修課的學生有沒有撞堂？
• 實驗室安全容量夠不夠？
• 教師、助教與實驗室的時段能不能配合？

驗證一份已經存在的實驗課表，可能沒有那麼困難。
真正困難的是：

如果什麼都還沒有，要怎麼從大量可能安排中找到這份實驗課表？

這就是為什麼：

我可以快速確認答案

不一定等於：

我可以快速找到答案

那 NP-hard 又是什麼？

這裡還有一個常出現的詞：

NP-hard

同樣不需要背正式定義。
在這個系列裡，可以先把它理解成：

有一類問題困難到，目前沒有已知的方法可以保證對所有輸入都快速找到最佳答案

例如我們前面談過的某些問題版本：

• Knapsack 最佳化問題
• Travelling Salesman Problem
• 許多 Scheduling problems
• 許多 Routing problems

都可能落在這類困難問題附近。
但這裡要特別注意：

「Scheduling」或「Routing」本身不是一個單一問題。

條件不同，複雜度也可能完全不同。
有些版本很好解，有些版本卻會變得非常困難。
所以我們不能看到排程、路線、最佳化，就直接說：

這一定是 NP-hard

真正決定難度的，仍然是：

你到底怎麼定義問題

NP-hard 並不是「電腦算不出來」

這也是一個很常見的誤解。
NP-hard 並不代表無解，也不代表電腦永遠算不出來。
小規模問題，我們完全可能直接算完。
例如只有 10 個配送地點，Brute Force 或更聰明的演算法也許完全足夠。
但如果變成：

100 個
1,000 個
10,000 個

問題就可能完全不同。
所以真正重要的是：

問題規模

同一個演算法 n = 10 可能瞬間完成。
到了 n = 100,000 卻可能完全不可行。

Complexity 真正想告訴我們的，不只是電腦要跑多久，還有：

當問題規模變大時，計算成本會用什麼速度增加？

這也解釋了為什麼 Big-O 重要

Day 1 我們第一次提到 Big-O 時，關心的是：

資料量增加之後，操作成本怎麼變化？

到了今天，可以看到它背後更深的一層意義。

我們分析複雜度時，其實是在問：

這個方法能不能跟著問題規模一起成長？

假設兩個演算法處理 10 筆資料時：

Algorithm A：0.001 秒
Algorithm B：0.01 秒

A 看起來比較快。

但如果：

A → O(2ⁿ)
B → O(n²)

當 n 開始變大，結果可能完全反過來。

所以演算法分析的意義是：

資料再增加下去會發生什麼事？

前面那些問題，其實現在串起來了

回頭看 Day 19 之後的內容。
Greedy 告訴我們：

不一定要把所有組合都試過，可以每一步先做局部選擇

但 Day 20 又看到：

Local Optimum 不一定是 Global Optimum

Knapsack 告訴我們：

當選項可以自由組合時，Search Space 可能快速增加

Bin Packing 告訴我們：

有時候最佳答案太貴，我們會使用 heuristic

Scheduling 告訴我們：

時間本身也是限制條件

Matching 告訴我們：

人與工作之間也存在大量可能組合

限制滿足問題告訴我們：

有時甚至還沒開始找最好，就得先找到一個合法答案

多目標最佳化又告訴我們：

「最好」可能同時包含很多互相衝突的最佳化目標

到了今天，還多了一個問題：

即使我們已經知道「最好」是什麼，我們真的算得出來嗎？

真實世界通常沒有時間等我們找到完美答案

假設今天是一套餐廳外送系統。

理論上，我們可以考慮：

所有外送員
×
所有訂單
×
所有可能配送順序
×
所有可能路線
×
未來可能出現的新訂單

然後找出一個真正的 Global Optimum，也許那會是數學上最漂亮的答案。
問題是：

• 使用者還在等餐
• 外送員的位置還在變
• 新的訂單還在進來
• 餐廳可能正在延遲出餐
• 道路狀況也可能改變

即使你真的有辦法在 3 小時後，算出一個完美答案，而那個答案可能早就失去意義了。
所以現實系統裡，一個答案除了好不好之外，往往還有另一個非常重要的考量：

多久能算出來

計算時間，本身也是限制條件

這時我們其實可以把問題再重新描述一次。
以前我們可能追求最大化答案品質，但真實世界可能更接近：

最大化答案品質

限制條件：

computation time < 500 ms

也就是：

計算資源本身，也是一種有限資源

CPU 有限、Memory 有限、時間有限，系統必須在某個 deadline 之前做出決定。
這時候 完美但算不完的答案，可能還不如** 100 毫秒內可以算出的夠好答案**。
這也讓「最佳」這個詞，再一次變得沒有那麼單純。

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

一個問題可能：

• 有明確規則
• 有合法答案
• 有清楚的最佳化目標
• 甚至知道怎麼逐一檢查所有可能

但仍然可能在實際規模下難以求解。
因為真正阻擋我們的，不一定是：

不知道怎麼算

更可能只是：

要算的東西太多了

這也是為什麼資料結構與演算法不糾結在找到一個能得到答案的方法。
還必須繼續問：

• 這個方法需要多少時間？
• 需要多少空間？
• 問題規模增加後還能不能使用？
• 我們真的需要完美答案嗎？

因為在真實工程裡：

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

而這也留下了下一個很實際的問題：

如果完美答案的計算成本高到無法負擔，工程上是否應該接受一個能及時算出的「夠好答案」？