Learning Objectives
- 分辨多項式時間（n²、n³）與指數時間（2ⁿ、n!）的成長速度，估計實際要跑多久
- 寫出旅行推銷員問題的暴力解，說明要比較 (n-1)!/2 條路線
- 寫出最近鄰居啟發式，說明它很快但不保證找到最佳解
- 用子集和問題說明「驗證一個答案很容易」和「找出答案很困難」的差別
- 說出 P、NP、NP-complete、NP-hard 的意思，以及 P vs NP 為什麼重要、至今仍未解決
- 列出遇到難解問題時的實務做法：近似演算法、啟發式、限制輸入規模
有些問題，再快的電腦也算不完
一位送貨員要從倉庫出發，把貨送到 20 個地點再回來，怎麼排順序路程最短？這叫旅行推銷員問題（Traveling Salesman Problem，TSP）。 它聽起來和第 18 課的最短路徑很像，難度卻完全不同：最短路徑有 Dijkstra 這類有效率的演算法，旅行推銷員問題到今天還沒有人找到有效率的解法， 大多數學者相信根本不存在。
第 23 課的回溯法可以列出所有可能，但排列的個數是 n!，子集合的個數是 2ⁿ。這一課先看這兩種成長有多快， 再談電腦科學怎麼區分「容易」和「困難」的問題，以及遇到困難的問題時實際上怎麼辦。
| 名詞 | 意思 | 例子 |
|---|---|---|
| 多項式時間 | 步驟數是 n 的某個固定次方以內，例如 n、n log n、n²、n³ | 排序、二分搜尋、最短路徑 |
| 指數時間 | 步驟數像 2ⁿ、n! 這樣，n 加 1 就乘上一個倍數 | 列出所有子集合、所有排列 |
多項式與指數的成長速度
每一輪算出 n²、2ⁿ 與旅行推銷員要比較的路線數 (n-1)!/2，並假設電腦每秒能檢查 1 億條路線。n 從 15 變成 20，n² 還不到 2 倍，路線數卻從 435 秒的工作量變成約 6 億秒，也就是大約 19 年。C++ 與 Java 要用 long long／long，因為 19! 遠超過 int 的上限。
把數字換成時間
假設電腦每秒做 1 億次基本運算（這是很粗略的估計，只用來比較數量級）：
| 步驟數 | n = 20 | n = 50 | n = 100 |
|---|---|---|---|
| n² | 不到 1 秒 | 不到 1 秒 | 不到 1 秒 |
| n³ | 不到 1 秒 | 不到 1 秒 | 約 0.01 秒 |
| 2ⁿ | 約 0.01 秒 | 約 130 天 | 約 4 × 10¹⁴ 年 |
| n! | 約 770 年 | 約 10⁴⁹ 年 | 遠超過宇宙的年齡 |
電腦變快 1000 倍，對多項式時間的演算法很有用：n³ 的演算法能處理的 n 變成 10 倍。 對 2ⁿ 的演算法卻只能讓 n 多約 10（因為 2¹⁰ ≈ 1000）。所以電腦科學把「多項式時間能解決」當作有效率、容易處理（tractable）的分界線。
旅行推銷員問題的暴力解
最直接的做法：列出所有拜訪順序，算每一種的總長度，取最短的。這就是第 23 課的排列回溯法，多記住目前在哪個城市、走了多遠：
- 固定從 A 出發（從哪裡出發都是同一個環），剩下 n - 1 個城市的順序有 (n-1)! 種
- 同一條環狀路線順著走和倒著走長度一樣，所以不同的路線只有 (n-1)!/2 條
下面的範例有 4 個城市，距離寫在 dist 表格裡（dist[i][j] 是城市 i 到 j 的距離）。
暴力解：試遍所有拜訪順序
遞迴樹的 6 片葉子就是 6 種順序。看輸出：ABCDA 和 ADCBA 長度都是 144，它們是同一條環狀路線的兩個方向，所以 6 種順序其實只有 3 條不同的路線，也就是 (4-1)!/2 = 3。最短的是 144。
最近鄰居：快，但不一定最好
暴力解保證找到最短的路線，但 n 一大就跑不完。另一種做法是啟發式（heuristic）：用一個「看起來合理」的規則快速做出一個答案， 不保證最好。
最近鄰居（nearest neighbor）是最簡單的一種：從 A 出發，每一步都走到「最近、還沒去過」的城市，全部去過再回到 A。 這是第 20 課的貪婪演算法：每一步選眼前最好的，選了就不回頭。每一步要看一遍所有城市，n 步總共 O(n²)， 100 個城市也是一瞬間的事。
下面加入第 5 個城市 E，用最近鄰居走一次。
最近鄰居：每一步走到最近的城市
從 A 先走到最近的 B（20），再到 D（32）、E（30），最後只剩 C，只好從 E 走 67 到 C，再走 60 回 A，總長 209。用暴力解算這 5 個城市，最短的是 ABCDEA，長度 162：最近鄰居多走了約 29%。前面幾步貪近，把遠的 C 留到最後，就付出代價。
想一想：旅行推銷員問題
6 個城市的旅行推銷員問題，暴力解要比較幾條不同的路線？
關於最近鄰居啟發式，下面哪一個正確？
暴力解的範例印出 ABCDA：144 和 ADCBA：144，為什麼長度相同？
找答案很難，檢查答案很容易
子集和問題（第 23 課剪枝的那一題）：給一些整數和一個目標，能不能挑出幾個數，總和剛好等於目標？ 不靠任何技巧時，只能把 2ⁿ 個子集合一個一個試。
可是，如果有人遞給你一組答案（例如「選 3、4、2」），檢查它對不對只要把幾個數加起來，O(n) 就做完了。 這組可以拿來檢查的答案叫證書（certificate）。旅行推銷員問題也一樣：「有沒有總長 ≤ 170 的路線？」很難回答， 但有人給你一條路線，你只要確認每個城市剛好去一次、把距離加起來和 170 比一比。
下面的範例用 mask 的二進位代表子集合：第 i 位是 1 就表示選了 nums[i]，mask 從 0 數到 2ⁿ - 1 就列出了所有子集合。
子集和：求解要試 2ⁿ 個，驗證只要加一次
4 個數有 2⁴ = 16 個子集合，程式全部試過，找到 7 2 和 3 4 2 兩組。最後驗證別人給的答案 [3, 4, 2]，只加了 3 個數。數字變成 60 個時，求解要試 2⁶⁰（超過 10¹⁸）個子集合，驗證仍然只要加 60 次以內。
P、NP 與 NP-complete
電腦科學用「是／否」形式的問題（判定問題）來分類難度，例如「有沒有總長 ≤ K 的路線？」「有沒有總和剛好等於目標的子集合？」
| 類別 | 意思 | 例子 |
|---|---|---|
| P | 可以在多項式時間內解決 | 排序、最短路徑、「這個數在不在已排序的陣列裡」 |
| NP | 答案是「是」的時候，有證書可以在多項式時間內驗證 | 子集和、旅行推銷員（判定版）、數獨、所有 P 的問題 |
| NP-complete | 屬於 NP，而且 NP 裡每一個問題都可以在多項式時間內轉換成它 | SAT（布林可滿足性）、子集和、旅行推銷員（判定版）、漢米爾頓迴路 |
| NP-hard | 至少和 NP-complete 一樣難，但不一定屬於 NP | 旅行推銷員的最佳化版本（找出最短路線本身） |
注意：NP 不是「non-polynomial」的縮寫，是 nondeterministic polynomial time，意思接近「猜對了就能在多項式時間內確認」。
Cook–Levin 定理：Stephen Cook 在 1971 年證明 SAT 是 NP-complete，Leonid Levin 也獨立得到相同的結果（1973 年發表）。 有了第一個 NP-complete 問題以後，要證明別的問題也是 NP-complete，只要把一個已知的 NP-complete 問題轉換過去就行。 Richard Karp 在 1972 年用這個方法一口氣證明了 21 個問題是 NP-complete，包括背包問題、團（clique）、漢米爾頓迴路等。
NP-complete 問題彼此是綁在一起的：只要其中任何一個找到多項式時間的演算法，所有 NP 的問題都有，也就是 P = NP。 反過來，只要證明其中一個不可能有，就是 P ≠ NP。
P vs NP：「能快速驗證的問題，是不是都能快速解決？」這個問題至今沒有人證明或否證。 它是克雷數學研究所（Clay Mathematics Institute）在 2000 年公布的七個千禧年大獎難題之一，解出任何一題的獎金是 100 萬美元。 大多數研究者相信 P ≠ NP，但這只是猜想。現在廣泛使用的公開金鑰密碼，也建立在「某些問題很難解」的假設上。
遇到 NP-hard 的問題怎麼辦
知道一個問題是 NP-hard，不代表放棄，而是知道「不要再找又快又保證最好的通用解法」，改用下面的做法：
| 做法 | 意思 | 例子 |
|---|---|---|
| 限制輸入規模 | n 很小時，指數時間也跑得完 | 10 個城市用暴力解；動態規劃（第 21 課）可以把 n! 降到約 n² × 2ⁿ，20 個城市約 4 億步 |
| 啟發式 | 快速找到不錯的答案，不保證最好 | 最近鄰居；再加上「交換兩段路線看會不會變短」的局部改善 |
| 近似演算法 | 有證明的保證：答案不會比最佳解差超過某個倍數 | 城市間的距離滿足三角不等式時，Christofides 演算法（1976）保證不超過最佳解的 1.5 倍 |
| 剪枝的精確搜尋 | 回溯法加上聰明的剪枝，實際資料常常很快 | 第 23 課的剪枝；整數規劃求解器 |
| 利用特殊結構 | 實際的輸入常常不是最壞情況 | 城市都在一條直線上時，問題就變簡單了 |
物流排程、晶片佈線、排課、蛋白質結構預測等實務問題，很多都是 NP-hard，靠的就是這些方法的組合。
想一想：P 與 NP
下面這段程式數一數 [1, 2, 3, 4] 有幾個子集合的總和是 5，會印出什麼？
「NP」這個名稱的意思是什麼？
如果有人找到子集和問題（NP-complete）的多項式時間演算法，會有什麼結果？
一個問題是 NP-hard，實務上比較合理的做法是哪一個？
實作：驗證一條路線
這是 NP 的「驗證」：給一條路線和上限 K = 170，在多項式時間內檢查它是不是一張合格的證書。請完成 verify：先確認每個城市剛好去一次，再算總長和 K 比較。城市 A～E 的距離和最近鄰居範例相同。
重點整理
- 多項式時間（n²、n³）在 n 變大時仍然可行；指數時間（2ⁿ、n!）在 n 只有幾十時就算不完
- 旅行推銷員的暴力解要比較 (n-1)!/2 條路線；最近鄰居是 O(n²) 的貪婪啟發式，快但不保證最短
- 驗證一個答案（證書）常常很容易，找出答案卻可能很難
- P：能快速解決；NP：能快速驗證；NP-complete：NP 裡最難的一群，彼此可以互相轉換；NP-hard：至少一樣難
- Cook–Levin 定理：SAT 是 NP-complete（Cook 1971；Levin 獨立得到，1973 年發表）
- P vs NP 是千禧年大獎難題之一，至今沒有解決
- 實務上：小規模精確求解、大規模用近似演算法或啟發式，或利用輸入的特殊結構
這是演算法軌的最後一課。從搜尋、排序、資料結構、圖、貪婪、動態規劃、回溯到難解問題，你已經看過分析一個問題的完整工具箱： 先問「有沒有更好的方法」，也知道什麼時候該問「是不是根本沒有更好的方法」。