--- # System prepended metadata title: 動態規劃（Dynamic Programming） --- # 動態規劃（Dynamic Programming） ## 介紹   動態規劃 （Dynamic Programming, DP） 是一個很重要的演算法，江老師說：「如果不會 Dynamic Programming，不要跟別人說你學過演算法。」其中 Programming 這個詞並不是寫程式的意思，而是數學上在求解一個最佳化問題的意思。   Dynamic Programming 跟分而治之法有點像，都是從數學歸納法的證明推導出來的。他的核心概念也是將問題拆成好幾個小問題，接著將小問題的解答慢慢組合而成最終解答。由於都是從數學歸納法的證明推導出來的，其演算法大多可以用遞迴函式寫出來。那 Dynamic Programming 實際該怎麼用呢？什麼時候該用 Dynamic Programming 而不是分而治之法呢？這兩個問題等我們看完第一個 Dynamic Programming 的問題再來解答。 ## Weighted Interval Scheduling ### 問題描述   之前我們談過 Interval Scheduling 的問題，若只有一個資源，請在給定的 intervals 下，設計一個能容納最多 intervals 的 schedule。這次我們的問題變成給定的 intervals 不僅有結束和開始時間限制，每個 intervals 還有自己的權重。題目是要設計一個 interval schedule，可以使權重最大。 ![image](https://hackmd.io/_uploads/H1VENj5_-l.png) ### 解法   顯而易見，Interval Scheduling 問題的 greedy 解法並不適用此問題。前面我們說過要使用數學歸納法來推導，那我們可以從遞迴的思路去思考如何求解。首先，既然要用遞迴，我們會想拆解原問題，但要如何拆解呢？我們可以先想，要是不考慮最後一個 interval (時槽8~9)，那最佳解會是什麼？不考慮最後一個 interval，最佳解應該會有兩種情況，第一個是「最終最佳解包含最後一個 interval」，所以目前的解是「包含第四個 interval 時的最佳解」。第二種情況是最終最佳解不包含最後一個 interval」，所以目前最佳解是「包含第11個 interval 時的最佳解」。所以最終解是否包含最後一個 interval 就很容易可以判斷了，我們可以看「包含第四個 interval 時的最佳解權重加上最後一個 interval 的權重」是否會大於「包含第11個 interval 時的最佳解權重」，如果大於就使用包含第四個 interval 時的最佳解加上最後一個 interval 的權重來當作最佳解。請注意，上述這種方法是使用 Dynamic Programming 的正確方法，也就是「從最大的集合出發，不斷把最後一個元素移除，來考慮沒有最後一個元素的最佳情況。」   用文字說明有點難理解我們就來看數學，以先定義幾個變數： 1. $p(j)$：小於 $j$ 且與第 $j$ 個 interval 不重疊的最大 interval index。若沒有則 $p(j)=0$。 2. $OPT(j)=\max\{v_j+OPT(p(j)),OPT(j-1)\}$：在第 $j$ 個 interval 時的最佳解。 因此完整演算法可以表示如下： ![image](https://hackmd.io/_uploads/rkqrEoqubx.png) 根據這個演算法我們可以畫出他的遞迴樹如下，記錄了每一個 interval 執行過的流程。從這棵樹我們可以發現第三個 interval 被重複算了三次。
為了避免重複計算的情況，我們希望在每次算完可以紀錄這個 interval 的計算結果，因此將演算法修改如下： #### Memoization: top-down
遞迴樹變成如下：
時間複雜度是 $O(n)$。 #### Iteration: Bottom up   任何的遞迴函數其實都可以用迴圈完成，這裡我們便要來討論這件事。其實這裡可以用另一種方法，既然每個 intervals 我們都只會計算一次，那我們也可以從第一個 interval 開始算，算完最後就可以得出最佳值了。其計算複雜度同樣是 $O(n)$，具體演算法如下：
## DP 使用時機   看完了這個範例，那所以到底什麼時候要用 Dynamic Programming？總結許多大師的論述，滿足以下情況可以使用 Dynamic Programming： 1. 原問題是一個最佳化問題，有最大/小化的目標。 2. 子問題的數量只有多項式的數量 3. 原問題的解可以輕易從子問題的解求得 4. 被拆解的子問題有一個自然 (天生) 地排序。 5. 能使用遞迴求解 6. 原問題被拆解成子問題後，子問題的解法有高度重疊性   那什麼時候該用 Dynamic Programming 而不是 Divide-and-conquer？通常一個問題滿足上述第 4 跟 6 點的話，我們會用 Dynamic Programming 而不是 Divide-and-conquer。 ## Fibonacci sequence (費波那契數列)   費波那契數列是一個自帶遞迴關係的數列，此數列除了第一個值是 0，第二個值是 1 ，其餘的每個值皆為前兩個值相加。很有名的黃金比例 $1.618$ 也是由這個數列推導而來，下圖中長邊與短邊之比會近似於長邊中大塊與小塊的邊長比，像是 $13:5\approx 8:5\approx 1.618$，其中變數越大時，比例值會越接近 $1.618$。
  費波那契數列這個範例沒有解最佳化問題，其實應該不需要使用 Dynamic programming ，只是剛好可以用 Dynamic programming 來實作。 ### 解法 #### Memoization
#### Iteration
## Maze Routing Problem ### 問題描述   問題是在給定一個（有障礙物的）迷宮內，指定起始點跟終點，如何找出最短路徑？其實我們在做 IC 設計時也會需要處理這種問題，當固有的電路已經設計完成了，如何不影響他們而設計出最短的線路。
### 解法   解法就是使用 Dynamic Programming 的 iteration 解法，從起點不斷向外紀錄目前到達的點，直到抵達終點時停下來，接著再往回看就可以找到最短路徑。此演算法的執行時間複雜度是 $O(MN)$，其中 $M$ 跟 $N$ 是迷宮的大小。
  從這個範例我們可以看出來，雖然 Dynamic Programming 可以確保找出最短路徑，但如果 $M$ 或 $N$ 很大，則會耗費很多記憶體來記錄，並且可能會耗時很久。所以我們可以知道，「Dynamic Programming 的演算法效能會與其大小高度相關」。 ## Subset Sum （無價值背包問題） ### 問題描述   假設有 $n$ 個物品，第 $i$ 個物品的重量為 $w_i$，若今天背包最多只能放 $W$ 重量的物品，請問最多可以放多重？
  我們可以先寫出其數學形式，可以發現他是一個最佳化問題：
其中變數就是我們要找的那些 $i$。 ### 解法   這個問題無法用 greedy 的方法求解，不信你可以試試看。一樣，我們試著使用 dynamic programming 。首先，我們先將所有物品隨意編號，然後一樣從最後一個開始回推，看會發生什麼事。我們定義一個最佳函數如下： ![image](https://hackmd.io/_uploads/SJceqrEdZl.png) 其中 $i$ 表示考慮第 $i$ 物品，而 $w$ 表示考慮當下可承受的重量。至此，我們可以寫出遞迴關係式如下： ![image](https://hackmd.io/_uploads/rJf8ro9_Zl.png) 第一個等式是說如果今天沒有物品或承重重量是 0，那我們的解也會是 0；第二個是說如果要考慮的第 $i$ 個物品已經大於目前承重重量了，那他便無法放進來，此時最佳解會跟沒有這個物品時的解一樣。第三個等式是我們移開編號 $i$ 的物品，此時會有兩種情況。第一種最佳解是包含最後一個物品的，那此時最大重量就是不包含這個物品時的最大重量（$w-w_i$）加上這個物品的重量；第二種就是最佳解不包含最後一個物品，那此時最大重量就是上一個物品時的最大重量 註：雖然我上面說過使用 DP 的時機是考慮的物件有一個自然的排序，但如果有時排序不影響解法，因為所有解都會被考慮進來，那就仍然可以使用。 具體演算法如下： ![image](https://hackmd.io/_uploads/Bkewrj9O-g.png) 舉例來說：
![image](https://hackmd.io/_uploads/ByVKSi5dbx.png) ### 時間複雜度：   這個演算法的時間複雜度 $O(nW)$，他是一個 pseudo polynomial running time，其時間複雜度會跟另一個題目給定值 $W$ 高度相關，因此不能算是 polynomial running time。 ## The Knapsack Problem （價值背包問題）   與上一個問題類似，但題目變成每個物品不只有一個重量還有一個價值，如何在背包承重範圍內取走價值總和最高的物品。   解法與上一個問題類似，只是遞迴函式要改成以價值做相加，修改如下： ![image](https://hackmd.io/_uploads/HkRxSINdWe.png)   以上被稱為 0/1 背包問題，可想而知還有 fractional 背包問題，跟 Bin Packing (多背包) 問題。有興趣可自行研究。 ## 最短路徑問題   這次，我們來看權重（花費）可以是負數的最短路徑問題。首先，大家可以思考為什麼不能使用 Dijkstra's Algorithm 求解。思考完後我來公佈解答，原因是 Dijkstra's Algorithm 這種貪婪演算法找的當下最佳解，會因為有負數的邊而使得小問題的解答組起來後不是最佳解。舉下面這個範例大家就可以瞭解了，使用 Dijkstra's Algorithm，s-t 的最短路徑永遠都是 1，因為第一步就確定了。
### 補充：修改後的 Dijkstra's Algorithm   也有 Dijkstra 的忠實信徒將權重做了某種調整後還是可以使用 Dijkstra's Algorithm，有興趣可以自行研究。 ### 解法：Bellman-Ford Algorithm   首先，我們先說明一個定理：「若圖 $G$ 沒有負迴圈，則圖中任兩點 $s,v$ 的 path 一定是 simple，並且最多經過 $n-1$ 條邊」。證明如下： ![image](https://hackmd.io/_uploads/ryMRHs5_-x.png)   之後我們便可以開始想這個性質是否可以用來解最短路徑問題，Bellman 跟 Ford 就想到以「邊的最多使用數量」來當作數學歸納法中「迭代的項」。   演算法首先令 $OPT(i,v)$ 為某點 $v$ 使用最多 $i$ 條邊至終點 $t$ 的最短路徑 $P$ 所產生的花費。請注意，這邊討論的是固定終點 $t$ 的情況，若要討論固定起點的情況，做法相同。接著，一樣，我們分兩種情況來討論 * Case 1: $P$ 僅使用 $i-1$ 條路徑，也就是使用 $i$ 條花費反而更大，因此用 $i-1$ 條的結果就好。 * $OPT(i,v)=OPT(i-1,v)$ * Case 2: $P$ 使用 $i$ 條路徑，也就是使用 $i$ 條花費更小。此時因為是固定終點的情況，因此第 $i$ 條邊必定是將節點 $v$ 指向某節點 $w$，而 $w$ 至 $t$ 會是使用 $i-1$ 條邊的最短路徑。 * $OPT(i,v)=c_{vw}+OPT(i-1,w)$ 這裡可能會很難理解，你需要記著我們分別在「花費」跟「邊的數量」這兩個維度裡設計演算法，接著繼續聽我講下去應該就能理解了。根據上面兩種情況，我們可以寫出遞迴關係式跟演算法： ![image](https://hackmd.io/_uploads/SJxJ8sc_We.png) ![image](https://hackmd.io/_uploads/S13yIoc_bx.png)   舉一個範例可能比較好理解，假設如下的情況，我們想找出每個節點至 $t$ 的最短路徑。
接著，我們可以列出下列表格，表個的最後一行代表每個節點到 $t$ 的最短路徑的花費。
  如果要知道某個節點的最短路徑，必須要回溯表格跟圖。舉例，我們想看節點 $b$ 的最短路徑，我們可以看他在邊的最多數量是 $5$ 時是怎麼操作的，他會看「邊的數量最多是 4 時自己到 $t$ 的最短路徑花費」跟「自己僅花 1 條邊便可到的所有節點（節點 $d$ 跟 $e$）只用最多 4 條邊便可以到 $t$ 的最短路徑花費」，之後選比較小花費的那個當作這次的決定。以此類推，便可以找出整條路徑。
### 複雜度 #### 空間複雜度   一般來說，我們要找到花費最小的最短路徑需要耗費 $O(n^2)$ 的記憶體來紀錄所有節點跟使用邊的數量的值。但如果我們今天只要看最短路徑的花費的話，我們其實只需要紀錄前一行的值就好，因為當下某行（某個邊的數量）的計算僅跟上一行有關。 #### 時間複雜度   正常看下來，演算法需要花費 $O(n^3)$ 的時間複雜度。但其實仔細分析後會發現，每個邊的數量的迴圈中，每個節點 $v$ 僅需計算自己的上一個值跟自己當下可以抵達並且邊數量最多為上一個邊數量的節點，也就是 $deg_{out}(v)+1$，而將所有節點的 $deg_{out}(v)+1$ 加總起來會發現總和最多就是 $m$，也就是邊的總數。因此實際時間複雜度為 $O(nm)$ ## Negative Cycle Detection   一開始我們就有說，如果一個圖有 negative cycle，那我們便無法找出其最短路徑。因此若要找一個圖的最短路徑，我們必須要先確定其有沒有 negative cycle。首先，我們介紹一個定理：「若 $OPT(n,v)=OPT(n-1,v)$，則此圖必存在 negative cycle」。怎麼說呢？我們知道如果此圖有最短路徑，我們一定可以用最多 $n-1$ 個邊求出，如果多加一個邊，也一定是最多用 $n-1$ 個邊便可以求出；但如果有 negative cycle，$OPT(n,v) ### 相關應用：貨幣交換 ![image](https://hackmd.io/_uploads/BylCa0c_We.png) ## Traveling Salesman Problem ### 問題描述   與前幾個題目相同，題目都是一張給定的有向權重圖。但這次我們會給定一個出發節點，我們的目標是找出可以經過所有其他節點一次並最終回到出發節點的最短路徑(最小花費路徑)。這個問題的由來是一位銷售員想要拜訪他所有的客戶一次，並希望儘快完成這項旅程。這個問題後來也被拿來說是幫聖誕老人規劃發禮物的最短路徑。問題看似有趣，實際解起來卻很困難，這個問題目前沒有人有辦法在 polynomial time 的時間求解出來。 ### 解法   這個問題如果用暴力解的話時間複雜度和空間複雜度分別是 $O(n!)$ 和 $O(n)$。1962 年時 Richard E. Bellman 使用 Dynamic Programming 將時間複雜度降至 $O(2^n n^3)$，但空間複雜度增加至 $O(2^n n^2)$。雖然仍舊很高，但其子問題的數量已被壓至多項式的數量。   其先令 $S$ 為一個元素數量大於等於 2 的節點集合，之後令 $OPT(S,u,v)$ 為從 $u$ 到 $v$ 的經過所有在 $S$ 裡的節點的最短路徑。而遞迴關係可以分成兩種情況 * Case 1: 集合中僅有兩個點 $S=\{u,v\}$ * $OPT(S,u,v)=d(u,v)$ * Case 2: 集合中超過兩個點 $|S| \geq 2$。此時令 $w\in S-\{u,v\}$ 為 $u$ 要到 $v$ 最先經過的一個節點，因此我們的遞迴關係式就可以寫成： * ![image](https://hackmd.io/_uploads/S1d8TpYOZg.png) 與上個問題類似，推出遞迴關係式便可以輕易完成演算法。   最後，給一個 Dynamic programming 的結論，使用 Dynamic programming 最重要的是要找出聰明且正確的關係式而不是填表。 ## 參考 [交大電機工程學系江蕙如老師演算法課程 OCW](https://ocw.nycu.edu.tw/?course_page=all-course%2Fcollege-of-electrical-and-computer-engineering%2F%E6%BC%94%E7%AE%97%E6%B3%95-algorithms-%E9%9B%BB%E6%A9%9F%E5%B7%A5%E7%A8%8B%E5%AD%B8%E7%B3%BB-%E6%B1%9F%E8%95%99%E5%A6%82%E8%80%81%E5%B8%AB)