1.分治法
適用條件：
- 問(wèn)題規(guī)模縮小到一定程度容易求解
- 問(wèn)題可以分解為若干個(gè)規(guī)模較小的相同子問(wèn)題，即問(wèn)題具有最優(yōu)子結(jié)構(gòu)（使用分治法前提）
- 可以利用子問(wèn)題的解合并為該問(wèn)題的解（決定是否使用分治法）
- 各個(gè)子問(wèn)題相互獨(dú)立，即子問(wèn)題之間不包含公共子問(wèn)題（若不滿(mǎn)足，最好使用動(dòng)態(tài)規(guī)劃算法）
基本步驟：
2.動(dòng)態(tài)規(guī)劃算法
適用條件：
- 滿(mǎn)足最優(yōu)性原理，即具有最優(yōu)子結(jié)構(gòu)性質(zhì)（該問(wèn)題最優(yōu)解包含子問(wèn)題最優(yōu)解）
- 重疊子問(wèn)題：可分解為相互關(guān)聯(lián)的若干子問(wèn)題，子問(wèn)題之間不獨(dú)立，子問(wèn)題的解可能在下一決策階段中被使用
設(shè)計(jì)思想：
利用最優(yōu)子結(jié)構(gòu)性質(zhì)，將問(wèn)題劃分為一系列子問(wèn)題，求各子問(wèn)題的最優(yōu)解，然后以自底向上的方式遞歸地從子問(wèn)題的最優(yōu)解構(gòu)造出整個(gè)問(wèn)題的最優(yōu)解。
ps：“填表” ——構(gòu)建數(shù)據(jù)結(jié)構(gòu)，保存子問(wèn)題的最優(yōu)解，以便求整個(gè)問(wèn)題的最優(yōu)解。
設(shè)計(jì)步驟：
（1）劃分子問(wèn)題（分段）：講整個(gè)問(wèn)題劃分為若干個(gè)子問(wèn)題，找到問(wèn)題的狀態(tài)，子問(wèn)題之間具有的重疊關(guān)系。
（2）構(gòu)建狀態(tài)轉(zhuǎn)移方程（分析）：關(guān)聯(lián)的狀態(tài)和狀態(tài)之間相互轉(zhuǎn)換關(guān)系。（動(dòng)態(tài)規(guī)劃的關(guān)鍵）
（3）存儲(chǔ)狀態(tài)的值求解（填表）：設(shè)計(jì)表格（即數(shù)據(jù)結(jié)構(gòu)），以自底向上的方式計(jì)算各個(gè)子問(wèn)題的解并填表保存，實(shí)現(xiàn)動(dòng)態(tài)規(guī)劃過(guò)程。
注：判斷問(wèn)題是否使用動(dòng)態(tài)規(guī)劃算法，一定要分析問(wèn)題滿(mǎn)足最優(yōu)性原理
分析問(wèn)題是否滿(mǎn)足最優(yōu)性原理，一般用反證法
- 假設(shè)由問(wèn)題的最優(yōu)解導(dǎo)出的子問(wèn)題的解不是最優(yōu)的；
- 證明在這個(gè)假設(shè)下可構(gòu)造出比原問(wèn)題最優(yōu)解更好的解，從而導(dǎo)致矛盾。
例：
（1）多路段圖問(wèn)題
（2） 旅行商問(wèn)題（TSP問(wèn)題）
ps：動(dòng)態(tài)規(guī)劃算法例題：
1.最長(zhǎng)公共子序列（LCS）
滿(mǎn)足最優(yōu)性原理--整個(gè)問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解
證明：若X=（x1,x2.x3....xm),Y=(y1,y2,y3.....yn),且設(shè)z=(z1,z2,z3...zk)為X，Y的最長(zhǎng)公共子序列，則：
（1）若xm=yn,則zk=xm=yn，且（z1,z2,z3...z(k-1))是（x1，x2...x(m-1))和（y1，y2...y(n-1))的最長(zhǎng)公共子序列；
（2）若xm！=yn且xk！=xm，則（z1,z2,z3...zk)是（x1，x2...x(m-1))和（y1，y2...yn)的一個(gè)最長(zhǎng)公共子序列；
（3）若xm！=yn且zk！=yn，則（z1,z2,z3...zk)是（x1，x2...xm)和（y1，y2...y（n-1）)的一個(gè)最長(zhǎng)公共子序列；
綜上，最長(zhǎng)公共子序列z包含序列X，Y的所有前綴的最長(zhǎng)公共子序列。故最長(zhǎng)公共子序列問(wèn)題滿(mǎn)足最優(yōu)性原理。
步驟一：劃分子問(wèn)題（分段）
設(shè)LCS（（x1,x2...xi),(y1,y2...yj))為序列X=（x1,x2...xi)和Y=(y1,y2...yj)的最長(zhǎng)公共子序列。
情況1：xi=yj
LCS（（x1,x2...xi),(y1,y2...yj)) = LCS（（x1,x2...x（i-1）),(y1,y2...y（j-1）)) +xi(或yj)
情況2：xi！=yj
LCS（（x1,x2...xi),(y1,y2...yj)) =
max（ LCS（（x1,x2...x（i-1）),(y1,y2...yj) ， LCS（（x1,x2...xi),(y1,y2...y（j-1）)) ）
故問(wèn)題共有m*n個(gè)子問(wèn)題。
步驟二：構(gòu)建狀態(tài)轉(zhuǎn)移方程（分析）
定義二數(shù)組L，L[i][j]表示 LCS（（x1,x2...xi),(y1,y2...yj)) 的長(zhǎng)度(i=1,2,3...m,j=1,2,3...n)
每考慮一個(gè)xi或yj都為動(dòng)態(tài)規(guī)劃的一個(gè)階段。
情況1：xi=yj????????? L[i][j]=L[i-1][j-1]+1
情況2：xi！=yj????? L[i][j] =max(L[i-1][j],L[i][j-1])
則狀態(tài)轉(zhuǎn)移方程為：
?顯然：
初始子問(wèn)題：X，Y中至少有一個(gè)空序列，即：L[0][j]=L[i][0]=0,i=1,2...m,j=1,2...n
L[i][j]是子問(wèn)題最優(yōu)解，L[m][n]是整個(gè)問(wèn)題最優(yōu)解。
?
步驟三：存儲(chǔ)狀態(tài)的值求解（填表）
基本思想：自底向上計(jì)算LCS的長(zhǎng)度
填寫(xiě)數(shù)組L的值：
算法設(shè)計(jì)：
為了得到序列（x1,x2,x3...xm)和(y1,y2,y3...yn)最長(zhǎng)公共子序列，另設(shè)數(shù)組S，其中S[i][j]表示在計(jì)算L[i][j]過(guò)程中的搜索狀態(tài)，并且有：
故：
①若S[i][j]=1，下一個(gè)回溯方向是S[i-1][j-1],即i=i-1，j=j-1；
②若S[i][j]=2,下一個(gè)回溯方向是S[i][j-1],即j=j-1；
③若S[i][j]=3，下一個(gè)回溯方向是S[i-1][j],即i=i-1；
算法：
算法：最長(zhǎng)公共子序列的動(dòng)態(tài)規(guī)化算法 輸入：序列X，Y 輸出：最長(zhǎng)公共子序列長(zhǎng)度和最長(zhǎng)公共子系列z 1.for(i=0;i<=m;i++) L[i][0] = 0; for(j=1;j<=n;j++) L[0][j] = 0; 2.for(i=1;i<=m;i++) for(j=1;j<=n;j++) if(X[i]==Y[j]) {L[i][j] = L[i-1][j-1]+1; S[i][j]=1;} else { if(L[i][j-1]>=L[i-1][j]) {L[i][j] = L[i][j-1]; S[i][j]=2;} else {L[i][j]=L[i-1][j]; S[i][j]=3;} } 3.i=m,j=n,k=L[m][n]; 4.while(i>0&&j>0) { if(S[i][j]==1) {z[k]=X[i]; i--;j--;} else if(S[i][j]==2) j--; else i--; } 5.輸出L[m][n]和z 時(shí)間復(fù)雜度：O（m*n）
2.最大子段和問(wèn)題
問(wèn)題：給定n個(gè)數(shù)（可以為負(fù)數(shù)）的序列（a1,a2,...an)，求
①子問(wèn)題界定：前邊界1，后邊界i，C[i]是A[1...i]中包含元素A[i]的向前連續(xù)延伸的最大子段和
②構(gòu)建狀態(tài)轉(zhuǎn)移方程：
C[i]=max{C[i-1]+A[i],A[i]},i=2,3,...n
若A[1]>0?? C[1]=A[1]
否則????????? C[1]=0
故：OPT（A）=max{C[i]}
③偽碼：
算法：MaxSum(A,n) 輸入：數(shù)組A[n] 輸出：最大字段和sum和子段最后位置c 1.max <- 0 if A[1]>0 then C[1]:=A[1]; else C[1]:=0; 2.for i <- 2 to n do 3. if C[i-1] > 0 then C[i] := C[i-1]+A[i] else C[i] := A[i] 4.max = 0; 5.for i <- 1 to n do if max < C[i] then max := C[i] 6.輸出max和i 時(shí)間復(fù)雜度：O(n)
3.矩陣連乘問(wèn)題
問(wèn)題：給定n個(gè)矩陣{A1,A2...An}，其中Ai與Ai+1是可乘的，確定計(jì)算矩陣連乘計(jì)算順序，使得依此次序矩陣連乘積需要的數(shù)乘次數(shù)最少。輸入數(shù)據(jù)為矩陣的個(gè)數(shù)和每個(gè)矩陣的規(guī)模，輸出結(jié)果為計(jì)算矩陣連乘積的計(jì)算次序和最少數(shù)乘次數(shù)。
最優(yōu)性原理：
為方便起見(jiàn)，將連乘積AiAi+1...Aj簡(jiǎn)記為A[i:j]，其中Ai的維度記為pi-1×pi。
計(jì)算A[i:j]最優(yōu)次序所包含的計(jì)算矩陣子鏈A[i:k],A[k+1:j]的次序也是最優(yōu)的。即該問(wèn)題的最優(yōu)解包含子問(wèn)題的最優(yōu)解，滿(mǎn)足最優(yōu)性原理。
步驟一：劃分子問(wèn)題
問(wèn)題目的求解A[1:n]的最優(yōu)解，則可將問(wèn)題劃分為求若干個(gè)A[i:j]的最優(yōu)計(jì)算次序。
考察A[i:j]的最優(yōu)計(jì)算次序：設(shè)這個(gè)計(jì)算次序在矩陣Ak和Ak+1之間將矩陣鏈斷開(kāi)，i<=k<j,則其相應(yīng)的括號(hào)方式為：（AiAi+1..Ak)(Ak+1...Aj)。則A[i:k]的計(jì)算量加上A[k+1,j]的計(jì)算量，再加上A[i:k]和A[k+1,j]相乘的計(jì)算量。
步驟二：建立狀態(tài)轉(zhuǎn)移方程
設(shè)計(jì)算A[i:j]，1<=k<j，所需要的最少數(shù)乘次數(shù)為dp[i,j],原問(wèn)題的最優(yōu)值dp[1,n].
①當(dāng)i=j時(shí)，dp[i,j]=0②當(dāng)i<j時(shí)，dp[i,j]=min{dp[i,k]+dp[k+1,j]+pi-1pkpj
步驟三：存儲(chǔ)狀態(tài)的值求解
在程序中，dp的實(shí)現(xiàn)是一個(gè)二維數(shù)組，也就是一張二維表，為了方便計(jì)算，dp的下標(biāo)從1開(kāi)始。要計(jì)算 A [ 1 : n ]的最少乘次，本質(zhì)上是求dp[1][n]的值，也就是二維表表右上角的值.
例如，連乘矩陣個(gè)數(shù)為6，維數(shù)分別為：
A 1 ( 30 × 35 ) ；
A 2 ( 35 × 15 ) ；
A 3 ( 15 × 5 ) ；
A 4 ( 5 × 10 ) ；
A 5 ( 10 × 20 ) ；
A 6 ( 20 × 25 ) ；?根據(jù)遞歸公式，對(duì)角線的值為0。其他值需要根據(jù)于斷開(kāi)位置 k k k的值來(lái)得到， k ∈ [ i , j ) k \in [i,j) k∈[i,j)，我們要遍歷所有 k k k，就要訪問(wèn)所求值的所有同一行左邊的值和同一列下方的值。因此，在代碼中我們可以使用自底向上、從左到右的計(jì)算順序來(lái)依次填充，最終得到右上角的值。如：
dp[2][5]=min{dp[2][2]+dp[3][5]+p1p2p5,dp[2][3]+dp[4][5]+p1p3p5,dp[2][4]+dp[5][5]+p1p4p5}文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-467462.html
關(guān)鍵代碼：文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-467462.html
for(i=1;i<=n;i++) { for(j=i;j<=n;j++) { if(i==j) dp[i][j]=0; else { for(k=i;k<j;k++) { temp=dp[i][k]+dp[k+1][j]+p[i-1]*p[k]*p[j]; if (temp < dp[i][j]) { dp[i]j]=temp; S[i][j]=k;//記錄分割處 } } } } }
到了這里，關(guān)于算法分析與設(shè)計(jì)---分治+動(dòng)態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
