摘要訊息 : 從問題的全局出發, 動態地對子問題的解進行規劃.

0. 前言

貪婪演算法 (《貪婪演算法》) 和分而治之演算法 (《分而治之演算法》) 都有把大規模問題拆解成小規模問題, 然後從小規模問題求解出發, 得到大規模問題解的趨向. 然而, 貪婪演算法一旦根據貪婪策略作出抉擇之後, 就無法再更改. 這也就導致了每一個小問題最佳解的組合並不一定就是大問題的最佳解. 另外, 如果在問題劃分之後存在公共子問題, 分而治之演算法會對那些公共字問題反覆求解, 影響了演算法的效能.

更新紀錄 :

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

1. 動態規劃演算法

定義 1. 設可分解問題 P 可以被分解為 P_{1}, P_{2}, ..., P_{n}. 演算法 A 在考慮前 i 個子問題的解 x_{1}, x_{2}, ..., x_{i} 之後, 通過動態調整前 i 個解來獲得 x_{i + 1}, 使得 x_{1}, x_{2}, ..., x_{i}, x_{i + 1} 是子問題 P_{1}, P_{2}, ..., P_{i}, P_{i + 1} 的最佳解, 最終通過 A 獲得子解集 \displaystyle {\mathscr {X} = \left \{ x_{1}, x_{2}, ..., x_{n} \right \}}. 若屏蔽 P 的子問題 P_{j}, 剩下的解 \left \{ x_{1}, x_{2}, ..., x_{j - 1}, x_{j + 1}, x_{j + 2}, ..., x_{n} \right \} 仍然是問題 P \setminus P_{j} 的最佳解, 則稱 A 為動態規劃演算法 (dynamic programming algorithm). 其中, i, j = 1, 2, ..., n.

通過定義 1, 我們可以窺探動態規劃演算法的本質就是動態地進行規劃. 它不像貪婪演算法那樣, 在決定了某個子問題的解之後就不再管它. 動態規劃演算法和分而治之演算法在問題的分解上最大的不同是分而治之的演算法是有規模地進行劃分, 但是動態規劃沒有這個限制. 我們完全可以從解出發進行劃分.

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

分析 :

如《貪婪演算法》第 4.3 節中那樣, 我們將 0/1 背包問題的解寫成 \displaystyle {x_{1}, x_{2}, ..., x_{n}}. 其中, x_{i} = \begin {cases} 0 & \text {第 } i \text { 個物品不被放入背包} \\ 1 & \text {第 } i \text { 個物品放入背包} \end {cases}, i = 1, 2, ..., n.

根據定義 1 從解出發, 不論 x_{1} = 1 還是 x_{1} = 0, \left \{ x_{2}, x_{3}, ..., x_{n} \right \} 必須是子問題的解. 當 x_{1} = 1 時, 子問題是 n - 1 個物品和一個容量為 c - w_{1} 的 0/1 背包問題; 當 x_{1} = 0 時, 子問題是 n - 1 個物品和一個容量為 c 的 0/1 背包問題. 為了得到最佳解, 我們需要遞迴方程式的幫助.

上面的討論中, 我們在已知 x_{2}, x_{3}, ..., x_{n} 取值的情況下對 x_{1} 作出抉擇. 那麼我們不妨假設抉擇的順序為 x_{n}, x_{n - 1}, x_{n - 2}, ..., x_{2}, x_{1}.

記 P_{i} 是在第 i 個物品被抉擇後, 即知道 x_{i} 的取值之後, 背包中的總價值. 那麼有 \displaystyle {P_{n} = \begin {cases} p_{n} & {x_{n} = 1} \\ 0 & {x_{n} = 0}, \end {cases} P_{i} = \begin {cases} p_{i} + P_{i + 1} & {x_{i} = 1} \\ P_{i + 1} & {x_{i = 0}}. \end {cases}} 但是這樣的遞迴方程式只考慮了價值, 沒有考慮背包的剩餘容量. 這就導致 x_{i} 的取值必須由我們主動進行抉擇. 當我們在對待 x_{i} 猶豫不決的時候, P_{1}, P_{2}, ..., P_{i - 1}, P_{i} 的計算就無法進行. 因此, 我們不但要考慮背包的價值, 還要考慮背包的剩餘容量.

\blacksquare解 :

記 P(i, y) 表示在背包剩餘容量為 y 的情況下, 抉擇 x_{1}, x_{2}, ..., x_{n} 所形成的背包價值. 對於 i = n, 有 \displaystyle {P(n, y) = \begin {cases} p_{n} & {y \geq w_{n} \wedge x_{n} = 1} \\ 0 & {0 \leq y < w_{n} \vee x_{n} = 0}. \end {cases}} 接著我們考慮 i < n 的情形. 當 0 \leq y < w_{i} 時, 必定有 \displaystyle {P(i, y) = P(i + 1, y);} 當 y \geq w_{i} 的時候,

• 若 x_{i} = 1, 則 \displaystyle {P(i, y) = P(i + 1, y - w_{i}) + p_{i};}
• 若 x_{i} = 0, 則 \displaystyle {P(i, y) = P(i + 1, y).}

綜上所述, 有 \displaystyle {P(n, y) = \begin {cases} p_{n} & {y \geq w_{n} \wedge x_{n} = 1} \\ 0 & {0 \leq y < w_{n} \vee x_{n} = 0}, \end {cases}} \displaystyle {P(i, y) = \begin {cases} P(i + 1, y - w_{i}) + p_{i} & {y \geq w_{n} \wedge x_{n} = 1} \\ P(i + 1, y) & {0 \leq y < w_{i} \vee x_{n} = 0.} \end {cases}} 就目前而言, 我們暫時還沒有辦法確定 x_{i} 的值, 它和 x_{i + 1}, x_{i + 2}, ..., x_{n} 的值沒什麼關係, 但卻會影響 x_{1}, x_{2}, ..., x_{i - 1} 的取值. 不過, 由於我們需要的是價值最高的背包裝載, 所以當 y \geq w_{i} 的時候, 我們可以令 \displaystyle {P(i, y) = \max \left \{ P(i + 1, y), P(i + 1, y - w_{i}) + p_{i} \right \}.}

最終, 我們可以將 P(i, y) 寫成 \displaystyle {P(i, y) = \begin {cases} \max \left \{ P(i + 1, y), P(i + 1, y - w_{i}) + p_{i} \right \} & {y \geq w_{i}} \\ P(i + 1, y) & {0 \leq y < w_{i}}. \end {cases}}

\blacksquare

例題 2. 對於例題 1, 令 n = 3, w = \left \{ 100, 14, 10 \right \}, p = \left \{ 20, 18, 15 \right \} 且 c = 116. 求最佳的背包裝載方案.

解 :

要得到這個 0/1 背包問題的最佳解, 實際上是要求 P(1, 116) 的值. 由於 w_{1} \leq 116, 故有 \displaystyle {P(1, 116) = \max \left \{ P(2, 116), P(2, 16) + 20 \right \}}. 以此類推 : \displaystyle {P(2, 116) = \max \left \{ P(3, 116), P(3, 102) + 18 \right \}}, \displaystyle {P(3, 116) = p_{3} = 15}, \displaystyle {P(3, 102) + 18 = p_{3} + 18 = 33}. 因此, P(2, 116) = P(3, 102) + 18 = 33. 而 \displaystyle {P(2, 16) + 20 = \max \left \{ P(3, 2) + 18, P(3, 16) \right \} + 20}, \displaystyle {P(3, 2) + 18 = 0 + 18 = 18}, \displaystyle {P(3, 16) = p_{3} = 15}. 那麼, P(2, 16) + 20 = 18 + 20 = 38. 於是 \displaystyle {P(1, 116) = P(2, 16) + 20 = 38}. 此時, \mathscr {X} = \left \{ x_{1}, x_{2}, x_{3} \right \} = \left \{ 1, 1, 0 \right \}. 目標函數 P(\mathscr {X}) = \sum \limits_{i = 1}^{n}x_{i}p_{i} = 38.

綜上所述, 我們得到了該例下的最佳解 \mathscr {X} = \left \{ 1, 1, 0 \right \}.

\blacksquare

我們稱 \displaystyle {P(n, y) = \begin {cases} p_{n} & {y \geq w_{n} \wedge x_{n} = 1} \\ 0 & {0 \leq y < w_{n} \vee x_{n} = 0}, \end {cases}} 和 \displaystyle {P(i, y) = \begin {cases} \max \left \{ P(i + 1, y), P(i + 1, y - w_{i}) + p_{i} \right \} & {y \geq w_{i}} \\ P(i + 1, y) & {0 \leq y < w_{i}}. \end {cases}} 為 0/1 背包問題的動態規劃遞迴方程式 (dynamic programming recursive equation).

根據我們對 0/1 背包問題的討論, 我們可以總結出使用動態規劃演算法解決問題的基本步驟 :

1. 確定問題是否可以適用動態規劃演算法;
2. 建立動態規劃遞迴方程式;
3. 解動態規劃遞迴方程式得到最佳解.

2. 遞迴

和分而治之演算法類似, 使用動態規劃演算法解決問題的時候, 我們也要建立遞迴方程式, 所以一般動態規劃演算法的實作也是採用遞迴. 以例題 1 為例, 可以根據 0/1 背包問題的動態規劃遞迴方程式寫出演算法 :

3. 複雜度

動態規劃演算法的時間複雜度和空間複雜度一般都和問題的動態規劃遞迴方程式有關. 而且一般來說, 動態規劃演算法的時間複雜度是多少, 空間複雜度也是多少. 因為遞迴的次數和所使用的空間是線性關係的. 解 0/1 背包問題的動態規劃遞迴方程式可以得到, 使用動態規劃演算法求解 0/1 背包問題的時間複雜度和空間複雜度為 \Theta(2^{n}). 相比於《貪婪演算法》第 4.3 節的啟發式演算法, 這個時間複雜度級別要高出 \Theta(n^{k}) 太多.