|
動態(tài)規(guī)劃
在數(shù)學與計算機科學領(lǐng)域，動態(tài)規(guī)劃用于解決那些可分解為重復(fù)子問題（overlapping subproblems，想想遞歸求階乘吧）并具有最優(yōu)子結(jié)構(gòu)（optimal substructure，想想最短路徑算法）（如下所述）的問題，動態(tài)規(guī)劃比通常算法花費更少時間。 上世紀40年代，Richard Bellman最早使用動態(tài)規(guī)劃這一概念表述通過遍歷尋找最優(yōu)決策解問題的求解過程。1953年，Richard Bellman將動態(tài)規(guī)劃賦予現(xiàn)代意義，該領(lǐng)域被IEEE納入系統(tǒng)分析和工程中。為紀念Bellman的貢獻，動態(tài)規(guī)劃的核心方程被命名為貝爾曼方程，該方程以遞歸形式重申了一個優(yōu)化問題。 在“動態(tài)規(guī)劃”（dynamic programming）一詞中，programming與“計算機編程”（computer programming）中的programming并無關(guān)聯(lián)，而是來自“數(shù)學規(guī)劃”（mathematical programming），也稱優(yōu)化。因此，規(guī)劃是指對生成活動的優(yōu)化策略。舉個例子，編制一場展覽的日程可稱為規(guī)劃。 在此意義上，規(guī)劃意味著找到一個可行的活動計劃。
圖1 使用最優(yōu)子結(jié)構(gòu)尋找最短路徑：直線表示邊，波狀線表示兩頂點間的最短路徑（路徑中其他節(jié)點未顯示）；粗線表示從起點到終點的最短路徑。 不難看出，start到goal的最短路徑由start的相鄰節(jié)點到goal的最短路徑及start到其相鄰節(jié)點的成本決定。
最優(yōu)子結(jié)構(gòu)即可用來尋找整個問題最優(yōu)解的子問題的最優(yōu)解。舉例來說，尋找圖上某頂點到終點的最短路徑，可先計算該頂點所有相鄰頂點至終點的最短路徑，然后以此來選擇最佳整體路徑，如圖1所示。 一般而言，最優(yōu)子結(jié)構(gòu)通過如下三個步驟解決問題： a) 將問題分解成較小的子問題； b) 通過遞歸使用這三個步驟求出子問題的最優(yōu)解； c) 使用這些最優(yōu)解構(gòu)造初始問題的最優(yōu)解。 子問題的求解是通過不斷劃分為更小的子問題實現(xiàn)的，直至我們可以在常數(shù)時間內(nèi)求解。
圖2 Fibonacci序列的子問題示意圖：使用有向無環(huán)圖（DAG, directed acyclic graph）而非樹表示重復(fù)子問題的分解。 為什么是DAG而不是樹呢？答案就是，如果是樹的話，會有很多重復(fù)計算，下面有相關(guān)的解釋。
一個問題可劃分為重復(fù)子問題是指通過相同的子問題可以解決不同的較大問題。例如，在Fibonacci序列中，F(xiàn)3 = F1 + F2和F4 = F2 + F3都包含計算F2。由于計算F5需要計算F3和F4，一個比較笨的計算F5的方法可能會重復(fù)計算F2兩次甚至兩次以上。這一點對所有重復(fù)子問題都適用：愚蠢的做法可能會為重復(fù)計算已經(jīng)解決的最優(yōu)子問題的解而浪費時間。 為避免重復(fù)計算，可將已經(jīng)得到的子問題的解保存起來，當我們要解決相同的子問題時，重用即可。該方法即所謂的緩存（memoization，而不是存儲memorization，雖然這個詞亦適合，姑且這么叫吧，這個單詞太難翻譯了，簡直就是可意會不可言傳，其意義是沒計算過則計算，計算過則保存）。當我們確信將不會再需要某一解時，可以將其拋棄，以節(jié)省空間。在某些情況下，我們甚至可以提前計算出那些將來會用到的子問題的解。 總括而言，動態(tài)規(guī)劃利用： 1) 重復(fù)子問題 2) 最優(yōu)子結(jié)構(gòu) 3) 緩存 動態(tài)規(guī)劃通常采用以下兩種方式中的一種兩個辦法： 自頂向下：將問題劃分為若干子問題，求解這些子問題并保存結(jié)果以免重復(fù)計算。該方法將遞歸和緩存結(jié)合在一起。 自下而上：先行求解所有可能用到的子問題，然后用其構(gòu)造更大問題的解。該方法在節(jié)省堆?？臻g和減少函數(shù)調(diào)用數(shù)量上略有優(yōu)勢，但有時想找出給定問題的所有子問題并不那么直觀。 為了提高按名傳遞（call-by-name，這一機制與按需傳遞call-by-need相關(guān)，復(fù)習一下參數(shù)傳遞的各種規(guī)則吧，簡單說一下，按名傳遞允許改變實參值）的效率，一些編程語言將函數(shù)的返回值“自動”緩存在函數(shù)的特定參數(shù)集合中。一些語言將這一特性盡可能簡化（如Scheme、Common Lisp和Perl），也有一些語言需要進行特殊擴展（如C++，C++中使用的是按值傳遞和按引用傳遞，因此C++中本無自動緩存機制，需自行實現(xiàn)，具體實現(xiàn)的一個例子是Automated Memoization in C++）。無論如何，只有指稱透明（referentially transparent，指稱透明是指在程序中使用表達式、函數(shù)本身或以其值替換對程序結(jié)果沒有任何影響）函數(shù)才具有這一特性。
1. Fibonacci序列 尋找Fibonacci序列中第n個數(shù)，基于其數(shù)學定義的直接實現(xiàn)： function fib(n) 如果我們調(diào)用fib(5)，將產(chǎn)生一棵對于同一值重復(fù)計算多次的調(diào)用樹：
特別是，fib(2)計算了3次。在更大規(guī)模的例子中，還有更多fib的值被重復(fù)計算，將消耗指數(shù)級時間。 現(xiàn)在，假設(shè)我們有一個簡單的映射（map）對象m，為每一個計算過的fib及其返回值建立映射，修改上面的函數(shù)fib，使用并不斷更新m。新的函數(shù)將只需O(n)的時間，而非指數(shù)時間： var m := map(0 → 1, 1 → 1) 這一保存已計算出的數(shù)值的技術(shù)即被稱為緩存，這兒使用的是自頂向下的方法：先將問題劃分為若干子問題，然后計算和存儲值。 在自下而上的方法中，我們先計算較小的fib，然后基于其計算更大的fib。這種方法也只花費線性（O(n)）時間，因為它包含一個n-1次的循環(huán)。然而，這一方法只需要常數(shù)（O(1)）的空間，相反，自頂向下的方法則需要O(n)的空間來儲存映射關(guān)系。 function fib(n) 在這兩個例子，我們都只計算fib(2)一次，然后用它來計算fib(3)和fib(4)，而不是每次都重新計算。 2. 一種平衡的0-1矩陣 考慮n*n矩陣的賦值問題：只能賦0和1，n為偶數(shù)，使每一行和列均含n/2個0及n/2個1。例如，當n=4時，兩種可能的方案是： + - - - - + + - - - - + 問：對于給定n，共有多少種不同的賦值方案。 至少有三種可能的算法來解決這一問題：窮舉法（brute force）、回溯法（backtracking）及動態(tài)規(guī)劃（dynamic programming）。窮舉法列舉所有賦值方案，并逐一找出滿足平衡條件的方案。由于共有C(n, n/2)^n種方案（在一行中，含n/2個0及n/2個1的組合數(shù)為C(n,n/2)，相當于從n個位置中選取n/2個位置置0，剩下的自然是1），當n=6時，窮舉法就已經(jīng)幾乎不可行了。回溯法先將矩陣中部分元素置為0或1，然后檢查每一行和列中未被賦值的元素并賦值，使其滿足每一行和列中0和1的數(shù)量均為n/2。回溯法比窮舉法更加巧妙一些，但仍需遍歷所有解才能確定解的數(shù)目，可以看到，當n=8時，該題解的數(shù)目已經(jīng)高達116963796250。動態(tài)規(guī)劃則無需遍歷所有解便可確定解的數(shù)目（意思是劃分子問題后，可有效避免若干子問題的重復(fù)計算）。 通過動態(tài)規(guī)劃求解該問題出乎意料的簡單?？紤]每一行恰含n/2個0和n/2個1的k*n(1<=k<=n)的子矩陣，函數(shù)f根據(jù)每一行的可能的賦值映射為一個向量，每個向量由n個整數(shù)對構(gòu)成。向量每一列對應(yīng)的一個整數(shù)對中的兩個整數(shù)分別表示該列上該行以下已經(jīng)放置的0和1的數(shù)量。該問題即轉(zhuǎn)化為尋找f((n/2,n/2),(n/2,n/2),...,(n/2,n/2))（具有n個參數(shù)或者說是一個含n個元素的向量）的值。其子問題的構(gòu)造過程如下： 1) 最上面一行（第k行）具有C(n, n/2)種賦值； 2) 根據(jù)最上面一行中每一列的賦值情況（為0或1），將其對應(yīng)整數(shù)對中相應(yīng)的元素值減1； 3) 如果任一整數(shù)對中的任一元素為負，則該賦值非法，不能成為正確解； 4) 否則，完成對k*n的子矩陣中最上面一行的賦值，取k=k-1，計算剩余的(k-1)*n的子矩陣的賦值； 5) 基本情況是一個1*n的細小的子問題，此時，該子問題的解的數(shù)量為0或1，取決于其向量是否是n/2個(0, 1)和n/2個(1, 0)的排列。 例如，在上面給出的兩種方案中，向量序列為： ((2, 2) (2, 2) (2, 2) (2, 2)) ((2, 2) (2, 2) (2, 2) (2, 2)) k =
4 ((1, 2) (2, 1) (1, 2) (2, 1)) ((1, 2) (1, 2) (2, 1) (2, 1)) k =
3 ((1, 1) (1, 1) (1, 1) (1, 1)) ((0, 2) (0, 2) (2, 0) (2, 0)) k =
2 ((0, 1) (1, 0) (0, 1) (1, 0)) ((0, 1) (0, 1) (1, 0) (1, 0)) k =
1 ((0, 0) (0, 0) (0, 0) (0, 0)) ((0, 0) (0, 0), (0, 0) (0, 0)) 動態(tài)規(guī)劃在此的意義在于避免了相同f的重復(fù)計算，更進一步的，上面著色的兩個f，雖然對應(yīng)向量不同，但f的值是相同的，想想為什么吧:D。 該問題解的數(shù)量（序列a058527在OEIS）是1, 2, 90, 297200, 116963796250, 6736218287430460752, ... 下面的外部鏈接中包含回溯法的Perl源代碼實現(xiàn)，以及動態(tài)規(guī)劃法的MAPLE和C語言的實現(xiàn)。 3. 棋盤 考慮n*n的棋盤及成本函數(shù)C(i,j)，該函數(shù)返回方格(i,j)相關(guān)的成本。以5*5的棋盤為例： 5 | 6 7 4 7 8 可以看到：C(1,3)=5 從棋盤的任一方格的第一階（即行）開始，尋找到達最后一階的最短路徑（使所有經(jīng)過的方格的成本之和最?。?，假定只允許向左對角、右對角或垂直移動一格。 5 | 該問題展示了最優(yōu)子結(jié)構(gòu)。即整個問題的全局解依賴于子問題的解。定義函數(shù)q(i,j)，令：q(i,j)表示到達方格(i,j)的最低成本。 如果我們可以求出第n階所有方格的q(i,j)值，取其最小值并逆向該路徑即可得到最短路徑。 記q(i,j)為方格(i,j)至其下三個方格（(i-1,j-1)、(i-1,j)、(i-1,j+1)）最低成本與c(i,j)之和，例如： 5 | q(A) = min(q(B),q(C),q(D)) + c(A) 定義q(i,j)的一般形式： |- inf.
j<1 or j>n 方程的第一行是為了保證遞歸可以退出（處理邊界時只需調(diào)用一次遞歸函數(shù)）。第二行是第一階的取值，作為計算的起點。第三行的遞歸是算法的重要組成部分，與例子A、B、C、D類似。從該定義我們可以直接給出計算q(i,j)的簡單的遞歸代碼。在下面的偽代碼中，n表示棋盤的維數(shù)，C(i,j)是成本函數(shù)，min()返回一組數(shù)的最小值： function minCost(i, j) 需要指出的是，minCost只計算路徑成本，并不是最終的實際路徑，二者相去不遠。與Fibonacci數(shù)相似，由于花費大量時間重復(fù)計算相同的最短路徑，這一方式慢的恐怖。不過，如果采用自下而上法，使用二維數(shù)組q[i,j]代替函數(shù)minCost，將使計算過程快得多。我們?yōu)槭裁匆@樣做呢？選擇保存值顯然比使用函數(shù)重復(fù)計算相同路徑要簡單的多。 我們還需要知道實際路徑。路徑問題，我們可以通過另一個前任數(shù)組p[i,j]解決。這個數(shù)組用于描述路徑，代碼如下： function computeShortestPathArrays() 剩下的求最小值和輸出就比較簡單了： function computeShortestPath() function printPath(y, x) 4. 序列比對 序列比對是動態(tài)規(guī)劃的一個重要應(yīng)用。序列比對問題通常是使用編輯操作（替換、插入、刪除一個要素等）進行序列轉(zhuǎn)換。每次操作對應(yīng)不同成本，目標是找到編輯序列的最低成本。 可以很自然地想到使用遞歸解決這個問題，序列A到B的最優(yōu)編輯通過以下措施之一實現(xiàn)： 插入B的第一個字符，對A和B的剩余序列進行最優(yōu)比對； 刪去A的第一個字符，對A和B進行最優(yōu)比對； 用B的第一個字符替換A的第一個字符，對A的剩余序列和B進行最優(yōu)比對。 局部比對可在矩陣中列表表示，單元(i,j)表示A[1..i]到b[1..j]最優(yōu)比對的成本。單元(i,j)的成本計算可通過累加相鄰單元的操作成本并選擇最優(yōu)解實現(xiàn)。至于序列比對的不同實現(xiàn)算法，參見Smith-Waterman和Needleman-Wunsch。 對序列比對的話題并不熟悉，更多的話也無從談起，有熟悉的朋友倒是可以介紹一下。
1) 許多字符串操作算法如最長公共子列、最長遞增子列、最長公共字串； 2) 將動態(tài)規(guī)劃用于圖的樹分解，可以有效解決有界樹寬圖的生成樹等許多與圖相關(guān)的算法問題； 3) 決定是否及如何可以通過某一特定上下文無關(guān)文法產(chǎn)生給定字符串的Cocke-Younger-Kasami (CYK)算法； 4) 計算機國際象棋中轉(zhuǎn)換表和駁斥表的使用； 5) Viterbi算法（用于隱式馬爾可夫模型）； 6) Earley算法（一類圖表分析器）； 7) Needleman-Wunsch及其他生物信息學中使用的算法，包括序列比對、結(jié)構(gòu)比對、RNA結(jié)構(gòu)預(yù)測； 8) Levenshtein距離（編輯距離）； 9) 弗洛伊德最短路徑算法； 10) 連鎖矩陣乘法次序優(yōu)化； 11) 子集求和、背包問題和分治問題的偽多項式時間算法； 12) 計算兩個時間序列全局距離的動態(tài)時間規(guī)整算法； 13) 關(guān)系型數(shù)據(jù)庫的查詢優(yōu)化的Selinger（又名System R）算法； 14) 評價B樣條曲線的De Boor算法； 15) 用于解決板球運動中斷問題的Duckworth-Lewis方法； 16) 價值迭代法求解馬爾可夫決策過程； 17) 一些圖形圖像邊緣以下的選擇方法，如“磁鐵”選擇工具在Photoshop； 18) 間隔調(diào)度； 19) 自動換行； 20) 巡回旅行商問題（又稱郵差問題或貨擔郎問題）； 21) 分段最小二乘法； 22) 音樂信息檢索跟蹤。 對于這些算法應(yīng)用，大多未曾接觸，甚至術(shù)語翻譯的都有問題，鑒于本文主要在于介紹動態(tài)規(guī)劃，所以倉促之中，未及查證。
1) 貝爾曼方程 2) 馬爾可夫決策過程 3) 貪心算法 |
|
|
