文章目錄

• • 1. 理論總結(jié)
  • • 1.1 “一個模型”
    • 1.2 “三個特征”
    • • 1.2.1 最優(yōu)子結(jié)構(gòu)
      • 1.2.2 無后效性
      • 1.2.3 重復(fù)子問題
  • 2. 實例剖析
  • • 2.1 問題描述
    • 2.2 兩種DP解題思路
    • • 2.2.1 狀態(tài)轉(zhuǎn)移表
      • 2.2.2 狀態(tài)轉(zhuǎn)移方程
  • 3. 四種算法思想比較

1. 理論總結(jié)

動態(tài)規(guī)劃理論總結(jié)為“一個模型、三個特征”。

1.1 “一個模型”

• 它指的是動態(tài)規(guī)劃適合解決的問題的模型。我把這個模型定義為“多階段決策最優(yōu)解模型"。
• 一般是用動態(tài)規(guī)劃來解決最優(yōu)問題。
• 解決問題的過程，需要經(jīng)歷多個決策階段。每個決策階段對應(yīng)著一組狀態(tài)。
• 然后我們尋找一組決策序列，經(jīng)過這組決策序列，能夠產(chǎn)生最終期望求解的最優(yōu)值。

1.2 “三個特征”

1.2.1 最優(yōu)子結(jié)構(gòu)

• 問題的最優(yōu)解包含子問題的最優(yōu)解。
• 反過來說就是，可以通過子問題的最優(yōu)解，推導(dǎo)出問題的最優(yōu)解。后面階段的狀態(tài)可以通過前面階段的狀態(tài)推導(dǎo)出來。

1.2.2 無后效性

• 在推導(dǎo)后面階段的狀態(tài)時，我們只關(guān)心前面階段的狀態(tài)值，不關(guān)心這個狀態(tài)是怎么一步一步推導(dǎo)出來的。
• 某階段狀態(tài)一旦確定，就不受之后階段的決策影響。只要滿足前面提到的動態(tài)規(guī)劃問題模型，其實基本上都會滿足無后效性。

1.2.3 重復(fù)子問題

• 不同的決策序列，到達某個相同的階段時，可能會產(chǎn)生重復(fù)的狀態(tài)。

2. 實例剖析

2.1 問題描述

一個n乘以n的矩陣w[n][n]。存儲的都是正整數(shù)。棋子起始位置在左上角，終止位置在右下角。每次只能向右或者向下移動一位。把每條路徑經(jīng)過的數(shù)字加起來看作路徑的長度。最短路徑長度是多少？

• 是否符合“一個模型”

從（0，0）走到（n-1，n-1），總共要走 2n-1 步，對應(yīng)著 2n-1 個階段。

每個階段都有向右或向下走兩種決策，并且每個階段都會對應(yīng)一個狀態(tài)集合。

我們把狀態(tài)定義為 min_dist（i，j），其中 i 表示行，j 表示列。min_dist 表達式的值表示從（0，0）到達（i，j）的最短路徑長度。

所以，這個問題是一個多階段決策最優(yōu)解問題，符合動態(tài)規(guī)劃的模型。

• 是否符合“三個特征”

我們可以用回溯算法來解決這個問題。自己寫一下代碼，畫一下遞歸樹，就會發(fā)現(xiàn)，遞歸樹中有重復(fù)的節(jié)點。重復(fù)的節(jié)點表示，從左上角到節(jié)點對應(yīng)的位置，有多種路線，這也能說明這個問題中存在重復(fù)子問題。

下面給出回溯解法

/*** @description: dp課第二節(jié)，案例回溯法求解* @author: michael ming* @date: 2019/7/19 19:55* @modified by: */ #include <iostream> #define N 4//地圖大小 #define k (2*N-1)//需要走的步數(shù) using namespace std; int selectWay[k], shortestWay[k]; void step(int (*map)[N], int s, int &mins, int r, int c, int idx) {selectWay[idx++] = map[r][c];//記錄選擇的路if(r == N-1 && c == N-1){if(s < mins){mins = s;//更新最小的總路程for(int i = 0; i < k; ++i)//把最終的路線記錄下來shortestWay[i] = selectWay[i];}return;}if(r == N || c == N)return;//走出地圖邊界了step(map,s+map[r+1][c],mins,r+1,c,idx);//往下走step(map,s+map[r][c+1],mins,r,c+1,idx);//往右走 } int main() {int s = 0, mins = 65535;int map[N][N] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};step(map,s+map[0][0],mins,0,0,0);cout << "最短路徑是：" << mins << endl;cout << "走過的點的距離分別是：" << endl;for(int i = 0; i < k; ++i)cout << shortestWay[i] << " ";return 0; }

走到（i，j）這個位置，只能通過（i-1，j），（i，j-1）這兩個位置移動過來，也就是，想要計算（i，j）位置對應(yīng)的狀態(tài)，只需關(guān)心（i-1，j），（i，j-1）兩個位置對應(yīng)的狀態(tài)，并不關(guān)心棋子是通過什么樣的路線到達這兩個位置。而且，我們僅僅允許往下和往右移動，不允許后退，所以，前面階段的狀態(tài)確定后，不會被后面的決策所改變，所以，這個問題符合“無后效性”這一特征。

把從起始位置（0，0）到（i，j）的最小路徑，記作函數(shù)min_dist（i，j）。因為只能往右或往下移動，所以只有可能從（i，j-1）或（i-1，j）兩個位置到達（i，j）。到達（i，j）的最短路徑肯定包含到達這兩個位置的最短路徑之一。換句話說就是，min_dist（i，j）可以通過min_dist（i，j-1）和min_dist（i-1，j）兩個狀態(tài)推導(dǎo)出來。這就說明，這個問題符合“最優(yōu)子結(jié)構(gòu)”。

min_dist(i, j) = w[i][j] + min{min_dist(i, j-1), min_dist(i-1, j)}

2.2 兩種DP解題思路

2.2.1 狀態(tài)轉(zhuǎn)移表

• 一般能用動態(tài)規(guī)劃的，都可以使用回溯暴力搜索。所以，可以先用簡單的回溯算法解決，然后定義狀態(tài)，對應(yīng)畫出遞歸樹。

• 從遞歸樹中，我們很容易可以看出來，是否存在重復(fù)子問題，以及重復(fù)子問題是如何產(chǎn)生的。以此來尋找規(guī)律，看是否能用動態(tài)規(guī)劃解決。

• 找到重復(fù)子問題之后，有兩種處理思路，第一種是回溯加“備忘錄”的方法，來避免重復(fù)子問題。從效率上來講，這跟動態(tài)規(guī)劃的解決思路沒有差別。

• 第二種是使用動態(tài)規(guī)劃，狀態(tài)轉(zhuǎn)移表法。

• 先畫出一個狀態(tài)表，一般是二維的，可以把它想象成二維數(shù)組。其中，每個狀態(tài)包含三個變量，行、列、數(shù)組值。

• 根據(jù)決策的先后，從前往后，根據(jù)遞推關(guān)系，分階段填充狀態(tài)表中的每個狀態(tài)。最后，將這個遞推填表的過程，翻譯成代碼，就是動態(tài)規(guī)劃代碼。

• 盡管大部分狀態(tài)表都是二維的，如果問題的狀態(tài)比較復(fù)雜，需要很多變量來表示，那對應(yīng)的狀態(tài)表就是高維的，這個時候，不適合用狀態(tài)轉(zhuǎn)移表法來解決了。一方面高維狀態(tài)轉(zhuǎn)移表不好畫圖表示，另一方面人腦不擅長思考高維的東西。

根據(jù)回溯代碼畫出遞歸樹，遞歸樹中，一個狀態(tài)（節(jié)點）包含三個變量（i，j，dist），其中i，j表示行和列，dist表示從起點到達點（i，j）的路徑長度。圖中看出，盡管（i，j，dist）不存在重復(fù)，但是（i，j）重復(fù)的有很多。對（i，j）重復(fù)的節(jié)點，我們只選擇 dist最小的節(jié)點，繼續(xù)遞歸求解，其他節(jié)點舍棄。

畫出二維狀態(tài)表，表中行、列表示棋子位置，表中數(shù)值表示從起點到這個位置的最短路徑。我們按照決策過程，將狀態(tài)表填好。為了方便，我們按行來進行依次填充。

dp狀態(tài)表法代碼如下：

/*** @description: * @author: michael ming* @date: 2019/7/19 23:30* @modified by: */ #include <iostream> #include <stack> #define N 4//地圖大小 using namespace std; void printShortestWay(int (*map)[N], int (*states)[N]) {stack<int> path;path.push(map[N-1][N-1]);//終點for(int i = N-1,j = N-1; j != 0 && i != 0; ){if(states[i][j]-map[i][j] == states[i-1][j])path.push(map[--i][j]);//從上面過來的elsepath.push(map[i][--j]);//從左邊過來的}path.push(map[0][0]);//起點cout << "走過的點的距離分別是：" << endl;while(!path.empty())//棧逆序彈出路徑{cout << path.top() << " ";path.pop();} } void step_dp(int (*map)[N]) {int (*states)[N] = new int [N][N];int i, j, sum = 0;for(j = 0; j < N; ++j)//初始化第一行狀態(tài){sum += map[0][j];states[0][j] = sum;}sum = 0;for(i = 0; i < N; ++i)//初始化第一列狀態(tài){sum += map[i][0];states[i][0] = sum;}for(i = 1; i < N; ++i)//填寫狀態(tài)表for(j = 1; j < N; ++j)states[i][j] = map[i][j]+min(states[i][j-1],states[i-1][j]);cout << "最短路徑是：" << states[N-1][N-1] << endl;printShortestWay(map,states);delete [] states;return; } int main() {int map[N][N] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};step_dp(map);return 0; }

2.2.2 狀態(tài)轉(zhuǎn)移方程

• 狀態(tài)轉(zhuǎn)移方程法有點類似遞歸。根據(jù)最優(yōu)子結(jié)構(gòu)，寫出遞歸公式，也就是狀態(tài)轉(zhuǎn)移方程。

• 有兩種代碼實現(xiàn)方法，一種是遞歸加“備忘錄”，另一種是迭代遞推。

  min_dist(i, j) = w[i][j] + min{min_dist(i, j-1), min_dist(i-1, j)}

• 狀態(tài)轉(zhuǎn)移方程是解DP的關(guān)鍵。如果能寫出狀態(tài)轉(zhuǎn)移方程，那DP問題基本上就解決一大半了。但是很多DP問題的狀態(tài)本身就不好定義，狀態(tài)轉(zhuǎn)移方程也就更不好想到。

下面用遞歸加“備忘錄”的方式，將狀態(tài)轉(zhuǎn)移方程翻譯成代碼。對于另一種實現(xiàn)方式，跟狀態(tài)轉(zhuǎn)移表法的代碼實現(xiàn)是一樣的，只是思路不同。

/*** @description: dp 狀態(tài)方程 遞歸* @author: michael ming* @date: 2019/7/20 9:35* @modified by: */ #include <iostream> #include <stack> #define N 4//地圖大小 using namespace std; int states [N][N]; void printShortestWay(int (*map)[N]) {stack<int> path;path.push(map[N-1][N-1]);//終點for(int i = N-1,j = N-1; j != 0 && i != 0; ){if(states[i][j]-map[i][j] == states[i-1][j])path.push(map[--i][j]);//從上面過來的elsepath.push(map[i][--j]);//從左邊過來的}path.push(map[0][0]);//起點cout << "走過的點的距離分別是：" << endl;while(!path.empty())//棧逆序彈出路徑{cout << path.top() << " ";path.pop();} } int minDist(int (*map)[N], int i, int j)//從起點到i,j點的最小距離 {if(i == 0 && j == 0)//從起點到起點，返回該位置數(shù)值return map[0][0];if(states[i][j] > 0)//遇到算過的，直接返回結(jié)果return states[i][j];int minLeft, minUp;minLeft = minUp = 65535;if(j-1 >= 0)minLeft = minDist(map,i,j-1);//點左邊的點的最小距離if(i-1 >= 0)minUp = minDist(map,i-1,j);//點上面的點的最小距離int currMinDist = map[i][j]+min(minLeft,minUp);states[i][j] = currMinDist;//備忘錄更新return currMinDist; } int main() {int map[N][N] = {1,3,5,9,2,1,3,4,5,2,6,7,6,8,4,3};cout << "最短路徑是：" << minDist(map,N-1,N-1) << endl;printShortestWay(map);return 0; }

強調(diào)一點，不是每個問題都同時適合這兩種解題思路。有的問題可能用狀態(tài)表更清晰，而有的問題可能用狀態(tài)方程思路更清晰。

3. 四種算法思想比較

到現(xiàn)在為止，已經(jīng)學(xué)習(xí)了四種算法思想，貪心、分治、回溯、動態(tài)規(guī)劃。

• 貪心、回溯、動態(tài)規(guī)劃，都可以抽象成多階段決策最優(yōu)解模型
• 而分治解決的問題盡管大部分也是最優(yōu)解問題，但是，大部分都不能抽象成多階段決策模型

算法算法特點

回溯	窮舉所有的情況，然后對比得到最優(yōu)解。時間復(fù)雜度非常高，指數(shù)級，只能用來解決小規(guī)模問題。大規(guī)模問題，執(zhí)行效率很低
動態(tài)規(guī)劃	需要滿足三個特征，最優(yōu)子結(jié)構(gòu)、無后效性和重復(fù)子問題，動態(tài)規(guī)劃之所以高效，是因為回溯算法實現(xiàn)中存在大量的重復(fù)子問題
分治	要求分割成的子問題，不能有重復(fù)子問題，與動態(tài)規(guī)劃正好相反
貪心	高效，代碼簡潔。可以解決的問題也有限。需要滿足三個條件，最優(yōu)子結(jié)構(gòu)、無后效性和貪心選擇性。“貪心選擇性”的意思是，通過局部最優(yōu)的選擇，能產(chǎn)生全局的最優(yōu)選擇。每一個階段，都選擇當(dāng)前看起來最優(yōu)的決策，所有階段的決策完成之后，最終由這些局部最優(yōu)解構(gòu)成全局最優(yōu)解

總結(jié)

以上是生活随笔為你收集整理的动态规划理论学习的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。