動態規劃
来自维基百科,自由的百科全书
来自维基百科,自由的百科全书
動態規劃(英語:Dynamic programming,簡稱DP)是一種在數學、管理科學、計算機科學、經濟學和生物信息學中使用的,通過把原問題分解為相對簡單的子問題的方式求解複雜問題的方法。
![]() |
動態規劃常常適用於有重疊子問題[1]和最優子結構性質的問題,動態規劃方法所耗時間往往遠少於樸素解法。
動態規劃背後的基本思想非常簡單。大致上,若要解一個給定問題,我們需要解其不同部分(即子問題),再根據子問題的解以得出原問題的解。
通常許多子問題非常相似,為此動態規劃法試圖僅僅解決每個子問題一次,從而減少計算量:一旦某個給定子問題的解已經算出,則將其記憶化存儲,以便下次需要同一個子問題解之時直接查表。這種做法在重複子問題的數目關於輸入的規模呈指數增長時特別有用。
動態規劃在查找有很多重疊子問題的情況的最優解時有效。它將問題重新組合成子問題。為了避免多次解決這些子問題,它們的結果都逐漸被計算並被保存,從簡單的問題直到整個問題都被解決。因此,動態規劃保存遞歸時的結果,因而不會在解決同樣的問題時花費不必要的時間。
動態規劃只能應用於有最優子結構的問題。最優子結構的意思是局部最優解能決定全局最優解(對有些問題這個要求並不能完全滿足,故有時需要引入一定的近似)。簡單地說,問題能夠分解成子問題來解決。
包括但不限於切割鋼條問題、Floyd最短路問題、最大不下降子序列、矩陣鏈乘、凸多邊形三角剖分、背包問題、最長公共子序列、最優二分搜索樹等。
背包問題作為NP完全問題,暫時不存在多項式時間算法。動態規劃屬於背包問題求解最優解的可行方法之一。此外,求解背包問題最優解還有搜索法等,近似解還有貪心法等,分數背包問題有最優貪婪解等。 背包問題具有最優子結構和重疊子問題。動態規劃一般用於求解背包問題中的整數背包問題(即每種物品所選的個數必須是整數)。 解整數背包問題: 設有件物品,每件價值記為,每件重量記為,用一個最大重量為的背包,求裝入物品的最大價值。 在總重量不超過W的前提下,我們希望總價格最高。對於Y ≤ W,我們將在總重量不超過Y的前提下,總價格所能達到的最高值定義為A(Y)。A(W)即為問題的答案。
顯然,A(Y)滿足:
其中,pj為第j種物品的價格。
對於特例0 1背包問題(即每件物品最多放1件,否則不放入)的問題,我們將在總重量不超過Y的前提下,前j種物品的總價格所能達到的最高值定義為A(j, Y)。
A(j, Y)的遞推關係為:
參考Pascal代碼
for i:=1 to n do
for v:=totv downto v[i] do
f[v]:=max(f[v],f[v-v[i]]+p[i]);
writeln(f[totv]);
參考C++代碼(不含include和數組聲明)
#define max(x,y) (x)>(y)?(x):(y) //max宏函数,也可以自己寫或者使用algorithm
for(int i=1;i<=n;i++)
for (v=totv;v>=v[i];v--)
f[v]=max(f[v],f[v-v[i]]+p[i]);
printf("%d",f[totv]); //或std::cout<<f[totv];
術語「動態規劃」最初是在1940年代由理查德·貝爾曼用來描述解決問題的過程,在這個過程中,人們需要一個接一個地找到最佳決策。到1953年,他將其精煉成為現代的含義,特別是指將較小的決策問題嵌套在較大的決策中,[2] 並且該領域隨後被電氣電子工程師學會認可為系統分析和工程學主題。貝爾曼的貢獻以貝爾曼方程的名義被銘記,它是動態規劃的核心結果,它以遞歸形式重申了優化問題。
貝爾曼選擇了「動態」這個詞來捕捉問題的隨時間變化的方面,也因為它聽起來令人印象深刻。[3] 「規劃」一詞指的是使用該方法來找到最佳的「程序」,在於軍事訓練或後勤計劃的意義。這種用法與短語「線性規劃」和「數學規劃」中的用法相同。[4]
術語起源的上述解釋是不足的。正如羅素和諾維格在他們的書中提到上述故事時所寫的那樣:「這不可能完全正確,因為他的第一篇使用這個詞(貝爾曼,1952)的論文出現在威爾遜於 1953 年成為國防部長之前。」[5]此外,還有Harold J. Kushner (頁面存檔備份,存於網際網路檔案館)在演講中的評論,他記得貝爾曼。他在談到貝爾曼時引用庫什納的話:「另一方面,當我問他同樣的問題時,他回答說他試圖通過加上動態來超越喬治·伯納德·丹齊格的線性規劃。也許這兩種動機都是正確的。」