摘要訊息 : 當下過得舒服就很不錯了, 至於以後?

0. 前言

人生有很多岔路口, 大家在人生的路上也會不斷面臨選擇. 這些選擇有時候會引導你走向人生高峰, 有時候會導致你跌入人生低谷. 也就是說, 人對未來都是未知的, 但是人又是貪婪的. 我們都希望做出的選擇不斷帶領我們走向人生高峰, 而不是跌入低谷. 於是, 在做出選擇的時候, 我們通常選擇那些當下看起來最好的選擇, 儘管當幾十年後, 我們可能突然發現選擇另外一條路就可以令我們的人生更加精彩.

在解決問題的時候, 我們也會應用這種理念, 選擇哪些看起來能夠導致最佳化的步驟. 這就是貪婪演算法的雛形.

更新紀錄 :

• 2022 年 5 月 12 日進行第一次更新和修正.

1. 貪婪演算法

定義 1. 給定一個函數 f : x \rightarrow R_{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) (最大化).

我們稱根據定義 1 尋找 x_{0} 的過程稱為最佳化 (mathematical optimization).

定義 1 雖然不嚴格, 但是具有一定的嚴謹性. 絕大多數問題都可以化約為最佳化問題 : 定義域 D_{f} 就是這些問題的限制條件 (limitation factor), 值域 R_{f} 稱為問題的可行解 (feasible solution). 函數 f 稱為目標函數 (cost function, 也稱為代價函數), 最小化或最大化 f(x_{0}), x_{0} \in D_{f} 稱為問題的最佳解 (best solution).

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

分析 :

設 x_{i} 是嬰兒飲用第 i 種飲料的量, 滿意度函數 \displaystyle {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} = t 及 0 \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}‘ 稱為這個問題的最佳解.

定義 2. 對於某一個問題, 選取一個標準策略. 在解決問題的過程中, 每一步中都在標準策略的指引下作出最佳決策, 並在之後步驟中不再更改這個策略 (或者根本無法改變這個決策). 最終, 合併每一步中得到的子解形成問題的最終解. 稱這個標準策略為貪婪策略 (greedy strategy).

定義 3. 當我們指定了貪婪策略之後, 通過這個貪婪策略逐步解決某個問題並得到可行解的演算法都可以歸類為貪婪演算法 (greedy algorithm).

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

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

在上面這些例子中, 我們都選取了最佳的貪婪策略或者接近最佳解的貪婪策略. 但是貪婪策略遠不是只有最佳策略或接近最佳的策略, 也可以是最差的策略. 比如第一個情況, 我們完全可以選擇優先處理那些比較簡單的任務作為貪婪策略; 對於第二個情況, 我們可以選擇優先放入觀賞性較高而毫無實用性的傢俱作為貪婪策略. 最終導致的問題就是我們緊急任務沒有完成的後果或者沒有預算購買實用傢俱的後果. 一般來說, 實際問題的限制會更加嚴格, 我們可能會遇到任務多但是時間少的問題, 或者部分傢俱可以重疊. 我們通常會綜合所有情況, 選擇出最佳的貪婪策略.

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

總結上面的理論和經驗, 我們可以得到貪婪演算法的細節 :

1. 將實際問題化約為數學問題;
2. 找到目標函數和限制條件;
3. 將大問題分解為若干個小問題;
4. 制定貪婪策略;
5. 在貪婪策略的指引下逐個找到小問題的最佳解;
6. 將小問題的最佳解合併為大問題的解, 得到原始問題的最終解.

那麼現在有一個疑問, 對於任意問題, 通過貪婪演算法得到的最終解是不是永遠都是最佳解呢? 畢竟將大問題分解得到若干個小問題之後, 通過貪婪策略得到的小問題的解都是最佳解. 也就是說, 若干個小問題最佳解的合併能否得到原始問題的最佳解? 貪婪演算法的魅力並不是在制定貪婪策略, 而是在證明得到的解是否為問題的最佳解. 因為貪婪策略很容易指定, 例如上面提到的傢俱裝入房間的問題, 我們很容易就想到根據傢俱實用度來排序, 然後作出選擇. 為了證明解是否為最佳解, 我們一般通過直接證明, 列舉, 歸納或者歸謬等方法從數學的角度來證明.

斷言 1. 對於例題 2, 設定貪婪策略為 “不超過要找的零錢總數的條件下, 每一次都選擇盡可能大的面額”, 根據這個貪婪策略得到的最終解必定是最佳解.

證明 :

設 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}, 即貪婪演算法產生的解就是最佳解.

\blacksquare

當然, 確實存在一些問題使用貪婪演算法無法得到其最佳解. 但是在絕大多數情況下, 貪婪演算法都可能接近最佳解, 這樣的貪婪演算法稱為啟發式演算法 (heuristic algorithm). 啟發式演算法雖然不能在最佳時間內獲得解, 但是也可以在我們可接受的時間範圍內獲得解. 除此之外, 相對於嚴謹的正確解法而言, 啟發式演算法通常具備容易理解的特點. 如果啟發式演算法的正確性和最佳化演算法的正確性有著一定的關係, 那麼我們也稱這個啟發式演算法為近似演算法 (approximation algorithm). 例如最佳解為 \mathscr {O}, 而由啟發式演算法得到的解為 \mathscr {X}, 若總有 \displaystyle {\alpha \leq \frac {\mathscr {X}}{\mathscr {O}} \leq 1} 成立, 那麼我們就可以稱這個貪婪演算法為精確演算法的近似演算法. 其中, \alpha 為近似比. 例如某個問題中, 最佳解為 100, 近似演算法得到的解一般在 [90, 100] 中, 那麼近似比就是 \frac {9}{10}. 這只是近似演算法的一種定義, 我們不詳細展開, 這個問題我們將在計算複雜性理論文章中詳細討論.

2. NP 問題

本文中介紹的 NP 問題相關的定義都是實用定義, 精確定義將在計算複雜性理論系列文章中介紹.

為什麼要引入啟發式演算法和近似演算法, 這就要談到臭名昭著的 NP 問題. 這還要從現代電腦的架構開始說起. 現代電腦都是基於決定性杜林機架構. 所謂決定性杜林機 (deterministic turning machine) 就是給定一些狀態和資料, 電腦下一步的運作結果是決定性的, 而且具有唯一性. 想像一下程式設計語言中的函式, 當給定了函式引數之後, 函式的運作結果是具有決定性和唯一性的, 不管轉移到任何決定性杜林機架構的裝置上都不會發生改變. 這便是決定性杜林機的特點. 與決定性架構相對應的就是非決定性的架構. 所謂非決定性杜林機 (non-deterministic turning machine) 就是電腦具有自主選擇的能力, 在給定一定的狀態和資料的情況下, 電腦可以自己選擇下一步應該做什麼. 其實, 人類的大腦就類似於一個非決定性杜林機, 我們人生下面的路應該怎麼走不是具有決定性和唯一性的, 我們可以自己掌握.

定義 4. 給定任意問題和對應演算法, 若決定性杜林機可以在多項式時間 T(n) 內完成計算, 那麼稱這個問題是 P 問題 (polynomial-time problem). 其中, 多項式時間 T(n) 可以表示為 \displaystyle {T(n) = a_{m}n^{m} + a_{m - 1}n^{m - 1} + ... + a_{2}n^{2} + a_{1}n + a_{0}}, 要求 a_{m} > 0.

根據定義 4, 實際上只要是問題解決方案的時間複雜度可以表示為 O(n^{k}) 的話, 就可以稱這個問題是 P 問題. 其中, k 是常數. 那麼對應地, 如果時間複雜度只能用 \Omega(k^{n}) 表示的話, 那麼就稱這個問題是 NP 問題. 其中, k 也是常數且 k > 1. 要注意 P 問題和 NP 問題的時間複雜度的不同性. P 問題的時間複雜度是多項式級別的, 而 NP 問題的時間複雜度並不是多項式級別的, 而是至少為指數級別.

定義 5. 給定任意問題和對應演算法, 若決定性杜林機無法或不確定是否可以在多項式時間內計算完成, 但是非決定性杜林機多項式時間內計算完成, 那麼稱這個問題是 NP 問題 (non-deterministic polynomial-time problem).

定義 5'. 給定任意問題和對應的一組解, 若決定性杜林機可以在多項式時間內驗證這個解是否成立, 那麼就可以稱這個問題是 NP 問題.

定義 5 和定義 5' 是關於 NP 問題的等價定義, 只是定義 5 是從問題出發, 定義 5' 是從解出發.

性質 1. 給定任意 NP 問題及對應演算法, 若決定性杜林機可以在多項式時間內解決該問題, 那麼稱這個 NP 問題也為 P 問題, 即對該問題有 P = NP 成立.

例如像排序問題, 不論這個排序演算法多麼慢, 電腦基本上也都能在 O(n^{2}) 的時間內完成排序, 所以排序問題是 NP 問題, 同時也是一個 P 問題. 不過一般來說, 我們不提排序問題是 NP 問題. 我們通常提的 NP 問題, 它們暫時都不是 P 問題. 為什麼這裡要用暫時呢? 因為到目前為止, 無法證明所有的 P 問題都是 NP 問題, 也無法證明所有的 P 問題都不是 NP 問題, P = NP? 的證明是一個世紀性的難題.

在定義或者性質中我們都明確了決定性杜林機這個背景, 但是一般來說, 只要提到 NP 問題, 都默認這個 NP 問題暫時不存在決定性杜林機下多項式時間複雜度的演算法.

定義 7. 給定一個布林 NP 問題, 在決定性杜林機下, 若其它 NP 問題都可以在多項式時間內化約到這個問題, 那麼稱這個問題為 NP 完備問題 (NP-complete problem, 簡稱為 NP-C 問題, NPC 問題), 或者稱該問題是 NP 完備的. NP 完備問題也稱為 NP 完全問題.

根據定義 7, NP 完備問題必須是一個決定性的問題, 其答案只限於 YES! 或者 NO!. NP 完備問題是人類解決 P = NP? 的過程中, 提出了一個過渡性的概念. 它的提出是為了找到一個渠道, 間接地證明 P = NP 成立. 因為如果給 NP 問題進行歸類, 那麼所有 NP 問題中肯定可以篩選出一些難度比其它 NP 問題更高的問題. 根據定義 7, 那些難度不太高的 NP 問題都可以在多項式時間內化約到這一類問題, 也就是說 NP 完備問題是 NP 問題中最難的那一部分問題. 若某個 NP 完備問題被證明在決定性架構的電腦下有多項式時間複雜度的演算法, 那麼 P = NP 對任意 NP 問題都成立. 從這個角度不嚴格地說, NP 完備問題是最不可能屬於 P 問題的那一類問題.

設問題 C_{0} 為給定一個集合 \mathscr {S}, 找到 S \subseteq \mathscr {S}, 使得 S 內所有元素之和為零. 其中, S \neq \emptyset. 這裡我直接給出一個結論 : 問題 C_{0} 是 NP 問題, 且暫時沒有人可以找到對應到 C_{0} 的多項式時間複雜度演算法. 那麼根據定義 7, 問題 C_{0} 不能算是一個 NP 完備問題, 因為 C_{0} 要求給出一個集合, 答案並不只限於 YES! 或者 NO!. 我們可以在常數時間內就把問題 C_{0} 進行化約到 C : 給定一個集合 \mathscr {S}, 是否可以找到 S \subseteq \mathscr {S}, 使得 S 內所有元素之和為零? 這裡同樣給出一個結論, 問題 C 是一個 NP 完備問題.

定義 8. 給定一個問題, 在決定性杜林機下, 如果所有 NP 問題都可以在多項式時間內化約到這個問題, 那麼稱這個問題為 NP 困難問題 (NP-hardness problem, 簡稱為 NP-H 問題, NPH 問題).

根據定義 7 和定義 8, 我們可以得出, NP 完備問題只是 NP 困難問題的一個特例, NP 問難問題的解就不再僅限於是或者否這樣的回答. 對於 NP 困難問題, 決定性架構的電腦也不一定可以在多項式時間內驗證其解是否正確. 即使 P = NP 成立, 但是 NP 困難問題仍然不一定存在多項式時間複雜度可解的演算法. 因此, NP 困難問題至少和 NP 完全問題一樣難.

3. P = NP?

目前, 大多數人都相信 P = NP 並不成立, 否則那些 NP 問題不可能到現在都沒有任何人找出多項式時間複雜度的演算法. Figure 1 描述了當 P = NP 成立或者不成立時候, 不同問題的歸屬關係.

4. 貪婪演算法與 NP 問題

通過第 2 節, 我們知道 NP 問題都暫時不存在決定性杜林機下多項時間複雜度的問題解. 目前, 要解決一個 NP 問題必須忍受其指數時間複雜度, 階乘時間複雜度甚至更高時間複雜度. 但是如果我們可以接受不那麼精確的答案, 即可能存在錯誤的答案, 那麼我們就可以利用貪婪演算法在多項時間複雜度內解決 NP 問題. 而且我們說過, 那些精確的演算法通常不易理解, 然而制定了貪婪策略的貪婪演算法通常比較好理解.

通常來說, 在生活中解決 NP 問題都是靠生活經驗. 實際上在使用貪婪演算法解決 NP 問題的時候, 我們絕大多數時候也都是靠生活經驗.

4.1 箱櫃裝載

例題 3. 設有等待裝載的物品 n 個, 第 i 個物品所佔用的容量為 w_{i}. 其中, i = 1, 2, ..., n. 箱櫃的數量不限, 但是每個箱櫃至多能夠裝載的容量為 c. 我們要找到一個方案, 使得所有物品都可以被裝載並且箱櫃使用的數量最少.

例題 3 被稱為箱櫃裝載問題, 幾乎很少人可以憑藉直覺很短時間內找到最佳的演算法來解決這個問題. 但是我們說過, 我們可以憑藉著我們的生活經驗, 制定貪婪準則, 得到一個啟發式演算法甚至就是準確的演算法. 在箱櫃裝載問題中, 我們可以使用的生活經驗有以下方案 :

1. 最先適配 : 按順序裝載, 每次裝載時選擇前面可以裝載物品的箱櫃;
2. 最佳適配 : 裝載時選擇可以容納物品但是剩餘容量最小的箱櫃;
3. 最先適配遞減 : 執行最先適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序;
4. 最佳適配遞減 : 執行最佳適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序;
5. 最後適配 : 按順序進行裝載, 每次裝載時選擇最後面可以裝載物品的箱櫃;
6. 最差適配 : 按順序進行裝載, 每次裝載時選擇可以容納物品但是剩餘容量最大的箱櫃;
7. 最後適配遞減 : 執行最後適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序;
8. 最差適配遞減 : 執行最差適配方案, 但是執行方案之前先按照物品所佔用容量的大小進行排序;
9. 隨機適配 : 隨機選取箱櫃, 當箱櫃可以容納物品的時候就裝載; 否則, 重新選區箱櫃;
10. 相鄰適配 : 為了裝載一件物品, 首先在非空的箱櫃中循環搜尋能夠裝載該物品的箱櫃. 如果找不到這樣的箱櫃, 那麼就啟用一個新的箱櫃. 開始時, 沒有非空的箱櫃, 那麼就啟用箱櫃 1 裝載物品 1. 不妨設箱櫃 1 至箱櫃 b 已經裝載了物品, 其中 b \geq 1. 我們將所有箱櫃從箱櫃 1 開始直到箱櫃 b 排列為一個環. 設第 i 個箱櫃是上一次被裝載的箱櫃 : 當 i \neq b 的時候, i 的下一個箱櫃為 i + 1; 當 i = b 時, i 的下一個箱櫃為箱櫃 1 (i = 1, 2, ..., b). 下一次再搜尋的時候, 從第 i 個箱櫃開始搜尋, 直到找到一個合適的箱櫃或者啟用一個空箱櫃為止;
11. ...

然而對於例題 3, 我們可以通過第四個方案產生精確的演算法.

斷言 1. 在例題 3 中, 選擇最佳適配遞減方案作為貪婪準則, 使用貪婪演算法產生的結果是最佳解.

證明 :

不失一般性. 設所有的物品被裝載之前已經按照重量從小到大排序, 即 \mathscr {W} = \left \{ w_{1}, w_{2}, ..., w_{n} \right \}, w_{i} \leq w_{i + 1} (i = 1, 2, ..., n - 1). 設 \mathscr {X} = \left \{ x_{1}, x_{2}, ..., x_{n} \right \} 是使用上述貪婪準則得到的解, \mathscr {Y} = \left \{ y_{1}, y_{2}, ..., y_{n} \right \} 是任意一個可行解, 其中, x_{c} 和 y_{c} 滿足 \displaystyle {x_{c}, y_{c} = \begin {cases} 0 & {\text {第 } c \text{ 個箱子未被裝載}} \\ 1 & {\text {第 } c \text{ 個箱子被裝載}} \end {cases}, c = 1, 2, ..., n}. 根據貪婪準則, 必定存在某個 k (0 \leq k \leq n), 使得當 i \leq k 時, 有 x_{k} = 1; 當 i > k 時, 有 x_{k} = 0.

接下來, 我們使用歸納法證明斷言成立. 令 j = \min \left \{ i : x_{i} = 1, i = 1, 2, ..., n \right \}. 當 j = 1 時, 任意可行解 \mathscr {Y} 滿足 \mathscr {Y} \subset \mathscr {X}. 否則, \sum \limits_{i = 1}^{n} y_{i} > M (M 為最大裝載量), 此時 \mathscr {Y} 不是一個可行解. 自然地, 有 \displaystyle {\sum \limits_{i = 1}^{n} x_{i} \geq \sum \limits_{i = 1}^{n} y_{i} \text { 且 } \sum \limits_{i = 1}^{n} x_{i} \cdot w_{i} \geq \sum \limits_{i = 1}^{n} y_{i} \cdot w_{i}}. 當 j > 1 時, 任取正整數 m, 不妨設 j \leq m 時, 有 \sum \limits_{i = 1}^{n}x_{i}w_{i} \geq \sum \limits_{i = 1}^{n} y_{i}w_{i} 成立. 當 j = m + 1 時, 令 y_{1} = 1, y_{j} = 0, y_{i} = x_{i} (i \neq j, i = 2, 3, ..., n), 那麼 \displaystyle {\sum \limits_{i = 1}^{n}y_{i}w_{i} = w_{1} - w_{j} + \sum \limits_{i = 1}^{n}w_{i}x_{i}} 成立. 由於 w_{j} \geq w_{1}, 因此 \displaystyle {\sum \limits_{i = 1}^{n}y_{i}w_{i} \leq \sum \limits_{i = 1}^{n}w_{i}x_{i}}. 另外, 又有 \displaystyle {\sum \limits_{i = 1}^{n}x_{i} = \sum \limits_{i = 1}^{n}y_{i}}. 最後, 考慮 j = 0 的情況, 此時 \sum \limits_{i = 1}^{n}x_{i} = \sum \limits_{i = 1}^{n}y_{i} = 0, \sum \limits_{i = 1}^{n}x_{i}w_{i} = \sum \limits_{i = 1}^{n}y_{i}w_{i} = 0. 於是, \displaystyle {\sum \limits_{i = 1}^{n}x_{i} \geq \sum \limits_{i = 1}^{n}y_{i} \text { 且 } \sum \limits_{i = 1}^{n}x_{i}w_{i} \geq \sum \limits_{i = 1}^{n}y_{i}w_{i}}.

綜上所述, 在任何情況下 \mathscr {X} 都是最佳解. 因此, 使用貪婪演算法產生的解是最佳解.

\blacksquare

在作業系統中, 記憶體裝載問題的原型實際上就是箱櫃裝載問題.

最後, 我們來分析一下選擇最佳適配遞減方案作為貪婪準則產生的貪婪演算法的時間複雜度. 首先將物品進行排序, 這個時間複雜度可以降低到 \Theta(n\log {n}). 將所有物品裝載到箱櫃的時間複雜度為 \Theta(n). 總體來說, 由最佳適配遞減方案驅動的貪婪演算法的時間複雜度為 \Theta(n\log {n}). 如果給定的物品就是有序的, 那麼時間複雜度還可以進一步降低為 \Theta(n). 根據定義 4, 箱櫃裝載問題是 P 問題.

4.2 任務排程

例題 4. 一個工廠有 m 台機器, 工廠接受了 n 個任務, 第 i 個任務的處理時間為 t_{i}. 其中, i = 1, 2, ..., n. 若一台機器同一時間至多只能處理一個任務, 一個任務不可同時在兩台機器上進行處理. 我們要找到一個方案, 使得 n 個任務在 m 台機器上用時最少的最佳排程方案.

例題 4 被稱為任務排程問題. 在作業系統中, 多核心 CPU 的執行緒級並行處理問題實際上就是任務排程問題. 我們可以使用的生活經驗有 :

1. 按順序排程, 先來先處理;
2. 按任務重要程度進行排程;
3. 按任務處理需要的時長進行排程 (從小到大或者從大到小);
4. 隨機排程;
5. ...

4.3 0/1 背包問題

例題 5. 有 n 個物品和一個容量為 c 的背包, 從 n 個物品中選取裝包的物品, 第 i 件物品的重量為 w_{i}. 價值為 p_{i} (i = 1, 2, ..., n). 一個可行的背包裝載是裝包物品的總重量不超過背包的容量的 c. 一個最佳背包裝載是指物品的總價值最高的可行背包裝載方案.

例題 5 被稱為 0/1 背包問題, 這是一個 NP 問題, 目前還沒有人找到多項式時間複雜度的演算法來解決這個問題. 根據題目描述可知, 目標函數為 f(\mathscr {X}) = f(x_{1}, x_{2}, ..., x_{n}) = \sum \limits_{i = 1}^{n}x_{i}p_{i}, 限制條件為 \sum \limits_{i = 1}^{n}x_{i}w_{i} \leq c. 只要符合限制條件的解均為可行解, 能使得目標函數 f 取得最大值的解為最佳解. 其中, x_{i} = \begin {cases} 0 & {\text {第 } i \text { 個物品不被放入背包}} \\ 1 & {\text {第 } i \text { 個物品被放入背包}} \end {cases}, i = 1, 2, ..., n.

那麼根據生活經驗, 可能的貪婪策略有 :

1. 從剩餘物品中選擇價值最大的物品放入背包;
2. 從剩餘物品中選擇重量最小的物品放入背包;
3. 價值密度 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 法則 : 從剩餘物品中選擇價值密度較大的物品放入背包;
4. 隨機選擇物品放入背包;
5. ...

現在, 我們採用第三個方案, 即價值密度 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 法則作為貪婪準則. 但是在多種變數的影響下, 價值密度法則並不能保證一定能夠得到最佳解. 更多情況下, 使用價值密度法則為貪婪準則的貪婪演算法得到的解是可以接近最佳解的. 所以, 以價值密度 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 法則作為貪婪準則的貪婪演算法是一個啟發式演算法. 那麼是否存在這樣一個 p (0 \leq p \leq 1), 使得啟發式演算法得到的解與最佳解相差在 p 之內呢? 其中, 設 \mathscr {X} = \left \{ x_{1}, x_{2}, ..., x_{n} \right \} 是最佳解, \mathscr {Y} = \left \{ y_{1}, y_{2}, y_{n} \right \} 是啟發式演算法得到的解.

對於任意 p, 有 \displaystyle {p = \frac {\sum \limits_{i = 1}^{n}x_{i}p_{i} - \sum \limits_{i = 1}^{n}y_{i}p_{i}} {\sum \limits_{i = 1}^{n}x_{i}p_{i}}}. 可能閣下還無法進行判定, 那麼不妨嘗試尋找一個否定的實例. 考慮 n = 2, \mathscr {W} = \left \{ 1, y \right \}, \mathscr {P} = \left \{ 10, 9y \right \}, c = y. 其中, y 為任意常數. 此時, \frac {p_{1}}{w_{1}} = 10, \frac {p_{2}}{w_{2}} = 9, 則使用啟發式演算法得到的解為 \mathscr {Y} = \left \{ 1, 0 \right \}. 當 y \geq \frac {10}{9}, 最佳解 \mathscr {X} = \left \{ 0, 1 \right \}. 故 p = \frac {9y - 10}{9y}. 令 p \to +\infty, 考慮極限 \displaystyle {\lim \limits_{y \to +\infty} \frac {9y - 10}{9y} = 1}, 顯然 |p - 1| 越小, 策略越不可用, 因為啟發式演算法得到的解和最佳解的差距越來越大. 此時, 需要修改啟發式演算法 : 設最多有 k 件物品放入背包 (0 \leq k \leq n). 若 \sum \limits_{i = 1}^{k}x_{i}w_{i} > c, 則放棄這個解; 否則, 按照順序容量將剩餘物品按 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 的遞減順序放入背包. 考慮所有可能的解 \mathbb {Y} = \left \{ \mathscr {Y}_{1}, \mathscr {Y}_{2}, ..., \mathscr {Y}_{j} \right \}. 其中, 0 \leq \mathop {\mathrm {card}} \mathscr {Y}_{i} \leq n (i = 1, 2, ..., n). 從 \mathbb {Y} 中選擇一個解, 滿足 |p - 1| 最大, 從而使得解的結果與最佳解相差在 p 之內.

例題 5. 設 n = 4, \mathscr {W} = \left \{2, 4, 6, 7 \right \}, \mathscr {P} = \left \{ 6, 10, 12, 13 \right \}, c = 11. 以價值密度 \frac {p_{i}}{w_{i}} (i = 1, 2, ..., n) 法則作為貪婪準則, 使用貪婪演算法解決 0/1 背包問題.

解 :

使用修改之前的啟發式演算法, 得到的解 \mathscr {Z} = \left \{ 1, 1, 0, 0 \right \}, f(\mathscr {Z}) = 16. 接著, 我們使用修改後的啟發式演算法求解.

當 k = 1 時, 考慮將一件物品放入背包, 可選的物品有 x_{1}, x_{2}, x_{3}, x_{4}. 當 x_{1} = 1 或 x_{2} = 1 時, 產生的結果與價值密度貪婪準則一樣. 考慮 x_{3} = 1, 此時背包剩餘容量為 5, 僅有 x_{1} 和 x_{2} 可以放入背包, 選擇價值密度較小的 x_{1} 放入背包得到的解為 \mathscr {Y}_{1} = \left \{ 1, 0, 0, 1 \right \}, 此時 f(\mathscr {Y}_{1}) = 19. 除此之外, 其餘解都是當 k = 1 時的不可行解.

當 k = 2 時, 可選的物品有 \left \{ x_{1}, x_{2} \right \}, \left \{ x_{2}, x_{3} \right \}, \left \{ x_{1}, x_{4} \right \}, \left \{ x_{2}, x_{3} \right \}, \left \{ x_{2}, x_{4} \right \}, \left \{ x_{3}, x_{4} \right \}. 排除已經考慮過的 \left \{ x_{1}, x_{2} \right \}, \left \{ x_{1}, x_{3} \right \}, \left \{ x_{1}, x_{4} \right \} 還有不可行的 \left \{ x_{2}, x_{4} \right \}. 還剩下 \left \{ x_{2}, x_{3} \right \} 和 \left \{ x_{2}, x_{4} \right \}. 考慮 x_{2} = 1, x_{3} = 1, 此時背包剩餘容量為 1, 不能再放入任何物品, 因此得到解 \mathscr {Y}_{2} = \left \{ 0, 1, 1, 0 \right \}, f(\mathscr {Y}_{2}) = 22. 考慮 x_{2} = 1, x_{4} = 1, 此時背包容量為 0, 不能再放入任何物品, 得到解 \mathscr {Y}_{3} = \left \{ 0, 1, 0, 1 \right \}, f(\mathscr {Y}_{3}) = 23.

當 k = 3 或者 k = 4, 物品的總重量已經超過 c, 不歸入可行解.

綜上所述, 選擇 \mathscr {Y}_{3} 作為修改後啟發式演算法的解.

\blacksquare

稱修改後的啟發式演算法稱為 k 階優化. 將這種啟發式演算法稱為有界性能啟發式演算法, 這種演算法所得到的解在最佳解的 \frac {1}{k + 1} 之內. 有界性能啟發式演算法的運作時間隨著 k 值的增大而增大, 需要嘗試的子集數目為 O(k^{n}), 每一個子集所用的時間為 \Theta(n - k). 設物品排序的時間為 \Theta(n\log {n}). 當 k > 0 時, 總的時間複雜度為 O(n^{k + 1}). 由於這種啟發式演算法得到的解在最佳解的 \frac {1}{k + 1} 之內, 所以 k 階優化也是一個近似演算法.