算法學習之動態(tài)規(guī)劃策略入門
一、概念
動態(tài)規(guī)劃策略，一種分治策略。和貪婪策略一樣，通常是用來解決***解問題。分治故名就是將問題分解為幾個子問題來解決，動態(tài)規(guī)劃的特點就是分解的子問題中（子問題又可以分解成子問題）每次選擇選擇***解。
動態(tài)規(guī)劃主要的特點是在做決定前她知道所有子問題的信息。
動態(tài)規(guī)劃的兩個重要要素是：1）***子結構。2）重疊子問題。
1）***子結構，這是采取動態(tài)規(guī)劃策略解***化問題后要做的***步。所謂***化子結構是說若問題的一個***解中包含了子問題的***解，則該問題具有***子結構。這個是我們采取動態(tài)規(guī)劃的一個充分條件（當然這個條件也滿足貪婪策略），問題出現(xiàn)這個條件就可以考慮采取動態(tài)規(guī)劃。
一般要考慮的因素是：
1.1）***解里需要解決的子問題數(shù)量有多少？
1.2）在判斷使用那些子問題時需要進行多少選擇？
2）重疊子問題，是指在遞歸解決方案中，若產(chǎn)生了大量的相同子問題，那么相同的子問題就會被重復計算很多次，這樣算法的效率損耗就很大。這個要素是動態(tài)規(guī)劃的優(yōu)勢所在，可以說動態(tài)規(guī)劃就是為解決這種問題而生的（實際上，有記憶的遞歸算法也可以做到類似的算法改進）.
二、解題策略
一般解題的思路為：
1）證明問題的解決方案中包括一個選擇，選擇之后將留下一個或多個子問題
2）設計子問題的遞歸描述方式（一般會出現(xiàn)遞歸公式又稱轉(zhuǎn)移方程，這個是解題和算法的關鍵）
3）證明對原問題的***解里包括對所有子問題的***解
4）證明子問題之間有重疊
可以看出1、3、4是為了使得子問題的構建能符合動態(tài)規(guī)劃策略，他們的目的都是為了他構建一個合理恰當?shù)淖訂栴}而服務的。但是不同問題構建子問題的思路不盡相同。除了要考慮1.1、1.2的問題外，通常有個比較有效的經(jīng)驗，就是盡量使得這個子問題簡單，然后在需要的時候去擴充她.
三、例子
用比較經(jīng)典的最長公共子序列問題(LCS)。
問題定義如下：兩個子序列S1[1..m]和S2[1..n],需要找出他們的一個最長公共子序列（其中子序列不一定必須是連續(xù)的）。
解法一：暴力窮舉法
思路：
1）檢查S1[1..m]中的每一個子序列.
2）看看其是否也在S2[1..n]里的子序列.
3）在每一步記錄當前找到的子序列里面最長的子序列.
顯然效率非常低下：每個子序列的檢查要時間O(n),而共有2^m子序列需要檢查,so時間復雜度問O(n*2^m).
那么如何改進呢,由于LCS中存在***子結構,即所求的最長公共子序列包含子最長公共子序列,所以我們可以嘗試使用動態(tài)規(guī)劃來解決問題.
解法二：動態(tài)規(guī)劃
按照解題策略,我們要先構造一個合適的子問題,根據(jù)第二點提到的,我們構建一個盡量簡單的子問題,然后在去擴展.在LCS中,便有:
1）先尋找最長公共子序列的長度.
2）擴展尋找長度的算法來獲得最長公共子序列.
由上可以得到一個遞歸表達式:
( c[i,j]表示長度為i的S1和長度為j的S2的最長公共子序列. xi表示表示S串中的第i個字符. )
上面遞歸式的推倒通過畫圖可以很容易得出.
代碼:
- charb[50][50]; //記錄路徑圖,方便輸出LCS
- intc[50][50]; //c[i][j]存長度為i的x串和長度為j的y串的LCS的長度
- charx[50], y[50]; //x,y存兩個要比對的字符串
- voidLCS()
- {
- intm = strlen(x+1);
- intn = strlen(y+1);
- //初始化
- for(inti=1;i<=m; ++i)
- c[i][0] = 0;
- for(intj=1;j<=n; ++j)
- c[0][j] = 0;
- for(inti=1;i<=m; ++i)
- for(intj=1;j<=n; ++j)
- {
- if(x[i] == y[j])
- {
- c[i][j] = c[i-1][j-1] + 1;
- b[i][j] = '\';
- }
- elseif(c[i-1][j] >= c[i][j-1])
- {
- c[i][j] = c[i-1][j];
- b[i][j] = '|';
- }
- else
- {
- c[i][j] = c[i][j-1];
- b[i][j] = '-';
- }
- }
- }
- //輸出LCS
- voidprintLCS(inti, intj)
- {
- if(i == 0|| j == 0)
- return;
- if(b[i][j] == '\')
- {
- printLCS(i-1, j-1);
- print(x[i] +"");
- }
- elseif(b[i][j] == '|')
- printLCS(i-1, j);
- else
- printLCS(i, j-1);
- }
四、小結
LCS的變種還有很多:最長遞增/遞減子序列、編輯距離等.
動態(tài)規(guī)劃的關鍵還是以上提到的兩個重要的元素:***子結構和重復子問題.***化問題中若出現(xiàn)了相關的信息或可以轉(zhuǎn)換到此類問題的則可嘗試使用動態(tài)規(guī)劃.但是子問題的構建需要花費一定的思考即構建遞歸方程式.
但是,動態(tài)規(guī)劃的雖然能做出最"明智的"決定,但她需要對一切"了如指掌"后才能做到,這顯然趨于"保守",所以并非所以問題都適用.這個時候其它***化算法可以被考慮.
原文鏈接：http://www.cnblogs.com/Quains/archive/2011/11/09/2241879.html
【編輯推薦】
