動態規劃

維基百科,自由的百科全書
跳轉到: 導覽搜尋

動態規劃英語Dynamic programming,DP)[1]是一種在數學計算機科學經濟學中使用的,通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。 動態規劃常常適用於有重疊子問題[2]最優子結構性質的問題,動態規劃方法所耗時間往往遠少於樸素解法。

動態規劃背後的基本思想非常簡單。大致上,若要解一個給定問題,我們需要解其不同部分(即子問題),再合併子問題的解以得出原問題的解。 通常許多子問題非常相似,為此動態規劃法試圖僅僅解決每個子問題一次,從而減少計算量: 一旦某個給定子問題的解已經算出,則將其記憶化存儲,以便下次需要同一個子問題解之時直接查表。 這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。

概述[編輯]

動態規劃在查找有很多重疊子問題的情況的最優解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題,它們的結果都逐漸被計算並被保存,從簡單的問題直到整個問題都被解決。因此,動態規劃保存遞歸時的結果,因而不會在解決同樣的問題時花費時間。

動態規劃只能應用於有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解(對有些問題這個要求並不能完全滿足,故有時需要引入一定的近似)。簡單地說,問題能夠分解成子問題來解決。

步驟[編輯]

  1. 最優子結構性質。如果問題的最優解所包含的子問題的解也是最優的,我們就稱該問題具有最優子結構性質(即滿足最優化原理)。最優子結構性質為動態規划算法解決問題提供了重要線索。
  2. 子問題重疊性質。子問題重疊性質是指在用遞歸演算法自頂向下對問題進行求解時,每次產生的子問題並不總是新問題,有些子問題會被重複計算多次。動態規划算法正是利用了這種子問題的重疊性質,對每一個子問題只計算一次,然後將其計算結果保存在一個表格中,當再次需要計算已經計算過的子問題時,只是在表格中簡單地查看一下結果,從而獲得較高的效率。

實例[編輯]

斐波那契數列(Fibonacci polynomial)[編輯]

計算斐波那契數列(Fibonacci polynomial)的一個最基礎的演算法是,直接按照定義計算:

   function fib(n)
       if n = 0 or n = 1
           return 1
       return fib(n − 1) + fib(n − 2)

當n=5時,fib(5)的計算過程如下:

  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))

由上面可以看出,這種演算法對於相似的子問題進行了重複的計算,因此不是一種高效的演算法。實際上,該演算法的運算時間是指數級增長的。 改進的方法是,我們可以通過保存已經算出的子問題的解來避免重複計算:

array map [0...n] = { 0 => 0, 1 => 1 }
fib( n )
    if ( map m does not contain key n)
        m[n] := fib(n − 1) + fib(n − 2)
    return m[n]

將前n個已經算出的數保存在數組map中,這樣在後面的計算中可以直接應用前面的結果,從而避免了重複計算。演算法的運算時間變為O(n)

背包問題[編輯]

背包問題作為NP完全問題,暫時不存在多項式時間演算法。動態規劃屬於背包問題求解最優解的可行方法之一。此外,求解背包問題最優解還有搜索法等,近似解還有貪心法等,分數背包問題有最優貪心解等。 背包問題具有最優子結構和重疊子問題。動態規劃一般用於求解背包問題中的整數背包問題(即每種物品所選的個數必須是整數)。 解整數背包問題: 設有n件物品,每件價值記為Pi,每件體積記為Vi,用一個最大容積為Vmax的背包,求裝入物品的最大價值。 用一個數組f[i,j]表示取i件商品填充一個容積為j的背包的最大價值,顯然問題的解就是f[n,Vmax].

f[i,j]=

      f[i-1,j] {j<Vi}
      max{f[i-1,j],f[i,j-Vi]+Pi} {j>=Vi}
      0 {i=0 OR j=0}

對於特例01背包問題(即每件物品最多放1件,否則不放入)的問題,狀態轉移方程:

f[i,j]=

      f[i-1,j] {j<Vi}
      max{f[i-1,j],f[i-1,j-Vi]+Pi} {j>=Vi}
      0 {i=0 OR j=0}

參考Pascal代碼

for i:=1 to n do
  for j:=totv downto v[i] do
    f[j]:=max(f[j],f[j-v[i]]+p[i]);
writeln(f[totv]);

使用動態規劃的演算法[編輯]

參考[編輯]

  1. ^ 動態規劃:從新手到專家
  2. ^ S. Dasgupta, C.H. Papadimitriou, and U.V. Vazirani, 'Algorithms', p 173, available at http://www.cs.berkeley.edu/~vazirani/algorithms.html

(參考:動態規劃:從新手到專家的嚴謹性需進一步查證)

外部連結[編輯]