[psac]

八、動態規劃法

經常會遇到複雜問題不能簡單地分解成幾個子問題，而會分解出一系列的子問題。簡單地採用把大問題分解成子問題，並綜合子問題的解匯出大問題的解的方法，問題求解耗時會按問題規模呈冪級數增加。
為了節約重複求相同子問題的時間，引入一個陣列，不管它們是否對最終解有用，把所有子問題的解存於該陣列中，這就是動態規劃法所採用的基本方法。以下先用實例說明動態規劃方法的使用。
【問題】 求兩字元序列的最長公共字元子序列
問題描述：字元序列的子序列是指從給定字元序列中隨意地（不一定連續）去掉若干個字元（可能一個也不去掉）後所形成的字元序列。令給定的字元序列X=「x0，x1，…，xm-1」，序列Y=「y0，y1，…，yk-1」是X的子序列，存在X的一個嚴格遞增上標序列<i0，i1，…，ik-1>，使得對所有的j=0，1，…，k-1，有xij=yj。例如，X=「ABCBDAB」，Y=「BCDB」是X的一個子序列。
給定兩個序列A和B，稱序列Z是A和B的公共子序列，是指Z同是A和B的子序列。問題要求已知兩序列A和B的最長公共子序列。
如採用列舉A的所有子序列，並一一檢查其是否又是B的子序列，並隨時記錄所發現的子序列，最終求出最長公共子序列。這種方法因耗時太多而不可取。
考慮最長公共子序列問題如何分解成子問題，設A=「a0，a1，…，am-1」，B=「b0，b1，…，bm-1」，並Z=「z0，z1，…，zk-1」為它們的最長公共子序列。不難證明有以下性質：
（1） 如果am-1=bn-1，則zk-1=am-1=bn-1，且「z0，z1，…，zk-2」是「a0，a1，…，am-2」和「b0，b1，…，bn-2」的一個最長公共子序列；
（2） 如果am-1!=bn-1，則若zk-1!=am-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列；
（3） 如果am-1!=bn-1，則若zk-1!=bn-1，蘊涵「z0，z1，…，zk-1」是「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列。
這樣，在找A和B的公共子序列時，如有am-1=bn-1，則進一步解決一個子問題，找「a0，a1，…，am-2」和「b0，b1，…，bm-2」的一個最長公共子序列；如果am-1!=bn-1，則要解決兩個子問題，找出「a0，a1，…，am-2」和「b0，b1，…，bn-1」的一個最長公共子序列和找出「a0，a1，…，am-1」和「b0，b1，…，bn-2」的一個最長公共子序列，再取兩者中較長者作為A和B的最長公共子序列。
定義c[j]為序列「a0，a1，…，ai-2」和「b0，b1，…，bj-1」的最長公共子序列的長度，計算c[j]可遞回地表述如下：
（1）c[j]=0 如果i=0或j=0；
（2）c[j]= c[i-1][j-1]+1 如果I，j>0，且a[i-1]=b[j-1]；
（3）c[j]=max（c[j-1]，c[i-1][j]） 如果I，j>0，且a[i-1]!=b[j-1]。
按此算式可寫出計算兩個序列的最長公共子序列的長度函數。由於c[j]的產生僅依賴於c[i-1][j-1]、c[i-1][j]和c[j-1]，故可以從c[m][n]開始，跟蹤c[j]的產生程序，逆向構造出最長公共子序列。細節見程序。
# include <stdio.h>
# include <string.h>
# define N 100
char a[N],b[N],str[N];

int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i<=m;i++) c[0]=0;
for (i=0;i<=n;i++) c[0]=0;
for (i=1;i<=m;i++)
for (j=1;j<=m;j++)
if (a[i-1]==b[j-1])
c[j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[j-1])
c[j]=c[i-1][j];
else
c[j]=c[j-1];
return c[m][n];
}

char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=』\0』;
while (k>0)
if (c[j]==c[i-1][j]) i--;
else if (c[j]==c[j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}

void main()
{ printf (「Enter two string（<%d）!\n」,N);
scanf(「%s%s」,a,b);
printf(「LCS=%s\n」,build_lcs(str,a,b));
}
1、動態規劃的適用條件
任何思想方法都有一定的局限性，超出了特定條件，它就失去了作用。同樣，動態規劃也並不是萬能的。適用動態規劃的問題必須滿足最最佳化原理和無後效性。
（1）最最佳化原理（最優子結構性質）
最最佳化原理可這樣闡述：一個最最佳化原則具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，餘下的諸決策必須構成最優原則。簡而言之，一個最最佳化原則的子原則總是最優的。一個問題滿足最最佳化原理又稱其具有最優子結構性質。

圖2
例如圖2中，若路線I和J是A到C的最優路徑，則根據最最佳化原理，路線J必是從B到C的最優路線。這可用反證法證明：假設有另一路徑J』是B到C的最優路徑，則A到C的路線取I和J』比I和J更優，矛盾。從而證明J』必是B到C的最優路徑。
最最佳化原理是動態規劃的基礎，任何問題，如果失去了最最佳化原理的支持，就不可能用動態規劃方法計算。根據最最佳化原理匯出的動態規劃基本方程是解決一切動態規劃問題的基本方法。
（2）無後向性
將各階段按照一定的次序排列好之後，對於某個給定的階段狀態，它以前各階段的狀態無法直接影響它未來的決策，而只能通過現用的這個狀態。換句話說，每個狀態都是過去歷史的一個完整總結。這就是無後向性，又稱為無後效性。
（3）子問題的重疊性
動態規划算法的關鍵在於解決冗余，這是動態規划算法的根本目的。動態規劃實質上是一種以空間換時間的技術，它在實現的程序中，不得不儲存於產生程序中的各種狀態，所以它的空間複雜度要大於其它的算法。選項動態規划算法是因為動態規划算法在空間上可以承受，而搜尋算法在時間上卻無法承受，所以我們捨空間而取時間。
所以，能夠用動態規劃解決的問題還有一個顯著特徵：子問題的重疊性。這個性質並不是動態規劃適用的必要條件，但是如果該性質無法滿足，動態規划算法同其他算法相比就不具備優勢。
2、動態規劃的基本思想
前文主要介紹了動態規劃的一些理論依據，我們將前文所說的具有明顯的階段劃分和狀態轉移方程的動態規劃稱為標準動態規劃，這種標準動態規劃是在研究多階段決策問題時推匯出來的，具有嚴格的數學形式，適合用於理論上的分析。在實際套用中，許多問題的階段劃分並不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規模更小的子問題，並且原問題的最優解中包含了子問題的最優解（即滿足最優子化原理），則可以考慮用動態規劃解決。
動態規劃的實質是分治思想和解決冗余，因此，動態規劃是一種將問題實例分解為更小的、相似的子問題，並儲存於子問題的解而避免計算重複的子問題，以解決最最佳化問題的算法原則。
由此可知，動態規劃法與分治法和貪心法類似，它們都是將問題實例歸納為更小的、相似的子問題，並通過求解子問題產生一個全局最優解。其中貪心法的當前選項可能要依賴已經作出的所有選項，但不依賴於有待於做出的選項和子問題。因此貪心法自頂向下，一步一步地作出貪心選項；而分治法中的各個子問題是獨立的（即不包含公共的子子問題），因此一旦遞回地求出各子問題的解後，便可自下而上地將子問題的解合併成問題的解。但不足的是，如果當前選項可能要依賴子問題的解時，則難以通過局部的貪心原則達到全局最優解；如果各子問題是不獨立的，則分治法要做許多不必要的工作，重複地解公共的子問題。
解決上述問題的辦法是利用動態規劃。該方法主要套用於最最佳化問題，這類問題會有多種可能的解，每個解都有一個值，而動態規劃找出其中最優（最大或最小）值的解。若存在若干個取最優值的解的話，它只取其中的一個。在求解程序中，該方法也是通過求解局部子問題的解達到全局最優解，但與分治法和貪心法不同的是，動態規劃允許這些子問題不獨立，（亦即各子問題可包含公共的子子問題）也允許其通過自身子問題的解作出選項，該方法對每一個子問題只解一次，並將結果儲存起來，避免每次碰到時都要重複計算。
因此，動態規劃法所針對的問題有一個顯著的特徵，即它所對應的子問題樹中的子問題呈現大量的重複。動態規劃法的關鍵就在於，對於重複出現的子問題，只在第一次遇到時加以求解，並把答案儲存起來，讓以後再遇到時直接引用，不必重新求解。
3、動態規划算法的基本步驟
設計一個標準的動態規划算法，通常可按以下幾個步驟進行：
（1）劃分階段：按照問題的時間或空間特徵，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無後向性），否則問題就無法用動態規劃求解。
（2）選項狀態：將問題發展到各個階段時所處於的各種客觀情況用不同的狀態表示出來。當然，狀態的選項要滿足無後效性。
（3）確定決策並寫出狀態轉移方程：之所以把這兩步放在一起，是因為決策和狀態轉移有著天然的聯繫，狀態轉移就是根據上一階段的狀態和決策來匯出本階段的狀態。所以，如果我們確定了決策，狀態轉移方程也就寫出來了。但事實上，我們常常是反過來做，根據相鄰兩段的各狀態之間的關係來確定決策。
（4）寫出規劃方程（包括邊界條件）：動態規劃的基本方程是規劃方程的通用形式化陳述式。
一般說來，只要階段、狀態、決策和狀態轉移確定了，這一步還是比較簡單的。動態規劃的主要難點在於理論上的設計，一旦設計完成，實現部分就會非常簡單。根據動態規劃的基本方程可以直接遞回計算最優值，但是一般將其改為遞推計算，實現的大體上的框架如下：
標準動態規劃的基本框架
1. 對fn+1(xn+1)啟始化; {邊界條件}
for k:=n downto 1 do
for 每一個xk∈Xk do
for 每一個uk∈Uk(xk) do
begin
5. fk(xk):=一個極值; {∞或－∞}
6. xk+1:=Tk(xk,uk); {狀態轉移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
if t比fk(xk)更優 then fk(xk):=t; {計算fk(xk)的最優值}
end;
9. t:=一個極值; {∞或－∞}
for 每一個x1∈X1 do
11. if f1(x1)比t更優 then t:=f1(x1); {按照10式求出最優指標}
12. 輸出t;
但是，實際套用當中經常不顯式地按照上面步驟設計動態規劃，而是按以下幾個步驟進行：
（1）分析最優解的性質，並刻劃其結構特徵。
（2）遞回地定義最優值。
（3）以自底向上的方式或自頂向下的記憶化方法（備忘錄法）計算出最優值。
（4）根據計算最優值時得到的訊息，構造一個最優解。
步驟（1）～（3）是動態規划算法的基本步驟。在只需要求出最優值的情形，步驟（4）可以省略，若需要求出問題的一個最優解，則必須執行步驟（4）。此時，在步驟（3）中計算最優值時，通常需記錄更多的訊息，以便在步驟（4）中，根據所記錄的訊息，快速地構造出一個最優解。

【問題】 凸多邊形的最優三角剖分問題
問題描述：多邊形是平面上一條分段線性的閉曲線。也就是說，多邊形是由一系列首尾相接的直線段組成的。組成多邊形的各直線段稱為該多邊形的邊。多邊形相接兩條邊的連接點稱為多邊形的頂點。若多邊形的邊之間除了連接頂點外沒有別的公共點，則稱該多邊形為簡單多邊形。一個簡單多邊形將平面分為3個部分：被包圍在多邊形內的所有點構成了多邊形的內部；多邊形本身構成多邊形的邊界；而平面上其餘的點構成了多邊形的外部。當一個簡單多邊形及其內部構成一個閉凸集時，稱該簡單多邊形為凸多邊形。也就是說凸多邊形邊界上或內部的任意兩點所連成的直線段上所有的點均在該凸多邊形的內部或邊界上。
通常，用多邊形頂點的逆時針序列來表示一個凸多邊形，即P=<v0，v1，…，vn-1>表示具有n條邊v0v1，v1v2，…，vn-1vn的一個凸多邊形，其中，約定v0=vn 。
若vi與vj是多邊形上不相鄰的兩個頂點，則線段vivj稱為多邊形的一條弦。弦將多邊形分割成凸的兩個子多邊形<vi，vi+1，…，vj>和<vj，vj+1，…，vi>。多邊形的三角剖分是一個將多邊形分割成互不重迭的三角形的弦的集合T。圖1是一個凸多邊形的兩個不同的三角剖分。

(a) (b)
圖1 一個凸多邊形的2個不同的三角剖分
在凸多邊形P的一個三角剖分T中，各弦互不相交且弦數已達到最大，即P的任一不在T中的弦必與T中某一弦相交。在一個有n個頂點的凸多邊形的三角刮分中，恰好有n-3條弦和n-2個三角形。
凸多邊形最優三角剖分的問題是：給定一個凸多邊形P=<v0，v1，…，vn-1>以及定義在由多邊形的邊和弦組成的三角形上的權函數ω。要求確定該凸多邊形的一個三角剖分，使得該三角剖分對應的權即剖分中諸三角形上的權之和為最小。
可以定義三角形上各種各樣的權函數ω。例如：定義ω(△vivjvk)=| vivj |+| vivk |+| vkvj |，其中，| vivj |是點vi到vj的歐氏距離。相應於此權函數的最優三角剖分即為最小弦長三角剖分。
（1）最優子結構性質
凸多邊形的最優三角剖分問題有最優子結構性質。事實上，若凸（n+1）邊形P=<v0，v1 ，…，vn>的一個最優三角剖分T包含三角形v0vkvn，1≤k≤n-1，則T的權為3個部分權的和，即三角形v0vkvn的權，子多邊形<v0，v1，…，vk>的權和<vk，vk+1，…，vn>的權之和。可以斷言由T所確定的這兩個子多邊形的三角剖分也是最優的，因為若有<v0，v1，…，vk>或<vk，vk+1，…，vn>的更小權的三角剖分，將會導致T不是最優三角剖分的矛盾。
（2）最優三角剖分對應的權的遞回結構
首先，定義t[i，j]（1≤i<j≤n）為凸子多邊形<vi-1，vi，…，vj>的最優三角剖分所對應的權值，即最優值。為方便起見，設退化的多邊形<vi-1，vi>具有權值0。據此定義，要計算的凸（n+1）邊多邊形P對應的權的最優值為t[1，n]。
t[i，j]的值可以利用最優子結構性質遞回地計算。由於退化的2頂點多邊形的權值為0，所以t[i，i]=0，i=1，2，…，n 。當j一i≥1時，子多邊形<vi-1，vi，…，vj>至少有3個頂點。由最優於結構性質，t[i，j]的值應為t[i，k]的值加上t[k+1，j]的值，再加上△vi-1vkvj的權值，並在i≤k≤j-1的範圍內取最小。由此，t[i，j]可遞回地定義為：

（3）計算最優值
下面描述的計算凸（n+1）邊形P=<v0，v1，…，vn>的三角剖分最優權值的動態規划算法MINIMUM_WEIGHT，輸入是凸多邊形P=<v0，v1，…，vn>的權函數ω，輸出是最優值t[i，j]和使得t[i，k]+t[k+1，j]+ω（△vi-1vkvj）達到最優的位置（k=）s[i，j]，1≤i≤j≤n 。
Procedure MINIMUM_WEIGHT(P，w)；
Begin
n=length[p]-1;
for i=1 to n do t[i,i]:=0;
for ll=2 to n do
for i=1 to n-ll+1 do
begin
j=i+ll-1;
t[i,j]=∞;
for k=i to j-1 do
begin
q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
if q<t[i,j] then
begin
t[i,j]=q;
s[i,j]=k;
end;
end;
end;
return(t,s);
end;
算法MINIMUM_WEIGHT_佔用θ(n2)空間，耗時θ(n3)。
（4）構造最優三角剖分
如我們所看到的，對於任意的1≤i≤j≤n ，算法MINIMUM_WEIGHT在計算每一個子多邊形<vi-1，vi，…，vj>的最優三角剖分所對應的權值t[i，j]的同時，還在s[i，j]中記錄了此最優三角剖分中與邊（或弦）vi-1vj構成的三角形的第三個頂點的位置。因此，利用最優子結構性質並借助於s[i，j]，1≤i≤j≤n ，凸（n+l）邊形P=<v0，v1，…，vn>的最優三角剖分可容易地在Ο(n)時間內構造出來。

習題：
1、汽車加油問題：
設有路程長度為L公里的公路上，分佈著m個加油站，它們的位置分別為p（i=1，2，……，m），而汽車油箱加滿油後（油箱最多可以加油k升），可以行駛n公里。設計一個方案，使汽車經過此公路的加油次數盡量少（汽車出發時是加滿油的）。
2、最短路徑：
設有一個網路，要求從某個頂點出發到其他頂點的最短路徑
3、跳馬問題：
在8*8方格的棋碟上，從任意指定的方格出發，為馬尋找一條走遍棋盤每一格並且只經過一次的一條路徑。
4、二叉樹的遍歷
5、背包問題
6、用分治法實現兩個大整數相乘
7、設x1，x2，…，xn是直線上的n個點，若要用服務機構長度的閉區間去覆蓋這n個點，至少需要多少個這樣的服務機構閉區間？
8、用關係「＜」和「＝」將3個數A、B和C依次排列時，有13種不同的序關係：
A＝B＝C，A＝B＜C，A＜B＝C，A＜B＜C，A＜C＜B，A＝C＜B，B＜A＝C，
B＜A＜C，B＜C＜A，B＝C＜A，C＜A＝B，C＜A＜B，C＜A＜B。
若要將n個數依序進行排列，試設計一個動態規划算法，計算出有多少鍾不同的序關係。
9、有一種單人玩的遊戲：設有n(2<=n<=200)堆薄片，各堆順序用0至 n-1編號，極端情況，有的堆可能沒有薄片。在遊戲程序中，一次移動只能取某堆上的若干張薄片，移到該堆的相鄰堆上。如指定
I堆k張 k 移到I-1(I>0)堆，和將k 張薄片移至I+1(I<n-1)堆。所以當有兩個堆與 I 堆相鄰 時，I堆原先至少有2k 張薄片；只有一個堆與 I 堆相鄰 時， I 堆原先至少有k張薄片。
遊戲的目標是對給定的堆數，和各堆上的薄片數，按上述規則移動薄片，最終使 各堆的薄片數相同。為了使移動次數較少些，移動哪一堆薄片，和移多少薄片先作以下估算：
設
ci:I堆的薄片數(0<=I<n,0<=ci<=200);
v：每堆 的平均薄片數；
ai:I堆的相鄰堆可以從I堆得到的薄片數。
估算方法如下：
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
這裡並不希望準確地求出A0 至an-1，而是作以下處理：若令 a0 為0，能按上述算式計算出 A1至 an-1。程序找出 a 中的最小值，並讓全部a值減去這最小值，使每堆移去的薄片數大於等於0。
實際操作採用以下貪心原則：
（1）每次從第一堆出發順序搜尋每一堆，若發現可從 I堆移走薄片，就完成一次移動。即， I堆的相鄰堆從 I堆取走 ai片薄片。可從I 堆移薄片到相鄰堆取於 I堆薄片數：若I 堆是處於兩端位置( I=0 I=n-1), 要求 ci>=ai ；若 I堆是中間堆，則要求ci>=2ai。
（2）因在ai>0的所有堆中，薄片數最多的堆 在平分程序中被它的相鄰堆取走的薄片數也最多。在用原則（1）搜尋移動時，當發生沒有滿足條件（1）的可移走薄片的堆時，採用本原則，讓在ai>0的所有堆中，薄片數最多的堆被它的相鄰堆取走它的全部薄片。