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

目錄

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

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

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

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

什么是多項(xiàng)式時(shí)間，什么是多項(xiàng)式時(shí)間算法

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

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

什么是分而治之(分治)

分治指的是將目標(biāo)問題分割成復(fù)數(shù)個(gè)子問題的手法。讓我們?cè)囍鴮偛盘岬降淖疃搪窂絾栴}進(jìn)行子問題分解。對(duì)于剛才提到的例子，首先不要去考慮從START開始能夠到達(dá)END的所有路線，而應(yīng)該只考慮在某個(gè)時(shí)間點(diǎn)能夠推進(jìn)的路線。所以對(duì)于最開始的路線，只需要考慮START到a，b，c，d這四條。考慮到我們要解決的是最短路徑的問題，這里我們選擇從START開始花費(fèi)最小的START->b路線開始。接著，我們只需考慮從b點(diǎn)出發(fā)能夠推進(jìn)的路線，這里我們也是選擇花費(fèi)最少的路線，b->g路線。

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

什么是記憶化

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

清單1

CulcFibonacci.py

          
            import sys

# フィボナッチ數(shù)の計(jì)算
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所示代碼，在計(jì)算n=10的時(shí)候，必須去計(jì)算n=9～1，因此計(jì)算時(shí)間是O(αn:α的n次冪)(α:實(shí)數(shù))，所以當(dāng)n變大的時(shí)候，相關(guān)的計(jì)算量會(huì)呈指數(shù)級(jí)增長(zhǎng)。
下圖表示的是斐波那契數(shù)列的計(jì)算過程。從下圖我們可以看出，除了f(10)之外的所有計(jì)算都不止一次。

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

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

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

清單2

CulcFibonacciMemo.py

          
            import sys

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

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

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