原作者：金子冴
校閱：內野良一
翻譯：葉子
原文鏈接

目錄

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

什么是動態規劃(Dynamic Programming)

動態規劃概要

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

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

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

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

什么是分而治之(分治)

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

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

什么是記憶化

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

清單1

CulcFibonacci.py

          
            import sys

# フィボナッチ數の計算
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番目フィボナッチ數列を表示
    #     ?　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次冪)(α:實數)，所以當n變大的時候，相關的計算量會呈指數級增長。
下圖表示的是斐波那契數列的計算過程。從下圖我們可以看出，除了f(10)之外的所有計算都不止一次。

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

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

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

清單2

CulcFibonacciMemo.py

          
            import sys

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

# フィボナッチ數の計算(メモ化あり)
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番目フィボナッチ數列を表示
    #     ?　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)

          
        

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

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