從這篇文章開始, 我們就開始程式設計上的藝術道路. 你沒有看錯, 很多人將演算法稱為藝術, 因為他們認為演算法太優美了, 根本就不像是科學. 然而, 演算法確實又可以解決實際問題

說到實際問題, 我們很多時候都需要將其建模為數學模型, 然後採用數學的方法來求解. 對於電腦中的實際問題, 就更需要這樣. 因此, 我們需要引入一個來自數學的概念 : 最佳化

給定一個函數 f, 其定義域為 D_{f}, 值域為 R_{f}. 尋找一個元素 x_{0} \in D_{f}, 對於所有 x \in D_{f}, 使得 f(x_{0}) \leq f(x) (最小化) 或 f(x_{0}) \geq f(x) (最大化)

上面的表述方法不是非常嚴格, 但是已經具有嚴謹性. 這是因為《數學分析》系列的文章我們暫時還沒有講到這個部分. 絕大多數的問題都可以建模到上述的一般性框架 : 定義域 D_{f} 就是這些問題的限制條件, 值域 R_{f} 稱為問題的可行解. 函數 f 稱為目標函數 (代價函數), 最小化或最大化 f(x_{0}), x_{0} \in D_{f} 稱為問題的最佳解

例 1. [渴嬰問題] 一個口渴而聰明的嬰兒想要解渴, 他可以得到 n 杯飲料. 但是每一杯飲料的量不同, 不妨設為 a_{1}, a_{2}, ..., a_{n}. 但是有一些飲料並不好喝, 因此嬰兒要想解渴, 可能需要組合多種飲料, 並且為每一種飲料指派一個滿意度 : s_{1}, s_{2}, ..., s_{n}. 如果嬰兒需要飲用 t 個單位的量才可以解渴, 那麼怎麼獲得最大的滿意度呢?

x_{i} 是嬰兒飲用第 i 種飲料的量, 滿意度函數 s(\mathscr {X}) = s(x_{1}, x_{2}, ..., x_{n}) = s_{1}x_{1} + s_{2}x_{2} + ... + s_{n}x_{n} = \sum \limits_{i = 1}^{n}s_{i}x_{i} 為這個問題的目標函數. 該問題的限制條件為 \sum \limits_{i = 1}^{n}x_{i} = t0 \leq x_{i} \leq a_{i}, 其中, i = 1, 2, ..., n. 任何滿足該限制條件的一組實數解 \mathscr {X} 都是該問題的可行解, 能夠使得滿意度函數 s(\mathscr {X}) 取得最大值的一組實數解 \mathscr {X} 稱為這個問題的最佳解. 特別指出, 若有 \sum \limits_{i = 1}^{n}a_{i} < t 成立, 那麼此問題無解

例2. [找零錢問題] 一個小孩用 1 美元來購買不足 1 美元的糖果, 假設有數量不限的面值為 25 美分、10 美分、5 美分以及 1 美分的硬幣 (1 美元 = 100 美分). 售貨員如何用數目最少的硬幣給孩子找錢?

設 25 美分的硬幣用量為 x_{1}, 10 美分的硬幣用量為 x_{2}, 5 美分的硬幣用量為 x_{3}, 1 美分的硬幣用量為 x_{4}. 求和函數 s(\mathscr {X}) = s(x_{1}, x_{2}, x_{3}, x_{4}) = \sum \limits_{i = 1}^{4}x_{i} 稱為這個問題的目標函數. 設應該找錢的數量為 R 美分, 該問題的限制條件為 R = 25x_{1} + 10x_{2} + 5x_{3}+x_{4}x_{i} \geq 0, 其中, i = 1, 2, 3, 4. 任何滿足該限制條件的一組實數解 \mathscr {X} 都是該問題的可行解, 能夠使得求和函數 s(\mathscr {X}) 取得最小值的一組實數解 \mathscr {X} 稱為這個問題的最佳解

在上面這些問題中, 我們通常選取一個總策略, 然後分步解決, 每一步都得到最佳解, 最後將解集合併得到最終的解. 這就是貪婪演算法的核心思想

貪婪演算法 : 對於某一個問題, 選取一個標準策略. 在每一步中都在標準策略的指引下作出最佳決策, 並在之後步驟中不再更改. 最終合併這些最佳策略形成問題的解. 稱這個標準策略為貪婪策略

在生活中, 我們幾乎都在使用貪婪演算法解決實際問題 :

  • 我們遇到了任務過多的情況, 這個時候我們會優先選取緊急度較高或者限時較短的任務來完成. 而 "優先選取緊急度較高或者限時較短的任務" 就是貪婪策略. 每完成一個任務, 我們都在貪婪策略下作出了該步之下的最佳決策, 並且在之後步驟中不再更改, 並且不可再更改. 當完成每一個任務的時候, 我們就在貪婪策略的指引下, 得到了最終解
  • 我們遇到在某個房間內裝入所有我們需要的傢俱, 這個時候我們會優先選取實用度較高的傢俱而放棄一些觀賞性的傢俱. 而 "優先選取實用度較高的傢俱而放棄一些觀賞性的傢俱" 就是貪婪策略. 每裝入一個傢俱, 我們都在貪婪策略下作出了該步之下的最佳決策, 並且在之後步驟中不再更改. 當完成裝入所有傢俱的時候, 我們在貪婪策略的指引下得到了最終解
  • ...

在上面這些例子中, 我們都選取了最佳的貪婪策略或者接近最佳解的貪婪策略. 但是貪婪策略遠不止於最佳或接近最佳, 也可以是最差的策略. 比如第一個情況, 我們完全可以選擇優先處理那些比較簡單的任務作為貪婪策略; 對於第二個情況, 我們可以選擇優先放入觀賞性較高的傢俱作為貪婪策略. 但是通常實際問題的限制會更加嚴格, 我們可能會遇到任務多但是時間少的問題, 而房間的面積必定也是有限的. 我們通常會綜合所有情況, 選擇出最佳的貪婪策略

貪婪演算法為什麼是貪婪的呢? 就是因為它在每一步作出決策之後, 之後都不可更改. 貪婪體現在這裡. 如果你還無法理解的話, 再次聯繫一下生活. 你為了提高生活質量, 你使用了信用卡添置了很多能夠讓你生活質量提高的物品, 但是你卻忘了你可能無法按時還款的事實. 你貪圖一時之爽快, 導致了無法預計的後果, 這也許就是貪婪最本質的體現 : 只考慮當時的最佳解, 而無法顧全大局

對於貪婪演算法的細節, 我總結一下上述所說過的步驟 :

  1. 將實際問題建模為數學問題. 找到目標函數和限制條件
  2. 將這個大問題分解為若干個小問題
  3. 選取貪婪策略
  4. 在貪婪策略的指引下找到若干個小問題的最佳解
  5. 合併若干個小問題的最佳解得到問題的解

現在, 我要是說貪婪演算法得到的並不一定是最佳解, 你也許可能理解了. 那麼如果我們得到了最佳解, 如何證明它就是使用貪婪演算法得到的這個問題的最佳解呢? 答案是使用數學方法進行證明 (直接證明、列舉法、歸納法和歸謬法等)

這裡要特別重提一下歸納法, 有些人可能已經有了解, 在文章《【初等數學】數學初步 (上篇)》中, 我已經要求大家掌握大部分證明方法. 歸納法是間接的證明方法. 首先檢驗解對於歸納變數 n 的一個或者多個基礎值是最佳解 (通常是 n = 0 或者 n = 1 的時候); 然後假設當歸納變數 n 小於或者小於等於 k 的時候 (k 大於任意基礎值或至少與那個最大的基礎值相等), 解仍然是最佳解; 最後根據前面的假設證明當 n = k 或者 n = k + 1 的時候, 解仍然是最佳解. 最終, 這個解就是這個問題的最佳解. 歸納法總共有三個步驟 : 歸納基礎、歸納假設和歸納步驟. 有時候歸納步驟可能需要歸謬法的配合, 因為直接證明可能有些困難, 我們需要反向証明

作為實例, 我們求解找零錢問題. 找零錢問題使用了直接證明, 如果大家需要查看歸納證明的實例, 大家可以首先去搜尋一些實例. 之後的文章中, 會大量使用歸納法和歸謬法

我們規定貪婪準則為 不超過要找的零錢總數的條件下, 每一次都選擇盡可能大的面額

斷言 : 使用這個貪婪準則, 每次都可以得到最佳解

證明 :

x_{1}, x_{2}, x_{3}, x_{4} 是貪婪演算法所產生的 25 美分、10 美分、5 美分和 1 美分所需要的數量, y_{1}, y_{2}, y_{3}, y_{4} 是最佳解下 25 美分、10 美分、5 美分和 1 美分所需要的數量. 記 R_{0} 為還需要找的零錢數量

根據貪婪準則, 我們可以知道,

  • 0 < R_{0} < 5, 至大可以選擇 1 美分進行找零, 至多使用四個 1 美分進行找零
  • 5 \leq R_{0} < 10, 可以用 5 美分和 1 美分進行找零, 至多使用一個 5 美分和四個 1 美分進行找零
  • 10 \leq R_{0} < 25, 可以用 10 美分、5 美分和 1 美分進行找零, 至多使用兩個 10 美分和四個 1 美分進行找零
  • 25 \leq R_{0} < 100, 可以使用全部面額的進行找零

綜合上面三點, 我們可以得到 y_{4} < 5, y_{3} < 2, y_{2} < 3. 若有 y_{4} \geq 5, 那麼我們至少可以使用一個 5 美分替代五個 1 美分; 若有 y_{3} \geq 3, 那麼我們至少可以提供一個 10 美分用於替換兩個 5 美分; 若有 y_{2} \geq 3, 那麼我們至少可以提供一個 25 美分以及一個 5 美分用於替換三個 10 美分. 由於小女孩只用了 1 美元付款, 因此自然有 y_{1} < 4. 其中, y_{i} \geq 0, i = 1, 2, 3, 4. 所以, s(\mathscr {Y}) = s(y_{1}, y_{2}, y_{3}, y_{4}) = \sum \limits_{i = 1}^{4}y_{i} 可以提供最少數量的零錢

不妨設 x_{1} \neq y_{1}, 那麼最佳解或者由貪婪演算法得到的解至少要提供一個 25 美分用於替換超出的部分, 否則違反了上述結論. 對於 x_{2} \neq y_{2}x_{3} \neq y_{3} 和 x_{4} \neq y_{4} 也有相同的結論

綜上所述, 有 x_{1} = y_{1}x_{2} = y_{2}x_{3} = y_{3} 和 x_{4} = y_{4}, 即貪婪演算法產生的解就是最佳解

但是有一些問題並不總能使用貪婪演算法得到最佳解, 也就是說, 貪婪演算法得到的解可能只能夠接近最佳解, 這樣的貪婪演算法稱為啟發式演算法. 自然地, 我們知道, 啟發式演算法都是相對於最佳化的演算法而言的. 因此, 啟發式演算法雖然不能在最佳時間內獲得解, 但是也可以在我們可接受的時間範圍內獲得解. 如若啟發式演算法的性能和最佳化演算法的性能有著一定的關係, 那麼我們也稱這個啟發式演算法為近似演算法. 啟發式演算法通常都是憑藉生活經驗而得的, 也就是我們憑藉生活經驗大致知道這樣去做可以高效地解決這個問題. 但這也導致了一個另外一個問題, 就是我們幾乎沒有辦法證明它可能有時候會得到最壞的解. 但是通常它都會在我們可以接受的時間範圍內得到解

這其中, 就包含了臭名昭著的 NP 問題. 首先, 我需要讓大家知道, 什麼是 P 問題、NP 問題、NP-困難 (NP-Hard) 問題和 NP-完全 (NP-Complete) 問題. 這還得從當今電腦的架構開始說起. 當今電腦的架構基本都是決定性的架構, 那什麼又是決定性的架構呢? 就是給定一定的狀態以及一些資料, 電腦下一步該做什麼有且唯有一種可能. 想像一下你自己所寫的程式碼, 是不是這樣的. 如果你有系統地學習過作業系統, 那麼你肯定認同我的說法. 與決定性架構相對應的就是非決定性的架構. 非決定性架構的電腦具有一定的自主選擇能力. 在給定一定的狀態和資料的情況下, 它能夠自己選擇下一步應該做什麼. 因此, 在解決計算問題上, 非決定性架構的電腦具有更快的計算速度, 因為它和人類一樣是智慧地解決問題, 而並非機械地解決問題

定義 1. [P 問題] 給定任意問題和對應演算法, 若決定性架構的電腦可以在多項式時間內完成計算, 那麼稱這個問題是 P 問題. P 是 Polynomial 的縮寫. 多項式時間 T(n) 可以表示為

T(n) = a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{2}n^{2} + a_{1}n + a_{0}

目前我的文章中, 所有已經講到的演算法都是多項式時間內可以完成計算的演算法

定義 2. [NP 問題] 給定任意問題和對應演算法, 若決定性架構的電腦無法或不確定是否可以在多項式時間內計算完成, 但是非決定性架構的電腦可以在多項式時間內計算完成, 那麼稱這個問題是 NP 問題. NP 是 Non-deterministic Polynomial 的縮寫

定義 2'. [NP 問題] 給定任意問題及其一組解, 如果決定性架構的電腦可以在多項式時間內驗證其是否成立, 那麼稱這個問題是 NP 問題

定義 2' 是定義 2 在數學上的一個等價判定方法, 定義 2 是從問題出發, 定義 2' 是從解出發

定義 3. [P = NP?] 給定任意 NP 問題及對應演算法, 若決定性架構的電腦可以在多項式時間內解決該問題, 那麼稱這個 NP 問題也為 P 問題, 即 P = NP

對於 NP 問題來說, 如果決定性架構的電腦都可以在多項式時間內解決這個問題, 那麼非決定性架構的電腦必然也可以在多項式時間內解決這個問題. 但是到目前為止, 無法證明所有的 P 問題都是 NP 問題, 也無法證明所有的 P 問題都不是 NP 問題. 因此 P = NP? 的證明是世紀性的難題. 估計大家都對 RSA 加密演算法有所了解, 如果某一天 P = NP 得證, 那麼幾乎所有加密演算法都會在多項式時間內被破解. 換句話說, 破解 RSA 加密演算法只需要使用決定性架構的電腦就可以了. 從另一個角度來看, 這是人類計算能力的飛躍

在人類解決 P = NP? 的過程中, 提出了一個過渡性的概念, 就是 NP-完全問題

定義 4. [NP-Complete 問題] 給定一個 NP 問題, 在決定性架構的電腦下, 若其它 NP-問題都可以在多項式時間內化約到這個問題

NP-Complete 問題定義的提出是為了找到一個渠道, 間接地證明 P = NP. 若某個 NP-Complete 問題被證明在決定性架構的電腦下有多項式時間複雜度的演算法, 那麼 P = NP 對任意問題都成立. 不嚴格地說, NP-Complete 問題是最不可能屬於 P 問題的, 即 NP-Complete 問題是 NP-問題中最難的問題

定義 4. [NP-Hard 問題] 給定一個 NP 問題, 在決定性架構的電腦下, 若它能夠在多項式時間內化約為另一個等價問題, 那麼稱這個問題為 NP-Hard 問題

可以看到, NP-Complete 問題只是 NP-Hard 問題的其中一個特例. 對於 NP-Hard 問題來說, 決定性架構的電腦也不一定可以在多項式時間內驗證其解是否正確. 即使 P = NP 成立, 但是 NP-Hard 問題仍然不一定存在多項式時間複雜度可解的演算法. 因此, NP-Hard 問題至少和 NP-Complete 問題一樣難

目前, 大多數人都相信 P ≠ NP, 也就是說有如下圖成立 :

若有一天 P = NP 得證, 那麼就有如下圖成立 :

對於暫時沒有找到多項式時間內可解的 NP 問題, 又回到了我們的主題, 就是使用貪婪演算法來解決問題. 我們可以憑藉著生活中的經驗, 制定貪婪準則, 在可接受的時間範圍內尋找能夠接近最佳解的近似解. 因此, 貪婪演算法常常被用於 NP 問題中