746
五大常用算法 之 動態規劃法
一、基本概念
動態規劃過程是：每次決策依賴於當前狀態，又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的，所以，這種多階段最優化決策解決問題的過程就稱為動態規劃。
動態規劃是運籌學中用於求解決策過程中的最優化數學方法。當然，我們在這裏關注的是作為一種算法設計技術，作為一種使用多階段決策過程最優的通用方法。它是應用數學中用於解決某類最優化問題的重要工具。
如果問題是由交疊的子問題所構成，我們就可以用動態規劃技術來解決它，一般來說，這樣的子問題出現在對給定問題求解的遞推關係中，這個遞推關係包含了相同問題的更小子問題的解。動態規劃法建議，與其對交疊子問題一次又一次的求解，不如把每個較小子問題隻求解一次並把結果記錄在表中（動態規劃也是空間換時間的），這樣就可以從表中得到原始問題的解。
動態規劃常常用於解決最優化問題，這些問題多表現為多階段決策。
關於多階段決策：
在實際中，人們常常遇到這樣一類決策問題：即由於過程的特殊性，可以將決策的全過程依據時間或空間劃分若幹個聯係的階段。而在各階段中，人們都需要作出方案的選擇，我們稱之為決策，並且當一個階段的決策之後，常常影響到下一個階段的決策，從而影響整個過程的活動。這樣，各個階段所確定的決策就構成一個決策序列，常稱之為策略。由於各個階段可供選擇的決策往往不止一個，因而就可能有許多決策以供選擇，這些 可供選擇的策略構成一個集合，我們稱之為允許策略集合（簡稱策略集合）。每個策略都相應地確定一種活動的效果，我們假定這個效果可以用數量來衡量。由於不同的策略常常導致不同的效果，因此，如何在允許策略集合中選擇一個策略，使其在預定的標準下達到最好的效果，常常是人們所關心的問題，我們稱這樣的策略為最優策略，這類問題就稱為多階段決策問題。
多階段決策問題舉例：機器負荷分配問題
某種機器可以在高低兩種不同的負荷下進行生產，在高負荷下生產時，產品的年產量g和投入生產的機器數量x的關係為g=g(x)，這時的年完好率為a，即如果年初完好機器數為x，到年終時完好的機器數為a*x(0<a<1)；在低負荷下生產時，產品的年產量h和投入生產的機器數量y的關係為h=h(y)，相應的完好率為b(0<b<0)，且a<b。
假定開始生產時完好的機器熟練度為s1。要製定一個五年計劃，確定每年投入高、低兩種負荷生產的完好機器數量，使5年內產品的總產量達到最大。
這是一個多階段決策問題。顯然可以將全過程劃分為5個階段（一年一個階段），每個階段開始時要確定投入高、低兩種負荷下生產的完好機器數，而且上一個階段的決策必然影響到下一個階段的生產狀態。決策的目標是使產品的總產量達到最大。這個問題經常使用數學方法建模，結合線性規劃等知識來進行解決。
二、基本思想與策略
基本思想與分治法類似，也是將待求解的問題分解為若幹個子問題（階段），按順序求解子階段，前一子問題的解，為後一子問題的求解提供了有用的信息。在求解任一子問題時，列出各種可能的局部解，通過決策保留那些有可能達到最優的局部解，丟棄其他局部解。依次解決各子問題，最後一個子問題就是初始問題的解。
由於動態規劃解決的問題多數有重疊子問題這個特點，為減少重複計算，對每一個子問題隻解一次，將其不同階段的不同狀態保存在一個二維數組中。
與分治法最大的差別是：適合於用動態規劃法求解的問題，經分解後得到的子問題往往不是互相獨立的（即下一個子階段的求解是建立在上一個子階段的解的基礎上，進行進一步的求解）。
三、適用的情況
能采用動態規劃求解的問題的一般要具有3個性質：
（1）、最優化原理：如果問題的最優解所包含的子問題的解也是最優的，就稱該問題具有最優子結構，即滿足最優化原理；
（2）、無後效性：即某階段狀態一旦確定，就不受這個狀態以後決策的影響。也就是說，某狀態以後的過程不會影響以前的狀態，隻與當前狀態有關；
（3）、有重疊子問題：即子問題之間是不獨立的，一個子問題在下一階段決策中可能被多次使用到（該性質並不是動態規劃適用的必要條件，但是如果沒有這條性質，動態規劃算法同其他算法相比就不具備優勢）。
四、求解的基本步驟
動態規劃所處理的問題是一個多階段決策問題，一般由初始狀態開始，通過對中間階段決策的選擇，達到結束狀態。這些決策形成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常是求最優的活動路線)。動態規劃的設計都有著一定的模式，一般要經曆以下幾個步驟。
初始狀態→│決策1│→│決策2│→…→│決策n│→結束狀態
（1）劃分階段：按照問題的時間或空間特征，把問題分為若幹個階段。在劃分階段時，注意劃分後的階段一定要是有序的或者是可排序的，否則問題就無法求解。
（2）確定狀態和狀態變量：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選擇要滿足無後效性。
（3）確定決策並寫出狀態轉移方程：因為決策和狀態轉移有著天然的聯係，狀態轉移就是根據上一階段的狀態和決策來導出本階段的狀態。所以如果確定了決策，狀態轉移方程也就可寫出。但事實上常常是反過來做，根據相鄰兩個階段的狀態之間的關係來確定決策方法和狀態轉移方程。
（4）尋找邊界條件：給出的狀態轉移方程是一個遞推式，需要一個遞推的終止條件或邊界條件。
一般，隻要解決問題的階段、狀態和狀態轉移決策確定了，就可以寫出狀態轉移方程（包括邊界條件）。
實際應用中可以按以下幾個簡化的步驟進行設計：
（1）分析最優解的性質，並刻畫其結構特征。
（2）遞歸的定義最優解。
（3）以自底向上或自頂向下的記憶化方式（備忘錄法）計算出最優值。
（4）根據計算最優值時得到的信息，構造問題的最優解。
五、算法實現的說明
動態規劃的主要難點在於理論上的設計，也就是上麵4個步驟的確定，一旦設計完成，實現部分就會非常簡單。
使用動態規劃求解問題，最重要的就是確定動態規劃三要素：問題的階段、每個階段的狀態、從前一個階段轉化到後一個階段之間的遞推關係。
遞推關係必須是從次小的問題開始到較大的問題之間的轉化，從這個角度來說，動態規劃往往可以用遞歸程序來實現，不過因為遞推可以充分利用前麵保存的子問題的解來減少重複計算，所以對於大規模問題來說，有遞歸不可比擬的優勢，這也是動態規劃算法的核心之處。
確定了動態規劃的這三要素，整個求解過程就可以用一個最優決策表來描述，最優決策表是一個二維表，其中行表示決策的階段，列表示問題狀態，表格需要填寫的數據一般對應此問題的在某個階段某個狀態下的最優值（如最短路徑，最長公共子序列，最大價值等），填表的過程就是根據遞推關係，從1行1列開始，以行或者列優先的順序，依次填寫表格，最後根據整個表格的數據通過簡單的取舍或者運算求得問題的最優解。
六、動態規劃——幾個典型案例
1、計算二項式係數
問題描述：
計算二項式係數
問題解析：
在排列組合中，我們有以下公式：
當n>k>0時，C(n,k) = C(n-1,k-1) + C(n-1,k)
這個式子將C(n,k)的計算問題簡化為（問題描述）C(n-1,k-1)和C(n-1,k)兩個較小的交疊子問題。
初始條件：C(n,n) = C(n,0) = 0；
我們可以用填矩陣的方式求解C(n,k)：
上圖即為二項式係數矩陣表。
那麼，我們要計算出任一C(n,k)，我們可以嚐試求出所有的二項式係數表格，然後通過查表來進行計算操作。
這裏，我們的構建二項式係數表的函數為（填矩陣）：
int BinoCoef(int n, int k);
函數及具體程序實現如下：
#include <stdio.h>
#define MAX 100
int BinoCoef(int n, int k);
int main(){
int n,k,result;
printf("Please input n and k:\n");
scanf("%d %d",&n,&k);
result = BinoCoef(n,k);
printf("The corrsponding coefficent is %d !\n",result);
return 0;
}
int BinoCoef(int n, int k){
int data[MAX][MAX];
int i,j;
for(i=0;i<=n;i++)
{
for(j=0;j<=((i<k)?i:k);j++)
{
if(i == 0||i == j)
data[i][j] = 1;
else
data[i][j] = data[i-1][j] + data[i-1][j-1];
}
}
return data[n][k];
}
這裏，我們要注意動態規劃時的這樣幾個關鍵點：
(1)、怎麼描述問題，要把問題描述為交疊的子問題；
(2)、交疊子問題的初始條件（邊界條件）；
(3)、動態規劃在形式上往往表現為填矩陣的形式；
(4)、遞推式的依賴形式決定了填矩陣的順序。
2、三角數塔問題：
問題描述：
設有一個三角形的數塔，頂點為根結點，每個結點有一個整數值。從頂點出發，可以向左走或向右走，要求從根結點開始，請找出一條路徑，使路徑之和最大，隻要輸出路徑的和。如圖所示：
當然，正確路徑為13-8-26-15-24（和為86）。
問題解析：
現在，如何求出該路徑？
首先，我們用數組保存三角形數塔，並設置距離矩陣d[i][j]，用於保存節點(i,j)到最底層的最長距離，從而，d[1][1]即為根節點到最底層的最大路徑的距離。
|
行/列 |
1 |
2 |
3 |
4 |
5 |
|
1 |
13 |
|
|
|
|
|
2 |
11 |
8 |
|
|
|
|
3 |
12 |
7 |
26 |
|
|
|
4 |
6 |
14 |
15 |
8 |
|
|
5 |
12 |
7 |
13 |
24 |
11 |
方法一：遞推方式
對應函數：void fnRecursive(int,int);
對於遞推方式，其基本思想是基於指定位置，逐層求解：
舉例：找尋從點(1,1)開始逐層向下的路徑的最長距離。
思想：自底向上的逐步求解（原因在於，這是一個三角形的矩陣形式，向上收縮，便於求解）。
首先，在最底層，d[n][j]=a[n][j](將最底層的節點到最底層的最長路徑距離設置為節點值)。
然後，逐層向上進行路徑距離處理，這裏需要注意距離處理公式：
d[i-1][j] = min{ (d[i][j] + a[i-1][j]), (d[i][j+1] + a[i-1][j]) }
最後，遞推處理路徑距離至根節點即可，這樣就建立了一個完整的路徑最長距離矩陣，用來保存三角數塔節點到最底層的最長路徑距離。
方法二：記憶化搜索方式
對應函數：int fnMemorySearch(int i,int j);
記憶化搜索方式的核心在於保存前麵已經求出的距離值，然後根據這些距離值可以求出後麵所需求解的距離值。該函數的返回值即為節點(i,j)到最底層的最長路徑距離值。
這裏，我們可以去考究這樣幾個問題：
（1）在什麼時候結束？
（2）有何限製條件和普通情況處理？
問題1解析：
當d[i][j]>0時，則說明節點(i,j)到最底層的最長路徑距離已經存在，因此直接返回該值即可；
問題2解析：
限製條件：當節點(i,j)位於最底層時，即i==n時，這時d[i][j]應該初始化為a[i][j]；
普通情況處理：即節點(i,j)的賦值問題。
這裏有兩種情況：
第一種情況，節點(i,j)對應的最長路徑的下一層節點為左邊節點：
此時，d[i][j] = a[i][j] + fnMemorySearch(i+1,j);
第二種情況，節點(i,j)對應的最長路徑的下一層節點為右邊節點：
此時，d[i][j] = a[i][j] + fnMemorySearch(i+1,j+1);
代碼實現：
#include <stdio.h>
#include <stdlib.h>
#define MAXN 101
int n,d[MAXN][MAXN];
int a[MAXN][MAXN];
void fnRecursive(int,int);
//遞推方法函數聲明
int fnMemorySearch(int,int);
//記憶化搜索函數聲明
int main()
{
int i,j;
printf("輸入三角形的行數n(n=1-100):\n");
scanf("%d",&n);
printf("按行輸入數字三角形上的數(1-100):\n");
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
scanf("%d",&a[i][j]);
for(i=1; i<=n; i++)
for(j=1; j<=i; j++)
d[i][j]=-1;//初始化指標數組
printf("遞推方法：1\n記憶化搜索方法：2\n");
int select;
scanf("%d",&select);
if(select==1)
{
fnRecursive(i,j);//調用遞推方法
printf("\n%d\n",d[1][1]);
}
else if(select==2)
{
printf("\n%d\n",fnMemorySearch(1,1));//調用記憶化搜索方法
}
else
printf("輸入錯誤！");
return 0;
}
void fnRecursive(int i,int j)
//遞推方法實現過程
{
for(j=1; j<=n; j++)
d[n][j]=a[n][j];
for(i=n-1; i>=1; i--)
for(j=1; j<=i; j++)
d[i][j]=a[i][j]+(d[i+1][j]>d[i+1][j+1]?d[i+1][j]:d[i+1][j+1]);
}
int fnMemorySearch(int i,int j)
//記憶化搜索實現過程
{
if(d[i][j]>=0) return d[i][j];
if(i==n) return(d[i][j]=a[i][j]);
if(fnMemorySearch(i+1,j)>fnMemorySearch(i+1,j+1))
return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j)));
else
return(d[i][j]=(a[i][j]+fnMemorySearch(i+1,j+1)));
}
3、硬幣問題
問題描述：
有n種硬幣，麵值分別為V1,V2,…,Vn元，每種有無限多。給定非負整數S，可以選用多少硬幣，使得麵值之和恰好為S元，輸出硬幣數目的最小值和最大值。（1<=n<=100,0<=S<=10000,1<=Vi<=S）
問題解析：
首先證明該問題問題具有最優子結構。假設組合成S元錢有最優解，而且最優解中使用了麵值Vi的硬幣，同時最優解使用了k個硬幣。那麼，這個最優解包含了對於組合成S-Vi元錢的最優解。顯然，S-Vi元錢的硬幣中使用了k-1個硬幣。如果S-Vi元錢還有一個解使用了比k-1少的硬幣，那麼使用這個解可以為找S元錢產生小於k個硬幣的解。與假設矛盾。
另外，對於有些情況下，貪心算法可能無法產生最優解。比如硬幣麵值分別為1、10、25。組成30元錢，最優解是3*10，而貪心的情況下產生的解是1*5+25。
對於貪心算法，有一個結論：假設可換的硬幣單位是c的冪，也就是c^0、c^1、...、 c^k，其中整數c>1，k>=1，在這種情況下貪心算法可以產生最優解。
上麵已經證明該問題具有最優子結構，因此可以用動態規劃求解該硬幣問題。
====>>>：
設min[j]為組合成j元錢所需的最少的硬幣數，max[j]為組合成j元錢所需的最多的硬幣數。
從而有，對於最小組合過程，我們盡可能使用大麵值的硬幣（不是必然，否則成為貪心算法），其滿足下麵的遞推公式：
當j=0時，min[0] = 0；//即組合成0元錢的所需硬幣數為0，顯而易見。
當j>0時，如果j > Vk且min[j] < 1 + min[j-Vk]，則有min[j] = 1 + min[j-Vk]；對於這一步，其思想是盡可能通過大麵值硬幣來減少所需硬幣數。
而對於最大組合過程，我們則是盡量使用小麵值的硬幣（此過程，同貪心算法一樣），其滿足下麵的遞推公式：
當j = 0時，max[0] = 0；//顯而易見。
當j > 0時，如果j > Vk且max[j] > 1 + max[j - Vk]，則有max[j] = 1 + max[j-Vk]；
如此，我們對整個麵值構成過程進行了簡單的處理，得到了不同麵值和情況下所需的硬幣數。
現在，舉例來說明此過程：
就上麵所提及的用1、10、25麵值硬幣來組成30元錢的過程，我們進行相關說明：
首先，min[0] = max[0] = 0，同時初始化min[i] = INF，max[i] = -INF，i!=0。
然後，我們根據上麵的兩個遞推公式，可以得到min[]和max[]的最終數據。
其數據最終為：
min[] = {0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,2,3,4,5,6,1,2,3,4,5,3};
max[] = {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,...,28,19,30};
於是根據min[]和max[]，我們便可以得到所需硬幣數，並通過print_ans函數打印具體組合。
代碼實現：
#include <stdio.h>
#include <stdlib.h>
#define INF 100000000
#define MAXNUM 10000
#define MONEYKIND 100
int n,S;
int V[MONEYKIND];
int min[MAXNUM],max[MAXNUM];
void dp(int*,int*);
//遞推方法函數聲明
void print_ans(int*,int);
//輸出函數聲明
int main()
{
int i;
printf("輸入硬幣的種數n(1-100):\n");
scanf("%d",&n);
printf("輸入要組合的錢數S(0-10000):\n");
scanf("%d",&S);
printf("輸入硬幣種類：\n");
for(i=1; i<=n; i++)
{
scanf("%d",&V[i]);
}
dp(min,max);
printf("最小組合方案：\n");
print_ans(min,S);
printf("\n");
printf("最大組合方案：\n");
print_ans(max,S);
return 0;
}
void dp(int *min,int *max)
//遞推過程實現
{
int i,j;
min[0] = max[0] = 0;
for(i=1; i<=S; i++)//初始化數組
{
min[i]=INF;
max[i]=-INF;
}
for(i=1; i<=S; i++)
for(j=1; j<=n; j++)
if(i>=V[j])
{
if(min[i-V[j]]+1<min[i]){
min[i]=min[i-V[j]]+1;//最小組合過程
//printf("%d\n",min[i]);
}
if(max[i-V[j]]+1>max[i])
max[i]=max[i-V[j]]+1;//最大組合過程
}
}
void print_ans(int *d,int S)
//輸出函數實現
{
int i;
for(i=1; i<=n; i++)
if(S>=V[i]&&d[S]==d[S-V[i]]+1)
{
printf("%d ",V[i]);
print_ans(d,S-V[i]);
break;
}
}
對於上麵的代碼，還需要說明的是print_ans函數的實現過程：
遞歸地打印出組合中的硬幣（麵值由小到大），每次遞歸時減少已打印出的硬幣麵值。
討論：
貪心算法的適用性（僅指最小組合）：
對於貪心算法，有一個結論：假設可換的硬幣單位是c的冪，也就是c^0、c^1、...、 c^k，其中整數c>1，k>=1，在這種情況下貪心算法可以產生最優解。
貪心算法的過程：對硬幣麵值進行升序排序，先取最大麵值（排序序列最後一個元素）進行極大匹配（除法），然後對餘數進行類上操作。
因此，在這裏，注意貪心算法與動態規劃的區別：
動態規劃和貪心算法都是一種遞推算法；
均由局部最優解來推導全局最優解。
不同點：
貪心算法：
(1)、貪心算法中，作出的每步貪心決策都無法改變，因為貪心策略是由上一步的最優解推導下一步的最優解，而上一部之前的最優解則不作保留。
(2)、由（1）中的介紹，可以知道貪心法正確的條件是：每一步的最優解一定包含上一步的最優解
動態規劃算法：
(1)、全局最優解中一定包含某個局部最優解，但不一定包含前一個局部最優解，因此需要記錄之前的所有最優解；
(2)、動態規劃的關鍵是狀態轉移方程，即如何由以求出的局部最優解來推導全局最優解；
(3)、邊界條件：即最簡單的，可以直接得出的局部最優解。
最後更新：2017-04-03 05:39:52