游戲人生

以前在學(xué)習(xí)非數(shù)值算法的時(shí)候，曾經(jīng)了解過(guò)動(dòng)態(tài)規(guī)劃算法（Dynamic programming），以下是對(duì)Wikipedia上動(dòng)態(tài)規(guī)劃的翻譯，圖也是Wikipedia上的，倉(cāng)促行文，不到之處，請(qǐng)方家指正。

這篇文章的術(shù)語(yǔ)實(shí)在是太多了，所以我在文中加入了少量注釋，一律以粗斜體注明。

本文的不足之處將隨時(shí)修正，MIT的《Introduction to Algorithms》第15章是專門講動(dòng)態(tài)規(guī)劃的。

_____________________________________________________________

動(dòng)態(tài)規(guī)劃

在數(shù)學(xué)與計(jì)算機(jī)科學(xué)領(lǐng)域，動(dòng)態(tài)規(guī)劃用于解決那些可分解為重復(fù)子問(wèn)題（overlapping subproblems，想想遞歸求階乘吧）并具有最優(yōu)子結(jié)構(gòu)（optimal substructure，想想最短路徑算法）（如下所述）的問(wèn)題，動(dòng)態(tài)規(guī)劃比通常算法花費(fèi)更少時(shí)間。

上世紀(jì)40年代，Richard Bellman最早使用動(dòng)態(tài)規(guī)劃這一概念表述通過(guò)遍歷尋找最優(yōu)決策解問(wèn)題的求解過(guò)程。1953年，Richard Bellman將動(dòng)態(tài)規(guī)劃賦予現(xiàn)代意義，該領(lǐng)域被IEEE納入系統(tǒng)分析和工程中。為紀(jì)念Bellman的貢獻(xiàn)，動(dòng)態(tài)規(guī)劃的核心方程被命名為貝爾曼方程，該方程以遞歸形式重申了一個(gè)優(yōu)化問(wèn)題。

在“動(dòng)態(tài)規(guī)劃”（dynamic programming）一詞中，programming與“計(jì)算機(jī)編程”（computer programming）中的programming并無(wú)關(guān)聯(lián)，而是來(lái)自“數(shù)學(xué)規(guī)劃”（mathematical programming），也稱優(yōu)化。因此，規(guī)劃是指對(duì)生成活動(dòng)的優(yōu)化策略。舉個(gè)例子，編制一場(chǎng)展覽的日程可稱為規(guī)劃。 在此意義上，規(guī)劃意味著找到一個(gè)可行的活動(dòng)計(jì)劃。

• 概述

圖1 使用最優(yōu)子結(jié)構(gòu)尋找最短路徑：直線表示邊，波狀線表示兩頂點(diǎn)間的最短路徑（路徑中其他節(jié)點(diǎn)未顯示）；粗線表示從起點(diǎn)到終點(diǎn)的最短路徑。

不難看出，start到goal的最短路徑由start的相鄰節(jié)點(diǎn)到goal的最短路徑及start到其相鄰節(jié)點(diǎn)的成本決定。

最優(yōu)子結(jié)構(gòu)即可用來(lái)尋找整個(gè)問(wèn)題最優(yōu)解的子問(wèn)題的最優(yōu)解。舉例來(lái)說(shuō)，尋找圖上某頂點(diǎn)到終點(diǎn)的最短路徑，可先計(jì)算該頂點(diǎn)所有相鄰頂點(diǎn)至終點(diǎn)的最短路徑，然后以此來(lái)選擇最佳整體路徑，如圖1所示。

一般而言，最優(yōu)子結(jié)構(gòu)通過(guò)如下三個(gè)步驟解決問(wèn)題：

a) 將問(wèn)題分解成較小的子問(wèn)題；

b) 通過(guò)遞歸使用這三個(gè)步驟求出子問(wèn)題的最優(yōu)解；

c) 使用這些最優(yōu)解構(gòu)造初始問(wèn)題的最優(yōu)解。

子問(wèn)題的求解是通過(guò)不斷劃分為更小的子問(wèn)題實(shí)現(xiàn)的，直至我們可以在常數(shù)時(shí)間內(nèi)求解。

圖2 Fibonacci序列的子問(wèn)題示意圖：使用有向無(wú)環(huán)圖（DAG, directed acyclic graph）而非樹表示重復(fù)子問(wèn)題的分解。

為什么是DAG而不是樹呢？答案就是，如果是樹的話，會(huì)有很多重復(fù)計(jì)算，下面有相關(guān)的解釋。

一個(gè)問(wèn)題可劃分為重復(fù)子問(wèn)題是指通過(guò)相同的子問(wèn)題可以解決不同的較大問(wèn)題。例如，在Fibonacci序列中，F(xiàn)3 = F1 + F2和F4 = F2 + F3都包含計(jì)算F2。由于計(jì)算F5需要計(jì)算F3和F4，一個(gè)比較笨的計(jì)算F5的方法可能會(huì)重復(fù)計(jì)算F2兩次甚至兩次以上。這一點(diǎn)對(duì)所有重復(fù)子問(wèn)題都適用：愚蠢的做法可能會(huì)為重復(fù)計(jì)算已經(jīng)解決的最優(yōu)子問(wèn)題的解而浪費(fèi)時(shí)間。

為避免重復(fù)計(jì)算，可將已經(jīng)得到的子問(wèn)題的解保存起來(lái)，當(dāng)我們要解決相同的子問(wèn)題時(shí)，重用即可。該方法即所謂的緩存（memoization，而不是存儲(chǔ)memorization，雖然這個(gè)詞亦適合，姑且這么叫吧，這個(gè)單詞太難翻譯了，簡(jiǎn)直就是可意會(huì)不可言傳，其意義是沒(méi)計(jì)算過(guò)則計(jì)算，計(jì)算過(guò)則保存）。當(dāng)我們確信將不會(huì)再需要某一解時(shí)，可以將其拋棄，以節(jié)省空間。在某些情況下，我們甚至可以提前計(jì)算出那些將來(lái)會(huì)用到的子問(wèn)題的解。

總括而言，動(dòng)態(tài)規(guī)劃利用：

1) 重復(fù)子問(wèn)題

2) 最優(yōu)子結(jié)構(gòu)

3) 緩存

動(dòng)態(tài)規(guī)劃通常采用以下兩種方式中的一種兩個(gè)辦法：

自頂向下：將問(wèn)題劃分為若干子問(wèn)題，求解這些子問(wèn)題并保存結(jié)果以免重復(fù)計(jì)算。該方法將遞歸和緩存結(jié)合在一起。

自下而上：先行求解所有可能用到的子問(wèn)題，然后用其構(gòu)造更大問(wèn)題的解。該方法在節(jié)省堆?？臻g和減少函數(shù)調(diào)用數(shù)量上略有優(yōu)勢(shì)，但有時(shí)想找出給定問(wèn)題的所有子問(wèn)題并不那么直觀。

為了提高按名傳遞（call-by-name，這一機(jī)制與按需傳遞call-by-need相關(guān)，復(fù)習(xí)一下參數(shù)傳遞的各種規(guī)則吧，簡(jiǎn)單說(shuō)一下，按名傳遞允許改變實(shí)參值）的效率，一些編程語(yǔ)言將函數(shù)的返回值“自動(dòng)”緩存在函數(shù)的特定參數(shù)集合中。一些語(yǔ)言將這一特性盡可能簡(jiǎn)化（如Scheme、Common Lisp和Perl），也有一些語(yǔ)言需要進(jìn)行特殊擴(kuò)展（如C++，C++中使用的是按值傳遞和按引用傳遞，因此C++中本無(wú)自動(dòng)緩存機(jī)制，需自行實(shí)現(xiàn)，具體實(shí)現(xiàn)的一個(gè)例子是Automated Memoization in C++）。無(wú)論如何，只有指稱透明（referentially transparent，指稱透明是指在程序中使用表達(dá)式、函數(shù)本身或以其值替換對(duì)程序結(jié)果沒(méi)有任何影響）函數(shù)才具有這一特性。

• 例子

1. Fibonacci序列

尋找Fibonacci序列中第n個(gè)數(shù)，基于其數(shù)學(xué)定義的直接實(shí)現(xiàn)：

   function fib(n)
       if n = 0
           return 0
       else if n = 1
           return 1
       return fib(n-1) + fib(n-2)

如果我們調(diào)用fib(5)，將產(chǎn)生一棵對(duì)于同一值重復(fù)計(jì)算多次的調(diào)用樹：

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

特別是，fib(2)計(jì)算了3次。在更大規(guī)模的例子中，還有更多fib的值被重復(fù)計(jì)算，將消耗指數(shù)級(jí)時(shí)間。

現(xiàn)在，假設(shè)我們有一個(gè)簡(jiǎn)單的映射（map）對(duì)象m，為每一個(gè)計(jì)算過(guò)的fib及其返回值建立映射，修改上面的函數(shù)fib，使用并不斷更新m。新的函數(shù)將只需O(n)的時(shí)間，而非指數(shù)時(shí)間：

   var m := map(0 → 1, 1 → 1)
   function fib(n)
       if map m does not contain key n
           m[n] := fib(n-1) + fib(n-2)
       return m[n]

這一保存已計(jì)算出的數(shù)值的技術(shù)即被稱為緩存，這兒使用的是自頂向下的方法：先將問(wèn)題劃分為若干子問(wèn)題，然后計(jì)算和存儲(chǔ)值。

在自下而上的方法中，我們先計(jì)算較小的fib，然后基于其計(jì)算更大的fib。這種方法也只花費(fèi)線性（O(n)）時(shí)間，因?yàn)樗粋€(gè)n-1次的循環(huán)。然而，這一方法只需要常數(shù)（O(1)）的空間，相反，自頂向下的方法則需要O(n)的空間來(lái)儲(chǔ)存映射關(guān)系。

   function fib(n)
       var previousFib := 0, currentFib := 1
       if n = 0
           return 0
       else if n = 1
           return 1
       repeat n-1 times
           var newFib := previousFib + currentFib
           previousFib := currentFib
           currentFib  := newFib
       return currentFib

在這兩個(gè)例子，我們都只計(jì)算fib(2)一次，然后用它來(lái)計(jì)算fib(3)和fib(4)，而不是每次都重新計(jì)算。

2. 一種平衡的0-1矩陣

考慮n*n矩陣的賦值問(wèn)題：只能賦0和1，n為偶數(shù)，使每一行和列均含n/2個(gè)0及n/2個(gè)1。例如，當(dāng)n=4時(shí)，兩種可能的方案是：

+ - - - - +             + - - - - +
| 0 1 0 1 |             | 0 0 1 1 |
| 1 0 1 0 |             | 0 0 1 1 |
| 0 1 0 1 |             | 1 1 0 0 |
| 1 0 1 0 |             | 1 1 0 0 |
+ - - - - +             + - - - - +

問(wèn)：對(duì)于給定n，共有多少種不同的賦值方案。

至少有三種可能的算法來(lái)解決這一問(wèn)題：窮舉法（brute force）、回溯法（backtracking）及動(dòng)態(tài)規(guī)劃（dynamic programming）。窮舉法列舉所有賦值方案，并逐一找出滿足平衡條件的方案。由于共有C(n, n/2)^n種方案（在一行中，含n/2個(gè)0及n/2個(gè)1的組合數(shù)為C(n,n/2)，相當(dāng)于從n個(gè)位置中選取n/2個(gè)位置置0，剩下的自然是1），當(dāng)n=6時(shí)，窮舉法就已經(jīng)幾乎不可行了?；厮莘ㄏ葘⒕仃囍胁糠衷刂脼?或1，然后檢查每一行和列中未被賦值的元素并賦值，使其滿足每一行和列中0和1的數(shù)量均為n/2。回溯法比窮舉法更加巧妙一些，但仍需遍歷所有解才能確定解的數(shù)目，可以看到，當(dāng)n=8時(shí)，該題解的數(shù)目已經(jīng)高達(dá)116963796250。動(dòng)態(tài)規(guī)劃則無(wú)需遍歷所有解便可確定解的數(shù)目（意思是劃分子問(wèn)題后，可有效避免若干子問(wèn)題的重復(fù)計(jì)算）。

通過(guò)動(dòng)態(tài)規(guī)劃求解該問(wèn)題出乎意料的簡(jiǎn)單?？紤]每一行恰含n/2個(gè)0和n/2個(gè)1的k*n(1<=k<=n)的子矩陣，函數(shù)f根據(jù)每一行的可能的賦值映射為一個(gè)向量，每個(gè)向量由n個(gè)整數(shù)對(duì)構(gòu)成。向量每一列對(duì)應(yīng)的一個(gè)整數(shù)對(duì)中的兩個(gè)整數(shù)分別表示該列上該行以下已經(jīng)放置的0和1的數(shù)量。該問(wèn)題即轉(zhuǎn)化為尋找f((n/2,n/2),(n/2,n/2),...,(n/2,n/2))（具有n個(gè)參數(shù)或者說(shuō)是一個(gè)含n個(gè)元素的向量）的值。其子問(wèn)題的構(gòu)造過(guò)程如下：

1) 最上面一行（第k行）具有C(n, n/2)種賦值；

2) 根據(jù)最上面一行中每一列的賦值情況（為0或1），將其對(duì)應(yīng)整數(shù)對(duì)中相應(yīng)的元素值減1；

3) 如果任一整數(shù)對(duì)中的任一元素為負(fù)，則該賦值非法，不能成為正確解；

4) 否則，完成對(duì)k*n的子矩陣中最上面一行的賦值，取k=k-1，計(jì)算剩余的(k-1)*n的子矩陣的賦值；

5) 基本情況是一個(gè)1*n的細(xì)小的子問(wèn)題，此時(shí)，該子問(wèn)題的解的數(shù)量為0或1，取決于其向量是否是n/2個(gè)(0, 1)和n/2個(gè)(1, 0)的排列。

例如，在上面給出的兩種方案中，向量序列為：

((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0       0       1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))

動(dòng)態(tài)規(guī)劃在此的意義在于避免了相同f的重復(fù)計(jì)算，更進(jìn)一步的，上面著色的兩個(gè)f，雖然對(duì)應(yīng)向量不同，但f的值是相同的，想想為什么吧:D。

該問(wèn)題解的數(shù)量（序列a058527在OEIS）是1, 2, 90, 297200, 116963796250, 6736218287430460752, ...

下面的外部鏈接中包含回溯法的Perl源代碼實(shí)現(xiàn)，以及動(dòng)態(tài)規(guī)劃法的MAPLE和C語(yǔ)言的實(shí)現(xiàn)。

3. 棋盤

考慮n*n的棋盤及成本函數(shù)C(i,j)，該函數(shù)返回方格(i,j)相關(guān)的成本。以5*5的棋盤為例：

5 | 6 7 4 7 8
4 | 7 6 1 1 4
3 | 3 5 7 8 2
2 | 2 6 7 0 2
1 | 7 3 5 6 1
- + - - - - -
  | 1 2 3 4 5

可以看到：C(1,3)=5

從棋盤的任一方格的第一階（即行）開始，尋找到達(dá)最后一階的最短路徑（使所有經(jīng)過(guò)的方格的成本之和最小），假定只允許向左對(duì)角、右對(duì)角或垂直移動(dòng)一格。

5 |
4 |
3 |
2 |   x x x
1 |     o
- + - - - - -
  | 1 2 3 4 5

該問(wèn)題展示了最優(yōu)子結(jié)構(gòu)。即整個(gè)問(wèn)題的全局解依賴于子問(wèn)題的解。定義函數(shù)q(i,j)，令：q(i,j)表示到達(dá)方格(i,j)的最低成本。

如果我們可以求出第n階所有方格的q(i,j)值，取其最小值并逆向該路徑即可得到最短路徑。

記q(i,j)為方格(i,j)至其下三個(gè)方格（(i-1,j-1)、(i-1,j)、(i-1,j+1)）最低成本與c(i,j)之和，例如：

5 |
4 |     A
3 |   B C D
2 |
1 |
- + - - - - -
  | 1 2 3 4 5

q(A) = min(q(B),q(C),q(D)) + c(A)

定義q(i,j)的一般形式：

            |-  inf.                                                  j<1 or j>n
q(i,j) = -+-  c(i,j)                                                i=1
            |-  min(q(i-1,j-1),q(i-1,j),q(i-1,j+1))+c(i,j)   otherwise.

方程的第一行是為了保證遞歸可以退出（處理邊界時(shí)只需調(diào)用一次遞歸函數(shù)）。第二行是第一階的取值，作為計(jì)算的起點(diǎn)。第三行的遞歸是算法的重要組成部分，與例子A、B、C、D類似。從該定義我們可以直接給出計(jì)算q(i,j)的簡(jiǎn)單的遞歸代碼。在下面的偽代碼中，n表示棋盤的維數(shù)，C(i,j)是成本函數(shù)，min()返回一組數(shù)的最小值：

function minCost(i, j)
    if j < 1 or j > n
        return infinity
    else if i = 1
        return c(i,j)
    else
        return min(minCost(i-1,j-1),minCost(i-1,j),minCost(i-1,j+1))+c(i,j)

需要指出的是，minCost只計(jì)算路徑成本，并不是最終的實(shí)際路徑，二者相去不遠(yuǎn)。與Fibonacci數(shù)相似，由于花費(fèi)大量時(shí)間重復(fù)計(jì)算相同的最短路徑，這一方式慢的恐怖。不過(guò)，如果采用自下而上法，使用二維數(shù)組q[i,j]代替函數(shù)minCost，將使計(jì)算過(guò)程快得多。我們?yōu)槭裁匆@樣做呢？選擇保存值顯然比使用函數(shù)重復(fù)計(jì)算相同路徑要簡(jiǎn)單的多。

我們還需要知道實(shí)際路徑。路徑問(wèn)題，我們可以通過(guò)另一個(gè)前任數(shù)組p[i,j]解決。這個(gè)數(shù)組用于描述路徑，代碼如下：

function computeShortestPathArrays()
     for x from 1 to n
         q[1, x] := c(1, x)
     for y from 1 to n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     for y from 2 to n
         for x from 1 to n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x)
             if m = q[y-1, x-1]
                 p[y, x] := -1
             else if m = q[y-1, x]
                 p[y, x] :=  0
             else
                 p[y, x] :=  1

剩下的求最小值和輸出就比較簡(jiǎn)單了：

function computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1]
     for i from 2 to n
         if q[n, i] < min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

function printPath(y, x)
     print(x)
     print("<-")
     if y = 2
         print(x + p[y, x])
     else
         printPath(y-1, x + p[y, x])

4. 序列比對(duì)

序列比對(duì)是動(dòng)態(tài)規(guī)劃的一個(gè)重要應(yīng)用。序列比對(duì)問(wèn)題通常是使用編輯操作（替換、插入、刪除一個(gè)要素等）進(jìn)行序列轉(zhuǎn)換。每次操作對(duì)應(yīng)不同成本，目標(biāo)是找到編輯序列的最低成本。

可以很自然地想到使用遞歸解決這個(gè)問(wèn)題，序列A到B的最優(yōu)編輯通過(guò)以下措施之一實(shí)現(xiàn)：

插入B的第一個(gè)字符，對(duì)A和B的剩余序列進(jìn)行最優(yōu)比對(duì)；

刪去A的第一個(gè)字符，對(duì)A和B進(jìn)行最優(yōu)比對(duì)；

用B的第一個(gè)字符替換A的第一個(gè)字符，對(duì)A的剩余序列和B進(jìn)行最優(yōu)比對(duì)。

局部比對(duì)可在矩陣中列表表示，單元(i,j)表示A[1..i]到b[1..j]最優(yōu)比對(duì)的成本。單元(i,j)的成本計(jì)算可通過(guò)累加相鄰單元的操作成本并選擇最優(yōu)解實(shí)現(xiàn)。至于序列比對(duì)的不同實(shí)現(xiàn)算法，參見(jiàn)Smith-Waterman和Needleman-Wunsch。

對(duì)序列比對(duì)的話題并不熟悉，更多的話也無(wú)從談起，有熟悉的朋友倒是可以介紹一下。

• 應(yīng)用動(dòng)態(tài)規(guī)劃的算法

1) 許多字符串操作算法如最長(zhǎng)公共子列、最長(zhǎng)遞增子列、最長(zhǎng)公共字串；

2) 將動(dòng)態(tài)規(guī)劃用于圖的樹分解，可以有效解決有界樹寬圖的生成樹等許多與圖相關(guān)的算法問(wèn)題；

3) 決定是否及如何可以通過(guò)某一特定上下文無(wú)關(guān)文法產(chǎn)生給定字符串的Cocke-Younger-Kasami (CYK)算法；

4) 計(jì)算機(jī)國(guó)際象棋中轉(zhuǎn)換表和駁斥表的使用；

5) Viterbi算法（用于隱式馬爾可夫模型）；

6) Earley算法（一類圖表分析器）；

7) Needleman-Wunsch及其他生物信息學(xué)中使用的算法，包括序列比對(duì)、結(jié)構(gòu)比對(duì)、RNA結(jié)構(gòu)預(yù)測(cè)；

8) Levenshtein距離（編輯距離）；

9) 弗洛伊德最短路徑算法；

10) 連鎖矩陣乘法次序優(yōu)化；

11) 子集求和、背包問(wèn)題和分治問(wèn)題的偽多項(xiàng)式時(shí)間算法；

12) 計(jì)算兩個(gè)時(shí)間序列全局距離的動(dòng)態(tài)時(shí)間規(guī)整算法；

13) 關(guān)系型數(shù)據(jù)庫(kù)的查詢優(yōu)化的Selinger（又名System R）算法；

14) 評(píng)價(jià)B樣條曲線的De Boor算法；

15) 用于解決板球運(yùn)動(dòng)中斷問(wèn)題的Duckworth-Lewis方法；

16) 價(jià)值迭代法求解馬爾可夫決策過(guò)程；

17) 一些圖形圖像邊緣以下的選擇方法，如“磁鐵”選擇工具在Photoshop；

18) 間隔調(diào)度；

19) 自動(dòng)換行；

20) 巡回旅行商問(wèn)題（又稱郵差問(wèn)題或貨擔(dān)郎問(wèn)題）；

21) 分段最小二乘法；

22) 音樂(lè)信息檢索跟蹤。

對(duì)于這些算法應(yīng)用，大多未曾接觸，甚至術(shù)語(yǔ)翻譯的都有問(wèn)題，鑒于本文主要在于介紹動(dòng)態(tài)規(guī)劃，所以倉(cāng)促之中，未及查證。

• 相關(guān)

1) 貝爾曼方程

2) 馬爾可夫決策過(guò)程

3) 貪心算法

• 參考