動態(tài)規(guī)劃算法

--動態(tài)規(guī)劃算法算法設(shè)計與分析動態(tài)規(guī)劃算法1、認(rèn)識動態(tài)規(guī)劃算法2、算法框架3、動態(tài)規(guī)劃應(yīng)用

在動態(tài)規(guī)劃算法策略中:

體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進行決策,并通過多階段決策來最終解決問題。

在各個階段采取決策后,會不斷決策出新的數(shù)據(jù),直到找到最優(yōu)解.每次決策依賴于當(dāng)前狀態(tài),又隨即引起狀態(tài)的轉(zhuǎn)移。

一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義。所以，這種多階段決策最優(yōu)化的解決問題的過程稱為動態(tài)規(guī)劃。

1認(rèn)識動態(tài)規(guī)劃【例1】數(shù)塔問題

如圖所示的一個數(shù)塔，從頂部出發(fā)，在每一結(jié)點可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。

問題分析算法設(shè)計小結(jié)

問題分析

這個問題用貪婪算法有可能會找不到真正的最大和。以上圖為例就是如此。用貪婪的策略，則路徑和分別為：

9+15+8+9+10=51（自上而下），

19+2+10+12+9=52（自下而上）。都得不到最優(yōu)解，真正的最大和是：

9+12+10+18+10=59。

算法設(shè)計動態(tài)規(guī)劃設(shè)計過程如下：

1.階段劃分：第一步對于第五層的數(shù)據(jù)，我們做如下決策：對經(jīng)過第四層2的路徑選擇第五層的19，對經(jīng)過第四層18的路徑選擇第五層的10，對經(jīng)過第四層9的路徑也選擇第五層的10，對經(jīng)過第四層5的路徑選擇第五層的16。

以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?階子問題，遞推出第四層與第五層的和為:21(2+19),28(18+10),19(9+10),21(5+16)。用同樣的方法還可以將4階數(shù)塔問題,變?yōu)?階數(shù)塔問題。……

最后得到的1階數(shù)塔問題，就是整個問題的最優(yōu)解。2．存儲、求解：

1)原始信息存儲原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型變量n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲成如下的下三角陣:9121510682189519710416

2)動態(tài)規(guī)劃過程存儲必需用二維數(shù)組a存儲各階段的決策結(jié)果。二維數(shù)組a的存儲內(nèi)容如下：

a[n][j]=data[n][j]j=1,2,……,n；

i=n-1,n-2,……1，j=1,2,……,i；時

a[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]

最后a[1][1]存儲的就是問題的結(jié)果。

3)最優(yōu)解路徑求解及存儲僅有數(shù)組data和數(shù)組a可以找到最優(yōu)解的路徑，但需要自頂向下比較數(shù)組data和數(shù)組a是可以找到。

數(shù)組data數(shù)組a95912155049106838342921895212819211971041619710416數(shù)塔及動態(tài)規(guī)劃過程數(shù)據(jù)總結(jié)

動態(tài)規(guī)劃=貪婪策略+遞推(降階)+存儲遞推結(jié)果貪婪策略、遞推算法都是在“線性”地解決問題，而動態(tài)規(guī)劃則是全面分階段地解決問題。可以通俗地說動態(tài)規(guī)劃是“帶決策的多階段、多方位的遞推算法”。

1.適合動態(tài)規(guī)劃的問題特征

動態(tài)規(guī)劃算法的問題及決策應(yīng)該具有三個性質(zhì)：最優(yōu)化原理、無后向性、子問題重疊性質(zhì)。1)最優(yōu)化原理(或稱為最佳原則、最優(yōu)子結(jié)構(gòu))。2)無后向性(無后效性)。

3)有重疊子問題。2、算法框架

2.動態(tài)規(guī)劃的基本思想動態(tài)規(guī)劃方法的基本思想是，把求解的問題分成許多階段或多個子問題，然后按順序求解各子問題。最后一個子問題就是初始問題的解。由于動態(tài)規(guī)劃的問題有重疊子問題的特點，為了減少重復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀態(tài)保存在一個二維數(shù)組中。

3.設(shè)計動態(tài)規(guī)劃算法的基本步驟設(shè)計一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法的步驟：

1)劃分階段

2)選擇狀態(tài)

3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程但是,實際應(yīng)用當(dāng)中的簡化步驟：

1)分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。

2)遞推地定義最優(yōu)值。

3)以自底向上的方式或自頂向下的記憶化方法(備忘錄法)計算出最優(yōu)值.4)根據(jù)計算最優(yōu)值時得到的信息，構(gòu)造問題的最優(yōu)解。3、動態(tài)規(guī)劃應(yīng)用【例1】

背包問題

給定n種物品和一個容量為C的背包，物品i的重量是wi，其價值為vi，背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?

前i個物品(1≤i≤n)定義的實例：物品的重量分別為w1,…,wi，價值分別為v1，…，vi，

背包的承重量為j(1≤j≤W)。

設(shè)V[i,j]為該實例的最優(yōu)解的物品總價值，也就是說，是能夠放進承重量為j的背包中的前i個物品中最有價值子集的總價值。

可以把前i個物品中能夠放進承重量為j的背包中的子集分成兩個類別：

1、包括第i個物品的子集

2、不包括第i個物品的子集算法分析有下面的結(jié)論：

1.根據(jù)定義，在不包括第i個物品的子集中，最優(yōu)子集的價值是V[i-1,j].2．在包括第i個物品的子集中(因此，j—w≥0)，最優(yōu)子集是由該物品和前i-1個物品中能夠放進承重量為wj的背包的最優(yōu)子集組成。這種最優(yōu)子集的總價值等于Vi+V[i-1,j-wi]。因此，在前j個物品中最優(yōu)解的總價值等于這兩個價值中的較大值。Max{V[i-1,j],vi+V[i-1,j-wi]}

j-wi≥0V[i，j]﹛

V[i-1,j]j-wi<0【例3】求兩個字符序列的最長公共字符子序列。

問題分析

算法設(shè)計

算法(遞歸形式)

算法(非遞歸)例如：X=“ABCBDAB”,Y=“BCDB”是X的一個子序列

問題分析若A的長度為n，若B的長度為m，則

A的子序列共有：

B的子序列共有：

如采用枚舉策略，當(dāng)m=n時，共進行串比較：

此問題不可能簡單地分解成幾個獨立的子問題，也不能用分治法來解。所以，我們只能用動態(tài)規(guī)劃的方法去解決。

算法設(shè)計1．遞推關(guān)系分析設(shè)A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-1”，

Z=“z0,z1,…,zk-1”

為它們的最長公共子序列。有以下結(jié)論：

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”的一個最長公共子序列。

算法設(shè)計【例4】最長不降子序列

設(shè)有由n個不相同的整數(shù)組成的數(shù)列，記為:a(1)、a(2)、……、a(n)且a(i)<>a(j)(i<>j)

若存在i1<i2<i3<…<ik且有a(i1)<a(i2)<…<a(ik)，則稱為長度為k的不下降序列。請求出一個數(shù)列的最長不下降序列。

算法設(shè)計

算法

算法設(shè)計1.遞推關(guān)系

1)對a(n)來說，由于它是最后一個數(shù)，所以當(dāng)從a(n)開始查找時,只存在長度為1的不下降序列；

2)若從a(n-1)開始查找，則存在下面的兩種可能性：

(1)若a(n-1)<a(n)則存在長度為2的不下降序列a(n-1)，a(n)。

(2)若a(n-1)>a(n)則存在長度為1的不下降序列a(n-1)或a(n)。

3)一般若從a(i)開始,此時最長不下降序列應(yīng)該按下列方法求出:在a(i+1),a(i+2),…,a(n)中，找出一個比a(i)大的且最長的不下降序列，作為它的后繼。

2.數(shù)據(jù)結(jié)構(gòu)設(shè)計用數(shù)組a[i]記錄1到n的不相同的整數(shù)數(shù)列用數(shù)組b[i],記錄點i到n的最長的不降子序列的長度用數(shù)組c[i]分別點i后繼接點的編號

intmaxn=100;

inta[maxn],b[maxn],c[maxn];

main(){intn,i,j,max,p;

input(n);

for(i=1;i<n;i++)

{input(a[i]);

b[i]=1;

c[i]=0;}

算法for(i=n-1;i>=1;i=i-1)

{max=0;p=0;

for(j=i+1;j<=n;j=j+1)

if(a[i]<a[j]andb[j]>max){max=b[j];p=j;}

if(p<>0)