原作者：金子冴
校閱：內(nèi)野良一
翻譯：葉子
原文鏈接

目錄

• 什么是動態(tài)規(guī)劃(Dynamic Programming)
• 例題：用Dijkstra的方法解決最短路徑問題(Python實現(xiàn))
• 使用動態(tài)規(guī)劃解決問題的步驟
• 參考

什么是動態(tài)規(guī)劃(Dynamic Programming)

動態(tài)規(guī)劃概要

動態(tài)規(guī)劃是一種解題手法的總稱。它通過將一個無法解決的大問題分解成復(fù)數(shù)個小問題(也叫子問題)，然后在解決這些小問題的基礎(chǔ)之上來解決原始的大問題。通過使用動態(tài)規(guī)劃，我們能將一部分在多項式時間內(nèi)無法解決的問題，在類似多項式的時間內(nèi)求得最優(yōu)解(稍后會進行說明)。
判斷一個問題是否可以通過動態(tài)規(guī)劃來解決的時，我們需要判斷該問題是否滿足可分治(分而治之)和可記憶(將階段性成果進行緩存，便于重復(fù)利用)兩個條件。首先，讓我們先去理解:多項式時間、分而治之、以及記憶化(Memoization)。

什么是多項式時間，什么是多項式時間算法

多項式時間是指由多項式表示的計算時間。多項式時間算法是指當(dāng)入力的大小(長度或者個數(shù))是n的時候，計算時間(執(zhí)行步數(shù))的上限在n的多項式時間內(nèi)能夠表示的算法。比如，計算九九乘法表的算法的計算時間可以表示為9x9。將其擴展到nxn的時候，計算時間用大O記法來表示的話，可以表示為O(n2)。這表明該算法的計算時間的上限可以用n2來表示，因此計算nxn的乘法的算法可以說是多項式算法。
但是，在多項式時間內(nèi)無法解決的問題也是存在的，比如說接下來將要說明的最短路徑問題，在多項式時間內(nèi)就無法解決。如下圖所示的加權(quán)路線圖，找一個從START開始到到達GOAL的花費最短(權(quán)重最小)的路線。

為了求最短路線，我們需要考慮全部路線的排列組合，在此基礎(chǔ)之上進行花費的計算，要使得花費最小，那就需要找到最短的路徑。像這樣的問題，入力的規(guī)模每增大一點，路線的組合就呈指數(shù)級增加，因此計算全部路線的花費是不現(xiàn)實的。但是，如果使用了動態(tài)規(guī)劃，就可以求得類似最短路徑這樣的在多項式時間內(nèi)無法解決的問題的最優(yōu)解。計算時會使用分而治之和記憶化兩種手法。

什么是分而治之(分治)

分治指的是將目標(biāo)問題分割成復(fù)數(shù)個子問題的手法。讓我們試著將剛才提到的最短路徑問題進行子問題分解。對于剛才提到的例子，首先不要去考慮從START開始能夠到達END的所有路線，而應(yīng)該只考慮在某個時間點能夠推進的路線。所以對于最開始的路線，只需要考慮START到a，b，c，d這四條。考慮到我們要解決的是最短路徑的問題，這里我們選擇從START開始花費最小的START->b路線開始。接著，我們只需考慮從b點出發(fā)能夠推進的路線，這里我們也是選擇花費最少的路線，b->g路線。

像這樣，將一個需要考慮全部路徑的問題轉(zhuǎn)換為只考慮某個時間點能夠推進的路線的問題(子問題)的分治手法，叫做分而治之。

什么是記憶化

記憶化是指將計算結(jié)果保存到內(nèi)存上，之后再次利用的手法。作為解釋記憶化的例子，讓我們來思考一下斐波那契數(shù)列的問題。這里我們省略斐波那契數(shù)列數(shù)列的說明。使用python進行斐波那契數(shù)列計算的場合，代碼編寫如下所示：

清單1

CulcFibonacci.py

          
            import sys

# フィボナッチ數(shù)の計算
def culc_fibonacci(n):
    if n > 1:
        return culc_fibonacci(n-1) + culc_fibonacci(n-2)
    elif n == 1:
        return 1
    else:
        return 0

def main():
    # 1～10番目フィボナッチ數(shù)列を表示
    #     ?　0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    for n in range(10):
        fibonacci_n = culc_fibonacci(n)
        print(fibonacci_n, end='')
        if not  n == 9:
            print(', ', end='')


if __name__ == '__main__':
    main()
    sys.exit(0)

          
        

但是，清單1所示代碼，在計算n=10的時候，必須去計算n=9～1，因此計算時間是O(αn:α的n次冪)(α:實數(shù))，所以當(dāng)n變大的時候，相關(guān)的計算量會呈指數(shù)級增長。
下圖表示的是斐波那契數(shù)列的計算過程。從下圖我們可以看出，除了f(10)之外的所有計算都不止一次。

將清單所示代碼用記憶化進行優(yōu)化的時候，如何減少復(fù)數(shù)次計算是重點。為了進行記憶化，我們需要做一個記憶化表，將第一次計算的值存儲到該表之中。

這樣，當(dāng)我們需要再次計算某個值的時候，直接去該表當(dāng)中查詢之前計算過得值即可。這樣就防止了進行多次同樣的計算。

如下所示清單2的源代碼，對清單1的源代碼進行了記憶化優(yōu)化。

清單2

CulcFibonacciMemo.py

          
            import sys

# メモ化テーブル(辭書形式)
fibonacci_list = {}

# フィボナッチ數(shù)の計算(メモ化あり)
def culc_fibonacci_memo(n):
    global fibonacci_list
    if n == 1:
        return 1
    elif n == 0:
        return 0
    if not n in fibonacci_list:
        fibonacci_list[n] = culc_fibonacci_memo(n-1) + culc_fibonacci_memo(n-2)
    return fibonacci_list[n]

def main():
    # 1～10番目フィボナッチ數(shù)列を表示
    #     ?　0, 1, 1, 2, 3, 5, 8, 13, 21, 34
    for n in range(10):
        fibonacci_n = culc_fibonacci_memo(n)
        print(fibonacci_n, end='')
        if not  n == 9:
            print(', ', end='')

if __name__ == '__main__':
    main()
    sys.exit(0)

          
        

記憶化的最大優(yōu)點是通過減少計算量，從而減少了計算的時間。清單2所示代碼會將第一次計算的斐波那契數(shù)存儲起來，之后通過再次利用之前的計算結(jié)果來減少計算量。實際上，筆者在自己的PC上計算f(40)的斐波那契數(shù)的時候，清單1沒有進行記憶化優(yōu)化的程序用了101.9秒，而清單2進行了記憶化優(yōu)化的程序只用了0.2秒，兩者的計算時間相比，后者的計算時間大幅度縮減。由于動態(tài)規(guī)劃是以遞歸的方式計算子問題，因此這種存儲優(yōu)化非常重要。
對于動態(tài)規(guī)劃的概要說明到此為止，接下來的章節(jié)我們將嘗試用Dijkstra算法(動態(tài)規(guī)劃的一種)來解決最短路徑的問題。

下一節(jié)將介紹用Dijkstra的方法解決最短路徑問題(Python實現(xiàn))。