第四章5(貪心、動態(tài))

第四章基本的算法策略4.5動態(tài)規(guī)劃

4.5.1認識動態(tài)規(guī)劃

4.5.2算法框架

4.5.3突出階段性的動態(tài)規(guī)劃應用

4.5.4突出遞推的動態(tài)規(guī)劃應用

2021/3/111

在動態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進行決策,并通過多階段決策來最終解決問題。在各個階段采取決策后,會不斷決策出新的數據,直到找到最優(yōu)解.每次決策依賴于當前狀態(tài),又隨即引起狀態(tài)的轉移。一個決策序列就是在變化的狀態(tài)中產生出來的，故有“動態(tài)”的含義。所以，這種多階段決策最優(yōu)化的解決問題的過程稱為動態(tài)規(guī)劃。

上節(jié)下節(jié)4.5動態(tài)規(guī)劃

2021/3/112

我們通過一個簡單的例子來說明動態(tài)規(guī)劃的多階段決策與貪婪算法有什么區(qū)別。

【例1】數塔問題

上節(jié)下節(jié)4.5.1認識動態(tài)規(guī)劃

2021/3/113【例1】數塔問題

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

問題分析算法設計算法小結2021/3/114

問題分析

這個問題用貪婪算法有可能會找不到真正的最大和。以圖4-11為例就是如此。用貪婪的策略，則路徑和分別為：9+15+8+9+10=51（自上而下），19+2+10+12+9=52（自下而上）。都得不到最優(yōu)解，真正的最大和是：9+12+10+18+10=59。

在知道數塔的全貌的前提下，可以用枚舉法或下一章將學習的搜索算法來完成。

上節(jié)下節(jié)2021/3/115

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

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

上節(jié)下節(jié)2021/3/116

以上的決策結果將五階數塔問題變?yōu)?階子問題，遞推出第四層與第五層的和為:21(2+19),28(18+10),19(9+10),21(5+16)。用同樣的方法還可以將4階數塔問題,變?yōu)?階數塔問題?！詈蟮玫降?階數塔問題，就是整個問題的最優(yōu)解。

上節(jié)下節(jié)2021/3/1172．存儲、求解：

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

上節(jié)下節(jié)2021/3/118

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

d[n][j]=data[n][j]j=1,2,……,n；i=n-1,n-2,……1，j=1,2,……,i；時d[i][j]=max(d[i+1][j]，d[i+1][j+1])+data[i][j]最后a[1][1]存儲的就是問題的結果。

上節(jié)下節(jié)2021/3/1193)最優(yōu)解路徑求解及存儲僅有數組data和數組a可以找到最優(yōu)解的路徑，但需要自頂向下比較數組data和數組a是可以找到。如圖4.5.2求解和輸出過程如下：

上節(jié)下節(jié)2021/3/1110輸出a[1][1]"9"b=d[1][1]-data[1][1]=59-9=50

b與d[2][1],d[2][2]比較b與d[2][1]相等輸出data[2][1]"12"b=d[2][1]-data[2][1]=50-12=38

b與d[3][1],d[3][2]比較b與d[3][1]相等輸出data[3][1]"10"b=a[3][1]-data[3][1]=38-10=28

b與d[4][1],d[4][2]比較b與d[4][2]相等輸出data[4][2]"18"b=d[4][2]-data[4][2]=28-18=10b與d[5][2],d[5][3]比較b與d[5][3]相等輸出data[5][3]"10“

上節(jié)下節(jié)2021/3/1111

數組data

數組d95912155049106838342921895212819211971041619710416

圖4-12數塔及動態(tài)規(guī)劃過程數據

上節(jié)下節(jié)2021/3/1112

為了設計簡潔的算法，我們最后用三維數組a[50][50][3]存儲以上確定的三個數組的信息。a[50][50][1]代替數組data，a[50][50][2]代替數組d,a[50][50][3]記錄解路徑。

上節(jié)下節(jié)2021/3/1113

數塔問題的算法main(){inta[50][50][3],i,j,n;

print('pleaseinputthenumberofrows:');

input(n);

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

forj=1toido

{input(a[i][j][1]);

a[i][j][2]=a[i][j][1];

a[i][j][3]=0;}

上節(jié)下節(jié)2021/3/1114for(i=n-1;i>=1;i--)

for(j=1;j>=i;j++)

if(a[i+1][j][2]>a[i+1][j+1][2])

{a[i][j][2]=a[i][j][2]+a[i+1][j][2];

a[i][j][3]=0;}

else

{a[i][j][2]=a[i][j][2]+a[i+1][j+1][2];

a[i][j][3]=1;}

print('max=’,a[1][1][2]);

j=1;

for(i=1;i<=n-1;i++){print(a[i][j][1],‘->’);

j=j+a[i][j][3];}

print(a[n][j][1]);}

上節(jié)下節(jié)2021/3/1115從例子中可以看到：

動態(tài)規(guī)劃=貪婪策略+遞推(降階)+存儲遞推結果貪婪策略、遞推算法都是在“線性”地解決問題，而動態(tài)規(guī)劃則是全面分階段地解決問題?？梢酝ㄋ椎卣f動態(tài)規(guī)劃是“帶決策的多階段、多方位的遞推算法”。

上節(jié)下節(jié)2021/3/1116

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

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

上節(jié)下節(jié)4.5.2

算法框架

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

上節(jié)下節(jié)2021/3/11183.設計動態(tài)規(guī)劃算法的基本步驟設計一個標準的動態(tài)規(guī)劃算法的步驟：1)劃分階段2)選擇狀態(tài)3)確定決策并寫出狀態(tài)轉移方程但是,實際應用當中的簡化步驟：1)分析最優(yōu)解的性質，并刻劃其結構特征。2)遞推地定義最優(yōu)值。3)以自底向上的方式或自頂向下的記憶化方法(備忘錄法)計算出最優(yōu)值.4)根據計算最優(yōu)值時得到的信息，構造問題的最優(yōu)解。

上節(jié)下節(jié)2021/3/11194.標準動態(tài)規(guī)劃的基本框架for(j=1;j<=m;j=j+1)//第一個階段

xn[j]=初始值；for(i=n-1;i>=1;i=i-1)//其它n-1個階段

for(j=1;j>=f(i);j=j+1)//f(i)與i有關的表達式

xi[j]=max(或min){g(xi-1[j1——j2])，……，

g(xi-1[jk——jk+1])}；t=g(x1[j1—j2]);//由最優(yōu)解求解最優(yōu)解的方案print(x1[j1]);

for(i=2;i<=n-1;i=i+1){t=t-xi-1[ji];for(j=1;j>=f(i);j=j+1)if(t=xi[ji])break;}

上節(jié)下節(jié)2021/3/1120

【例2】

資源分配問題。

【例3】

n個矩陣連乘的問題。

上節(jié)下節(jié)4.5.3突出階段性的動態(tài)規(guī)劃應用

2021/3/1121【例2】資源分配問題。設有資源a,分配給n個項目,gi(x)為第i個項目分得資源x所得到的利潤。求總利潤最大的資源分配方案，也就是解下列問題：maxz=g1(x1)+g2(x2)+……gn(xn)x1+xx2+x3+……xn=a,xi≥0,i=1，2,3,……,n函數gi(x)以數據表的形式給出.例如：現(xiàn)有7萬元投資到A，B，C三個項目，利潤見表,求問題總利潤最大的資源分配方案。

上節(jié)下節(jié)2021/3/1122

算法設計1．階段劃分及決策比較直觀的階段劃分就是逐步考慮每一個項目在不同投資額下的利潤情況。3.數據結構設計：1)開辟一維數組q來存儲原始數據。2)另開辟一維數組f存儲當前最大收益情況。3)開辟記錄中間結果的一維數組數組temp，記錄正在計算的最大收益。4)開辟二維數組a。5)數組gain存儲第i個工程投資數的最后結果。

上節(jié)下節(jié)2021/3/1123對于一般問題設計算法如下：main()

{inti,j,k,m,n,rest;inta[100][100]，gain[100];

floatq[100],f[100],temp[100];

print(“Howmangitem?”);input(m);print(“Howmangmoney?”);input(n);print(“inputgaintable:”);for(j=0;j<=n;j++)

{input(q[j]);f[j]=q[j];}

for(j=0;j<=n;j++)

a[1,j]=j;

上節(jié)下節(jié)2021/3/1124for(k=2;k<=m;k++)

{for(j=0;j<=n;j++)

{temp[j]=q[j];input(q[j]);a[k][j]=0;}

for(j=0;j<=n;j++)

for(i=0;i<=j;i++)

if（f[j-i]+q[i]>temp[j]）

{temp[j]=f[j-i]+q[i];a[k,j]=i;}for(j=0;j<=n;j++)f[j]=temp[j];

}

rest=n;

for(i=m;i>=1;i--){gain[i]=a[i][rest];rest=rest-gain[i];}for(i=1;i<=m;i++)print(gain[i],””);

print(f[n]);

}2021/3/1125

【例3】n個矩陣連乘的問題。

問題分析

算法設計

算法1(遞歸算法)

算法1說明

算法2(遞歸算法)

算法3(非遞歸算法)

輸出算法

上節(jié)下節(jié)2021/3/1126

問題分析多個矩陣連乘運算是滿足結合律的。例:M1[5*20]*M2[20*50]*M3[50*1]*M4[1*100]分別按((M1*M2)*M3)*M4，M1*(M2*(M3*M4))，(M1*(M2*M3))*M4的次序相乘,各需進行5750,115000,1600次乘法。這個問題要用“動態(tài)規(guī)劃”算法來完成:首先,從兩個矩陣相乘的情況開始；然后,嘗試三個矩陣相乘的情況；……最后,等到n個矩陣相乘所用的最少的乘法次數及結合方式。

上節(jié)下節(jié)2021/3/1127

算法設計

1.階段劃分

1）初始狀態(tài)為一個矩陣相乘的計算量為0;2）第二階段,計算兩個相鄰矩陣相乘的計算量,共n-1組3）第三階段,計算兩個相鄰矩陣相乘的計算量,共n-2組4）最后一個階段,是n個相鄰矩陣相乘的計算量,共1組,是問題解。

上節(jié)下節(jié)2021/3/11282.階段決策一般地，計算M1*M2*M3*……*Mn其中M1，M2，……,Mi分別是r1*r2，r2*r3，……,ri*ri+1階矩陣，i=1,2,3,……n。設mi,j是計算Mi*Mi+1*…Mj的最少乘法次數(1≤i≤j≤n),對mi,j有公式：0當i=j時ri-1*ri*ri+1當j=i+1時min(mi,k+mk+1,j+rirk+1rj+1)i≤k≤j當i<j時以上動態(tài)規(guī)劃方法是按s=0,1,2,3,.,n-1的順序計算mi,i+s的。3.記錄最佳期方案用二維矩陣comij(n*n)來存儲使mij為最小值時的k值。

上節(jié)下節(jié)2021/3/1129

算法1(遞歸算法)intr[100],com[100][100];main（）{intn,i;print(“Howmangmatrixes?”);input(n);peint(“Howsizeeverymatrixe?”);for(i=1;i<=n+1;i++)input(r[i]);print(“Theleastcalculatequantity：”,course(1,n));for(i=1;i<=n;i++){print(“換行符”);for(j=1;j<=n;j++)print(com[i][j]);}}

上節(jié)下節(jié)2021/3/1130intcourse(inti,intj){intu,t;if(i=j)return0;if(i=j-1){com[i][i+1]=i;return（r[i]*r[i+1]*r[r+2]）;}u=course(i,i)+course(i+1,j)+r[i]*r[i+1]*r[j+1];com[i][j]=i;for(intk=i+1;k<j;k++){t=course(i,k)+course(k+1,j)+r[i]*r[k+1]*r[j+1];if(t<u){u=t;com[i][j]=k;}}returnu;}

上節(jié)下節(jié)2021/3/1131

算法1說明

以上的遞歸算法雖然解決了問題，但效率很低，有子問題重疊，n=4時的遞歸過程如下圖：

上節(jié)下節(jié)2021/3/1132

算法2(改進后遞歸算法)intm[100][100],com[100][100],r[100];matrix2（）{intn,;print(“Howmangmatrixes?”);input(n);print(“Howsizeeverymatrixe?”);for(i=1;i<=n+1;i++)input(r[i]);for(i=1;i<=n;i++)/初始化化數組com和m。/for(j=1;j<=n;j++){com[i][j]=0;m[i][j]=0;}course(1,n)；print(“Theleastcalculatequantity：”m[1][n]);for(i=1;i<=n;i++){print(“換行符”);for(j=1;j<=n;j++)print(com[i][j]);}}

上節(jié)下節(jié)2021/3/1133course(inti,intj){if（m[i][j]>0）returnm[i][j];if(i=j)return0;if(i=j-1){com[i][i+1]=i;m[i][j]=r[i]*r[i+1]*r[i+2];returnm[i][j];}intu=course(i,i)+course(i+1,j)+r[i]*r[i+1]*r[j+1];com[i][j]=i;for(intk==i+1;k<j;k++){intt=course(i,k)+course(k+1,j)+r[i]*r[k+1]*r[j+1];if(t<u){u=t;com[i][j]=k;}}m[i][j]=u;returnu;}

上節(jié)下節(jié)2021/3/1134

算法3(非遞歸算法)main（）{intn,r[100],m[100][100],com[100][100];peint(“Howmangmatrixes?”);input(n);peint(“Howsizeeverymatrixe?”);for(i=1;i<=n+1;i++)input(r[i]);for(i=1;i<=n;i++)/初始化化數組com和m。/for(j=1;j<=n;j++)com[i][j]=0;for(i=1;i<n;i++){m[i][i]=0;\s=0\m[i][i+1]=r[i]*r[i+1]*r[i+2];\s=1\com[i][i+1]=i+1;}

上節(jié)下節(jié)2021/3/1135m[n][n]=0;for(s=2;s<=n-1;s++)/動態(tài)規(guī)劃過程/for(i=1;i<n-s+1;i++){j=i+s;m[i][j]=m[i][i]+m[i+1][j]+r[i]*r[i+1]*r[j+1];com[i][j]=i;for(k=i+1;k<j;k++){t=m[i][k]+m[k+1][j]+r[i]*r[k+1]*r[j+1];if(t<m[i][j]){m[i][j]=t;com[i][j]=k;}}}print(“Theleastcalculatequantity：”m[1][n]);for(i=1;i<=n;i++){print(“換行符”);for(j=1;j<=n;j++)print(com[i][j]);}}

上節(jié)下節(jié)2021/3/1136輸出部分的算法設計以上算法中關于矩陣相乘的結合方式，只是簡單的輸出了數組com的內容，不容易直觀地被利用，還需要繼續(xù)進行必要的人工處理，才能真正找到矩陣相乘的結合方式。怎么樣更直觀、合理地輸出結合過程？即算法的輸出能使用戶直接了解計算矩陣的過程。首先看一下com數組存儲的信息意義，它是一個二維數組，元素com[i][j]存儲的是Mi——Mj相乘的組合點k1，也就是說：Mi*Mi+1*……*Mj是由Mi*Mi+1*……Mk和Mk+1*……Mj同樣，在數組com中我們也能找到Mi——Mk相乘的組合點k2，Mk+1——Mj相乘的組合點k3，……。從數組信息中找到了大規(guī)模問題與小規(guī)模問題的遞歸關系：2021/3/1137

輸出算法

記k1=com[1][n]，則最后一次運算的結合過程是M1*……*Mk1和Mk1+1*……*Mn記k2=com[1][k1]，M1*……*Mk1的結合過程是M1*……*Mk2和Mk2+1*……*Mk1……combine(inti,intj){if(i=j)return;combine(i,com[i][j]);combine(com[i][j]+1,j);print（"M",i,“*M”，com[i][j]）;print（"andM",com[i][j]+1,“*M”，j）;}

上節(jié)下節(jié)2021/3/1138

這一節(jié)問題的設計角度是從遞推思想進行的,設計中只要找出大規(guī)模問題與小規(guī)模問題(子問題)之間的遞推關系,最后一個子問題所得最優(yōu)解就是原問題的最優(yōu)解。

【例4】求兩個字符序列的最長公共字符子序列。

【例5】最長不降子序列。

上節(jié)下節(jié)4.5.4突出遞推的動態(tài)規(guī)劃應用2021/3/1139【例4】求兩個字符序列的最長公共字符子序列。

問題分析

算法設計

算法(遞歸形式)

算法(非遞歸)

上節(jié)下節(jié)2021/3/1140

問題分析若A的長度為n，若B的長度為m，則A的子序列共有：Cn1+Cn2+Cn3+……+Cnn=2n-1B的子序列共有：Cm1+Cm2+Cm3+……+Cmm=2m-1如采用枚舉策略，當m=n時，共進行串比較：Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+……+Cnn*Cnn<22n次，耗時太多,不可取。此問題不可能簡單地分解成幾個獨立的子問題，也不能用分治法來解。所以，我們只能用動態(tài)規(guī)劃的方法去解決。

上節(jié)下節(jié)2021/3/1141

算法設計1．遞推關系分析設A=“a0，a1，…，am-1”，B=“b0，b1，…，bn-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”的一個最長公共子序列。

上節(jié)下節(jié)2021/3/11422．存儲、子問題合并定義c[i][j]為序列a0,a1,…,ai-2”和“b0,b1,…,bj-1”的最長公共子序列的長度，計算c[i][j]可遞歸地表述如下：1）c[i][j]=0

如果i=0或j=0；

2）c[i][j]=c[i-1][j-1]+1如果i,j>0,且a[i-1]=b[j-1]；3）c[i][j]=max(c[i][j-1],c[i-1][j])如果i,j>0,且a[i-1]≠b[j-1]。

上節(jié)下節(jié)2021/3/1143

算法(遞歸形式)intNum=100

char

a[Num],b[Num],str[Num];main()

{intm,n,k;print

(“Enter

two

string”);

input(a,b);m=strlen(a);n=strlen(b),

k=lcs_len(n,m);buile_lcs(k,n,m);print(str);

}

上節(jié)下節(jié)2021/3/1144lcs_len(int

i，j)//計算最優(yōu)值{

if(i=0orj=0)

c[i][j]=0;elseif(a[i-1]=b[j-1])c[i][j]=

lcs_len(i-1，j-1)+1

;elsec[i][j]=max（lcs_len(i，j-1)，lcs_len(i-1，j);}buile_lcs(k,i,j);//構造最長公共子序列{if（i=0orj=0）return;

if（c[i][j]=c[i-1][j]）buile_lcs(k,i-1,j);elseif（c[i][j]=c[i][j-1]）buile_lcs(k,i,j-1);else{str[k]=a[i-1];

buile_lcs(k-1,i-1,j-1);}}

上節(jié)下節(jié)2021/3/1145

算法(非遞歸)n=100

char

a[n],b[n],str[n];lcs_len(char

a[],

char

b[],

int

c[

][

n])//計算最優(yōu)值

{int

m,n,i,j;

print

(“Enter

two

string”);

input(a,b);

m=strlen(a);n=strlen(b);for

(i=0;i<=m;i++)

c[i][0]=0;

for

(i=0;i<=n;i++)

c[0][i]=0;

for

(i=1;i<=m;i++)

for

(j=1;j<=m;j++)

if

(a[i-1]=b[j-1])

c[i][j]=c[i-1][j-1]+1;

else

if

(c[i-1][j]>=c[i][j-1])

c[i][j]=c[i-1][j];

else

c[i][j]=c[i][j-1];

}

2021/3/1146buile_lcs()//構造最長公共子序列

{

int

k,

i=strlen(a),

j=strlen(b);

k=lcs_len();

str[k]=’’;

while

(k>0)

if

(c[i][j]=c[i-1][j])

i=i-1;

else

if

(c[i][j]=c[i][j-1])

j=j-1;

else

{k=k-1;str[k]=a[i-1];

j=j-1;}

}

上節(jié)下節(jié)2021/3/1147【例5】最長不降子序列

設有由n個不相同的整數組成的數列，記為:a(1)、a(2)、……、a(n)且a(i)<>a(j)(i<>j)若存在i1<i2<i3<…<ik且有a(i1)<a(i2)<…<a(ik)，則稱為長度為k的不下降序列。請求出一個數列的最長不下降序列。

算法設計

算法(逆推法)

上節(jié)下節(jié)2021/3/1148

算法設計1.遞推關系

1)對a(n)來說，由于它是最后一個數，所以當從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)開始,此時最長不下降序列應該按下列方法求出:在a(i+1),a(i+2),…,a(n)中，找出一個比a(i)大的且最長的不下降序列，作為它的后繼。

上節(jié)下節(jié)2021/3/1149算法(逆推法)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;}

上節(jié)下節(jié)2.數據結構設計用數組b[i],c[i]分別記錄點i到n的最長的不降子序列的長度和點i后繼接點的編號。2021/3/1150for(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){b[i]=b[p]+1;c[i]=p;}}

max=0;p=0;

for(i=1;i<n;i++)if(b[i]>max){max:=b[i];p:=i;}

print('maxlong=',max);print('resultis:');

while(p<>0)

{print(a[p]);p:=c[p];}

}

上節(jié)下節(jié)2021/3/1151

算法策略和算法是有區(qū)別的,它們是算法設計中的兩個方面，算法策略是面向問題的,算法是面向實現(xiàn)的；但二者又是不可分的,首先是通過算法策略才找出解決問題的算法，其次對于用不同算法求解的問題算法策略是自然不同的。本章共介紹了五種算法策略,它們互相有著一定的差別，適應的問題也有所差異。

上節(jié)下節(jié)4.6算法策略間的比較

2021/3/1152

“貪婪算法”

“遞推法”

“遞歸法”

“枚舉法”

“遞歸回朔法”

“分治法”

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

上節(jié)下節(jié)4.6.1不同算法策略特點小結2021/3/1153

“貪婪算法”這些策略求解的是最簡單的一類問題，或者說是對問題要求最嚴格的算法策略。“貪婪算法”解決這類問題是按一定順序（從前向后或從后向前等）一定的策略，只需考慮當前局部信息就能做出決策，即所謂局部最優(yōu)就是全局最優(yōu)。

上節(jié)下節(jié)2021/3/1154

“遞推法”“遞推法”和貪婪算法一樣也是由當前問題的逐步解決從而得到整個問題的解，只是依賴的是信息間本身的遞推關系，每一步不需要策略參與到算法中，它們更多地用于計算。

上節(jié)下節(jié)2021/3/1155

“遞歸法”

和遞推法類似，遞歸法是利用大問題與其子問題間的遞歸關系來解決問題的。能采用遞歸描述的算法通常有這樣的特征：為求解規(guī)模為N的問題，設法將它分解成規(guī)模較小的問題，然后從這些小問題的解方便地構造出大問題的解，并且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分解成規(guī)模更小的問題，并從這些更小問題的解構造出規(guī)模較大問題的解。特別地，當規(guī)模N=1時，能直接得解。

上節(jié)下節(jié)2021/3/1156

“枚舉法”枚舉法既是一個策略，也是一個算法，也是一個分析問題的手段。枚舉法的求解思路很簡單,就是對所有可能的解逐一嘗試，從而找出問題的真正解。當然這就要求所解的問題可能的解是有限的、固定的，不會產生組合爆炸、容易枚舉的。多用于決策類問題。這類問題都不易進行問題的分解，只能整體來求解。

上節(jié)下節(jié)2021/3/1157

“遞歸回朔法”類似于枚舉法的思想,遞歸回朔法通過遞歸嘗試遍問題各個可能解的通路，發(fā)現(xiàn)此路不通時回朔到上一步繼續(xù)嘗試別的通路。在下一章中對其應用做詳細介紹。

上節(jié)下節(jié)2021/3/1158

“分治法”求解的則是較復雜的問題，這類問題是可以被分解成獨立的子問題來解決的，將兩個或兩個以上的獨立子問題的解“合成”，就得到較大的子問題的解，最后合成為總問題的解。

上節(jié)下節(jié)2021/3/1159

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

動態(tài)規(guī)劃法與貪心法類似，是通過多階段決策過程來解決問題的。但每個階段決策的結果是一個決策結果序列，這個結果序列中最后采用哪一個結果取決于以后每個階段決策，因此稱為“動態(tài)”規(guī)劃法。當然每一次的決策結果序列都必須進行存儲。因此，可以說“動態(tài)規(guī)劃是高效率、高消費的算法”。另一方面，動態(tài)規(guī)劃法與分治法類似，當問題不能分解為獨立的子問題,但又符合最優(yōu)化原理(最優(yōu)子結構性質)時,用動態(tài)規(guī)劃，通過多階段決策過程從逐步找出子問題的最優(yōu)解，從而決策出問題的結果。

上節(jié)下節(jié)2021/3/1160

1.對問題進行分解的算法策略---"分治法"與"動態(tài)規(guī)劃法"2.多階段過程"貪婪算法"、"遞推法"、"遞歸法"和"動態(tài)規(guī)劃法"3.全面逐一嘗試、比較"蠻力法"、"枚舉法"、"遞歸回溯法"4．算法策略的中心思想

上節(jié)下節(jié)4.6.2算法策略間的關聯(lián)

2021/3/11611.對問題進行分解的算法策略---“分治法”與“動態(tài)規(guī)劃法”

“分治法”與“動態(tài)規(guī)劃法”都是遞歸思想的應用之一，是找出大問題與小的子問題之間的關系,直到小的子問題很容易解決，再由小的子問題的解導出大問題的解。區(qū)別在于：

上節(jié)下節(jié)2021/3/1162

分治法所能解決的問題一般具有以下幾個特征：1)該問題的規(guī)?？s小到一定的程度就可以容易地解決；2)該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有。3)利用該問題分解出的子問題的解可以合并為該問題的解;4)該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子問題。

上節(jié)下節(jié)2021/3/1163

第一條特征是絕大多數問題都可以滿足的;第二條特征是應用分治法的前提,它也是大多數問題可以滿足的;第三條特征是關鍵。第四條特征涉及到分治法的效率。動態(tài)規(guī)劃的實質是分治思想和解決冗余。

上節(jié)下節(jié)2021/3/11642．多階段過程“貪婪算法”、“遞推法”、

“遞歸法”和“動態(tài)規(guī)劃法”

多階段過程就是按一定順序(從前向后或從后向前等)一定的策略,逐步解決問題的方法。“貪婪算法”每一步根據策略得到一個結果傳遞到下一步，自頂向下，一步一步地作出貪心選擇。

上節(jié)下節(jié)2021/3/1165

“動態(tài)規(guī)劃法”則根據一定的決策,每一步決策出的不是一個結果，而只是使問題的規(guī)模不斷的縮小，如果決策比較簡單,是一般的算法運算,則可找到不同規(guī)模問題間的關系，使算法演變成“遞推法”、“遞歸法”算法,所以說動態(tài)規(guī)劃更側重算法設計策略，而不是算法?！斑f推法”、“遞歸法”更注重每一步之間的關系,決策的因素較少。“遞推法”根據關系從前向后推,由小規(guī)模的結論,推解出問題的解。“遞歸法”根據關系先從后向前使大問題，轉化為小問題，最后同樣由小規(guī)模結論，推解出問題的解。

上節(jié)下節(jié)2021/3/11663．全面逐一嘗試、比較“蠻力