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

1、第第 四四 章章 基本的算法策略基本的算法策略 4.5 4.5 動態(tài)規(guī)劃動態(tài)規(guī)劃 4.5.1 4.5.1 認(rèn)識動態(tài)規(guī)劃認(rèn)識動態(tài)規(guī)劃 4.5.2 4.5.2 算法框架算法框架 4.5.3 4.5.3 突出階段性的動態(tài)規(guī)劃應(yīng)用突出階段性的動態(tài)規(guī)劃應(yīng)用 4.5.4 4.5.4 突出遞推的動態(tài)規(guī)劃應(yīng)用突出遞推的動態(tài)規(guī)劃應(yīng)用 在動態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是在動態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是 全面考慮不同的情況分別進(jìn)行決策全面考慮不同的情況分別進(jìn)行決策, , 并通過多階段決策來最并通過多階段決策來最 終解決問題。在各個階段采取決策后終解決問題。在各個階段采取決策后, ,

2、 會不斷決策出新的數(shù)會不斷決策出新的數(shù) 據(jù)據(jù), ,直到找到最優(yōu)解直到找到最優(yōu)解. .每次決策依賴于當(dāng)前狀態(tài)每次決策依賴于當(dāng)前狀態(tài), , 又隨即引起又隨即引起 狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，狀態(tài)的轉(zhuǎn)移。一個決策序列就是在變化的狀態(tài)中產(chǎn)生出來的， 故有故有“動態(tài)動態(tài)”的含義。所以，這種多階段決策最優(yōu)化的解決的含義。所以，這種多階段決策最優(yōu)化的解決 問題的過程稱為問題的過程稱為動態(tài)規(guī)劃動態(tài)規(guī)劃。 上節(jié)上節(jié) 下節(jié)下節(jié) 4.5 4.5 動態(tài)規(guī)劃動態(tài)規(guī)劃 我們通過一個簡單的例子來說明動態(tài)規(guī)劃的多階段決策與 貪婪算法有什么區(qū)別。 【例【例1】 數(shù)塔問題數(shù)塔問題 上節(jié) 下節(jié) 4.5.1

3、 認(rèn)識動態(tài)規(guī)劃 【例【例1 1】數(shù)塔問題數(shù)塔問題 有形如圖4-11所示的一個數(shù)塔，從頂部出發(fā)，在每一結(jié)點 可以選擇向左走或是向右走，一直走到底層，要求找出一條路 徑，使路徑上的數(shù)值和最大。 問題分析 算法設(shè)計 算法 小結(jié) 問題分析問題分析 這個問題用貪婪算法有可能會找不到真正的最大和。 以圖4-11為例就是如此。用貪婪的策略，則路徑和分別為： 9+15+8+9+10=51 （自上而下）， 19+2+10+12+9=52（自下而上）。 都得不到最優(yōu)解，真正的最大和是： 9+12+10+18+10=59。 在知道數(shù)塔的全貌的前提下，可以用枚舉法或下一章將學(xué) 習(xí)的搜索算法來完成。 上節(jié) 下節(jié) 算法設(shè)

4、計算法設(shè)計 動態(tài)規(guī)劃設(shè)計過程如下：動態(tài)規(guī)劃設(shè)計過程如下： 1.1.階段劃分：階段劃分： 第一步對于第五層的數(shù)據(jù)，我們做如下五次決策：第一步對于第五層的數(shù)據(jù)，我們做如下五次決策： 對經(jīng)過第四層對經(jīng)過第四層2 2的路徑選擇第五層的的路徑選擇第五層的1919， 對經(jīng)過第四層對經(jīng)過第四層1818的路徑選擇第五層的的路徑選擇第五層的1010， 對經(jīng)過第四層對經(jīng)過第四層9 9的路徑也選擇第五層的的路徑也選擇第五層的1010， 對經(jīng)過第四層對經(jīng)過第四層5 5的路徑選擇第五層的的路徑選擇第五層的1616。 上節(jié)上節(jié) 下節(jié)下節(jié) 以上的決策結(jié)果將五階數(shù)塔問題變?yōu)橐陨系臎Q策結(jié)果將五階數(shù)塔問題變?yōu)? 4階子問題，遞推

5、階子問題，遞推 出第四層與第五層的和為出第四層與第五層的和為: : 21(2+19),28(18+10),19(9+10),21(5+16) 21(2+19),28(18+10),19(9+10),21(5+16)。 用同樣的方法還可以將用同樣的方法還可以將4 4階數(shù)塔問題階數(shù)塔問題, ,變?yōu)樽優(yōu)? 3階數(shù)塔問題。階數(shù)塔問題。 最后得到的最后得到的1 1階數(shù)塔問題，就是整個問題的最優(yōu)解。階數(shù)塔問題，就是整個問題的最優(yōu)解。 上節(jié)上節(jié) 下節(jié)下節(jié) 2 2存儲、求解：存儲、求解： 1) 1) 原始信息存儲原始信息存儲 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個整型原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個

6、整型 變量變量n n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組datadata，存儲成如，存儲成如 下的下三角陣下的下三角陣: : 9 9 12 15 12 15 10 6 8 10 6 8 2 18 9 5 2 18 9 5 19 7 10 4 16 19 7 10 4 16 上節(jié)上節(jié) 下節(jié)下節(jié) 2) 2) 動態(tài)規(guī)劃過程存儲動態(tài)規(guī)劃過程存儲 必需用二維數(shù)組必需用二維數(shù)組a a存儲各階段的決策結(jié)果。二維數(shù)組存儲各階段的決策結(jié)果。二維數(shù)組a a 的存儲內(nèi)容如下：的存儲內(nèi)容如下： dnj=datanj j=1,2,dnj=datanj j=1,2,n,n； i=n-1,n-2,i=n

7、-1,n-2,1 1，j=1,2,j=1,2,i,i；時；時 dij=max(di+1jdij=max(di+1j，di+1j+1)+dataijdi+1j+1)+dataij 最后最后a11a11存儲的就是問題的結(jié)果。存儲的就是問題的結(jié)果。 上節(jié)上節(jié) 下節(jié)下節(jié) 3) 3) 最優(yōu)解路徑求解及存儲最優(yōu)解路徑求解及存儲 僅有數(shù)組僅有數(shù)組datadata和數(shù)組和數(shù)組a a可以找到最優(yōu)解的路徑，可以找到最優(yōu)解的路徑， 但需要但需要 自頂向下比較數(shù)組自頂向下比較數(shù)組datadata和數(shù)組和數(shù)組a a是可以找到。如圖是可以找到。如圖4.5.24.5.2求解求解 和輸出過程如下：和輸出過程如下： 上節(jié)上節(jié)

8、下節(jié)下節(jié) 輸出輸出a119a119 b=d11-data11=59-9=50 b=d11-data11=59-9=50 b b與與d21,d22 d21,d22 比較比較 b b與與d21d21相等輸出相等輸出data2112data2112 b=d21-data21=50-12=38 b=d21-data21=50-12=38 b b與與d31,d32 d31,d32 比較比較 b b與與d31d31相等輸出相等輸出data3110data3110 b=a31-data31=38-10=28 b=a31-data31=38-10=28 b b與與d41,d42 d41,d42 比較比較 b

9、b與與d42d42相等輸出相等輸出data4218data4218 b=d42-data42=28-18=10 b b=d42-data42=28-18=10 b與與d52,d53 d52,d53 比較比較 b b與與d53d53相等輸出相等輸出data5310“data5310“ 上節(jié)上節(jié) 下節(jié)下節(jié) 數(shù)組數(shù)組datadata 數(shù)組數(shù)組d d 9 59 9 59 12 15 50 49 12 15 50 49 10 6 8 38 34 29 10 6 8 38 34 29 2 18 9 5 21 28 19 21 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 1

10、0 4 16 19 7 10 4 16 19 7 10 4 16 圖圖4-12 4-12 數(shù)塔及動態(tài)規(guī)劃過程數(shù)據(jù)數(shù)塔及動態(tài)規(guī)劃過程數(shù)據(jù) 上節(jié)上節(jié) 下節(jié)下節(jié) 為了設(shè)計簡潔的算法，我們最后用三維數(shù)組為了設(shè)計簡潔的算法，我們最后用三維數(shù)組a50503a50503 存儲以上確定的三個數(shù)組的信息。存儲以上確定的三個數(shù)組的信息。 a50501a50501代替數(shù)組代替數(shù)組datadata， a50502a50502代替數(shù)組代替數(shù)組d, d, a50503 a50503記錄解路徑。記錄解路徑。 上節(jié)上節(jié) 下節(jié)下節(jié) 數(shù)塔問題的算法數(shù)塔問題的算法 main( )main( ) int int a50503,i,j

11、,n; a50503,i,j,n; print( please input the number of rows:); print( please input the number of rows:); input(n); input(n); for( i=1 ;i=n;i+)for( i=1 ;i=1;i-)for (i=n-1 ; i=1;i-) for (j=1 ;j= i ;j+) for (j=1 ;j= i ;j+) if (ai+1j2ai+1j+12) if (ai+1j2ai+1j+12) aij2=aij2+ai+1j2; aij2=aij2+ai+1j2; aij3=0;

12、 aij3=0; elseelse aij2=aij2+ai+1j+12; aij2=aij2+ai+1j+12; aij3=1; aij3=1; print(max=,a112);print(max=,a112); j=1;j=1; for( i=1 ;i= n-1;i+)for( i=1 ;i); print(aij1,-); j=j+aij3; j=j+aij3; print (anj1);print (anj1); 上節(jié)上節(jié) 下節(jié)下節(jié) 從例子中可以看到：從例子中可以看到： 動態(tài)規(guī)劃動態(tài)規(guī)劃= =貪婪策略貪婪策略+ +遞推遞推( (降階降階)+)+存儲遞推結(jié)果存儲遞推結(jié)果 貪婪策略、遞推

13、算法都是在貪婪策略、遞推算法都是在“線性線性”地解決問題，而動態(tài)地解決問題，而動態(tài) 規(guī)劃則是全面分階段地解決問題?？梢酝ㄋ椎卣f動態(tài)規(guī)劃是規(guī)劃則是全面分階段地解決問題。可以通俗地說動態(tài)規(guī)劃是 “帶決策的多階段、多方位的遞推算法帶決策的多階段、多方位的遞推算法”。 上節(jié)上節(jié) 下節(jié)下節(jié) 1.適合動態(tài)規(guī)劃的問題特征 動態(tài)規(guī)劃算法的問題及決策應(yīng)該具有三個性質(zhì)：最優(yōu) 化原理、無后向性、子問題重疊性質(zhì)。 1) 最優(yōu)化原理(或稱為最佳原則、最優(yōu)子結(jié)構(gòu))。 2) 無后向性(無后效性)。 3) 有重疊子問題。 上節(jié) 下節(jié) 4.5.2 算法框架 2. 動態(tài)規(guī)劃的基本思想 動態(tài)規(guī)劃方法的基本思想是，把求解的問題分成許

14、多階 段或多個子問題，然后按順序求解各子問題。最后一個子問 題就是初始問題的解。 由于動態(tài)規(guī)劃的問題有重疊子問題的特點，為了減少重 復(fù)計算，對每一個子問題只解一次，將其不同階段的不同狀 態(tài)保存在一個二維數(shù)組中。 上節(jié) 下節(jié) 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)解。 上節(jié) 下節(jié)

15、 4. 標(biāo)準(zhǔn)動態(tài)規(guī)劃的基本框架 for( j=1 ;j=1;i=i-1) /其它其它n-1個階段個階段 for (j=1 ;j=f(i) ;j=j+1)/ f(i)與與 i有關(guān)的表達(dá)式有關(guān)的表達(dá)式 xij=max(或或min)g(xi-1j1j2)， g(xi-1jkjk+1)； t=g(x1j1j2); /由最優(yōu)解求解最優(yōu)解的方案由最優(yōu)解求解最優(yōu)解的方案 print(x1j1); for( i=2 ;i=f(i) ;j=j+1) if(t= xiji) break; 上節(jié) 下節(jié) 【例【例2 2】 資源分配問題。 【例【例3 3】 n個矩陣連乘的問題。 上節(jié) 下節(jié) 4.5.3 突出階段性的動態(tài)

16、規(guī)劃應(yīng)用 【例【例2 2】資源分配問題。資源分配問題。 設(shè)有資源設(shè)有資源a,a,分配給分配給n n個項目個項目,gi(x,gi(x) )為第為第i i個項目分得資源個項目分得資源x x 所得到的利潤。求總利潤最大的資源分配方案，也就是解下所得到的利潤。求總利潤最大的資源分配方案，也就是解下 列問題：列問題： max z=g1(x1)+ g2(x2)+max z=g1(x1)+ g2(x2)+gn(xngn(xn) ) x1+xx2+x3+ x1+xx2+x3+xnxn=a, xi0,i=1=a, xi0,i=1，2,3,2,3,n,n 函數(shù)函數(shù)gi(xgi(x) )以數(shù)據(jù)表的形式給出以數(shù)據(jù)表的

17、形式給出. . 例如：現(xiàn)有例如：現(xiàn)有7 7萬元投資到萬元投資到A A，B B，C C 三個項目，利潤見表三個項目，利潤見表, ,求問求問 題總利潤最大的資源分配方案。題總利潤最大的資源分配方案。 上節(jié)上節(jié) 下節(jié)下節(jié) 算法設(shè)計算法設(shè)計 1 1階段劃分及決策階段劃分及決策 比較直觀的階段劃分就是比較直觀的階段劃分就是逐步逐步考慮考慮每一個項目每一個項目在不在不 同投資額下的利潤情況。同投資額下的利潤情況。 3. 3. 數(shù)據(jù)結(jié)構(gòu)設(shè)計：數(shù)據(jù)結(jié)構(gòu)設(shè)計： 1) 1) 開辟一維數(shù)組開辟一維數(shù)組q q來存儲原始數(shù)據(jù)。來存儲原始數(shù)據(jù)。 2) 2) 另開辟一維數(shù)組另開辟一維數(shù)組f f存儲當(dāng)前最大收益情況。存儲當(dāng)前

18、最大收益情況。 3) 3) 開辟記錄中間結(jié)果的一維數(shù)組數(shù)組開辟記錄中間結(jié)果的一維數(shù)組數(shù)組temptemp，記錄正在計，記錄正在計 算的最大收益。算的最大收益。 4) 4) 開辟二維數(shù)組開辟二維數(shù)組a a。 5) 5) 數(shù)組數(shù)組gaingain存儲第存儲第i i個工程投資數(shù)的最后結(jié)果。個工程投資數(shù)的最后結(jié)果。 上節(jié)上節(jié) 下節(jié)下節(jié) 對于一般問題設(shè)計對于一般問題設(shè)計算法算法如下如下： main( ) main( ) int int i,j,k,m,n,rest; i,j,k,m,n,rest; int a100100 int a100100，gain100;gain100; float q100,f

19、100,temp100; float q100,f100,temp100; print(“How mang print(“How mang item? ”); input (m); item? ”); input (m); print(“How mang print(“How mang money? ”); input (n); money? ”); input (n); print(“input gain table:”); print(“input gain table:”); for( j=0;j= n;j+) for( j=0;j= n;j+) input(qj); fj=qj; in

20、put(qj); fj=qj; for( j=0;j= n;j+) for( j=0;j= n;j+) a1,j=j; a1,j=j; 上節(jié)上節(jié) 下節(jié)下節(jié) for( k=2;k=m;k+)for( k=2;k=m;k+) for( j=0;j= n;j+) for( j=0;j= n;j+) tempj=qj; input(qj); akj=0; tempj=qj; input(qj); akj=0; for( j=0 ;j= n;j+) for( j=0 ;j= n;j+) for( i=0 ;i=j;i+)for( i=0 ;itempjfj-i+qitempj） tempj=fj-i+q

21、i; ak,j=i; tempj=fj-i+qi; ak,j=i; for(j=0;j= n;j+) for(j=0;j=1;i-) for(i=m;i=1;i-) gaini=airest; rest=rest-gaini; gaini=airest; rest=rest-gaini; for(i=1;i=m;i+) print(gaini,” ”); for(i=1;i=m;i+) print(gaini,” ”); print(fn); print(fn); 【例3】n個矩陣連乘的問題。 問題分析 算法設(shè)計 算法1(遞歸算法) 算法1說明 算法2(遞歸算法) 算法3(非遞歸算法) 輸出算

22、法 上節(jié) 下節(jié) 問題分析問題分析 多個矩陣連乘多個矩陣連乘運算是滿足結(jié)合律的。運算是滿足結(jié)合律的。 例例: : M15 M15* *20 20 * * M220 M220* *50 50 * * M350 M350* *1 1 * * M41 M41* *100100分別按分別按 (M1(M1* *M2)M2)* *M3)M3)* *M4M4，M1M1* *(M2(M2* *(M3(M3* *M4)M4)，(M1(M1* *(M2(M2* *M3)M3)* *M4M4 的次序相乘的次序相乘, ,各需進(jìn)行各需進(jìn)行 5750, 115000, 16005750, 115000, 1600次乘法。次

23、乘法。 這個問題要用這個問題要用“動態(tài)規(guī)劃動態(tài)規(guī)劃”算法來完成算法來完成: : 首先首先, ,從兩個矩陣相乘的情況開始；從兩個矩陣相乘的情況開始； 然后然后, ,嘗試三個矩陣相乘的情況；嘗試三個矩陣相乘的情況； 最后最后, ,等到等到n n個矩陣相乘所用的最少的乘法次數(shù)及結(jié)合方式。個矩陣相乘所用的最少的乘法次數(shù)及結(jié)合方式。 上節(jié)上節(jié) 下節(jié)下節(jié) 算法設(shè)計算法設(shè)計 1. 1. 階段劃分階段劃分 1 1）初始狀態(tài)為一個矩陣相乘的計算量為）初始狀態(tài)為一個矩陣相乘的計算量為0;0; 2 2）第二階段）第二階段, ,計算兩個相鄰矩陣相乘的計算量計算兩個相鄰矩陣相乘的計算量, , 共共n-1n-1組組 3

24、3）第三階段）第三階段, ,計算兩個相鄰矩陣相乘的計算量計算兩個相鄰矩陣相乘的計算量, , 共共n-2n-2組組 4 4）最后一個階段）最后一個階段, ,是是n n個相鄰矩陣相乘的計算量個相鄰矩陣相乘的計算量, ,共共1 1組組, , 是問題解。是問題解。 上節(jié)上節(jié) 下節(jié)下節(jié) 2. 2. 階段決策階段決策 一般地，計算一般地，計算M1M1* *M2M2* *M3M3* * *MnMn 其中其中M1M1，M2M2，,Mi,Mi分別是分別是 r1r1* *r2r2，r2r2* *r3r3，,ri,ri* *ri+1ri+1階矩陣，階矩陣，i=1,2,3,i=1,2,3,n n。 設(shè)設(shè)mi,jmi,

25、j是計算是計算MiMi* *Mi+1Mi+1* *MjMj的最少乘法次數(shù)的最少乘法次數(shù)(1ijn),(1ijn),對對 mi,jmi,j有公式：有公式： 0 0 當(dāng)當(dāng)i=ji=j時時 ri-1ri-1* *riri* *ri+1 ri+1 當(dāng)當(dāng)j=i+1j=i+1時時 min(mi,k+mk+1,j+rirk+1rj+1) ikj min(mi,k+mk+1,j+rirk+1rj+1) ikj 當(dāng)當(dāng)ijij時時 以上動態(tài)規(guī)劃方法是按以上動態(tài)規(guī)劃方法是按s=0,1,2,3,.,n-1s=0,1,2,3,.,n-1的順序計算的順序計算mi,i+smi,i+s的。的。 3.3.記錄最佳期方案記錄最佳

26、期方案 用二維矩陣用二維矩陣comij(ncomij(n* *n)n)來存儲使來存儲使mijmij為最小值時的為最小值時的 k k 值。值。 上節(jié)上節(jié) 下節(jié)下節(jié) 算法算法1 1( (遞歸算法遞歸算法) ) int r100,com100100; main（ ） int n,i; print(“How mang matrixes?”); input (n); peint(“How size every matrixe?”); for (i=1;i=n+1;i+) input (ri); print (“The least calculate quantity：”, course (1,n); f

27、or (i=1;i=n;i+) print(“換行符”); for (j=1;j=n;j+) print(comij); 上節(jié) 下節(jié) int course(int i, int j) int u,t; if (i=j) return 0; if (i=j-1) comii+1=i; return（ ri*ri+1*rr+2）; u= course(i,i) + course(i+1,j)+ ri*ri+1*rj+1; comij = i; for (int k = i+1; k j; k+) t = course(i,k) + course(k+1,j)+ri*rk+1*rj+1; if (t

28、u) u= t; comij = k; return u; 上節(jié) 下節(jié) 算法算法1 1說明說明 以上的遞歸算法雖然解決了問題，但效率很低，有子問題 重疊，n=4時的遞歸過程如下圖： 上節(jié) 下節(jié) 算法算法2 2( (改進(jìn)后遞歸算法改進(jìn)后遞歸算法) ) int m100100,com100100,r100; matrix2（ ） int n,; print(“How mang matrixes?”); input (n); print(“How size every matrixe?”); for (i=1;i=n+1;i+) input (ri); for (i=1;i=n;i+) /初始化化數(shù)

29、組初始化化數(shù)組com和和m。/ for (j=1;j=n;j+) comij=0; mij=0; course (1,n)； print (“The least calculate quantity：”m1n); for (i=1;i=n;i+) print(“換行符換行符”); for (j=1;j0） return mij; if(i=j) return 0; if(i=j-1) comii+1=i; mij= ri*ri+1*ri+2; return mij; int u= course (i,i)+ course (i+1,j)+ri*ri+1*rj+1; comij=i ; for

30、(int k=i+1; kj;k+) int t= course (i,k)+ course (k+1,j)+ri*rk+1*rj+1; if (tu) u=t ; comij=k; mij=u; return u; 上節(jié) 下節(jié) 算法算法3 3( (非遞歸算法非遞歸算法) ) main（ ） int n,r100,m100100,com100100; peint(“How mang matrixes?”); input (n); peint(“How size every matrixe?”); for (i=1;i=n+1;i+) input (ri); for (i=1;i=n;i+) /

31、初始化化數(shù)組com和m。/ for (j=1;j=n;j+) comij=0; for (i=1;in;i+) mii=0; s=0 mii+1= ri*ri+1*ri+2; s=1 comii+1 = i+1; 上節(jié) 下節(jié) mnn= 0; for ( s =2; s=n-1; s+) /動態(tài)規(guī)劃過程動態(tài)規(guī)劃過程/ for (i=1;in-s+1;i+) j=i+s; mij =mii +mi+1j + ri*ri+1*rj+1; comij = i; for (k=i+1;kj;k+) t=mik+mk+1j+ ri*rk+1*rj+1; if (t mij) mij = t; comij=

32、 k; print (“The least calculate quantity：”m1n); for (i=1;i=n;i+) print(“換行符換行符”); for (j=1;j=n;j+) print(comij); 上節(jié) 下節(jié) 輸出部分的算法設(shè)計 以上算法中關(guān)于矩陣相乘的結(jié)合方式，只是簡單的輸出了數(shù)組 com的內(nèi)容，不容易直觀地被利用，還需要繼續(xù)進(jìn)行必要的人工 處理，才能真正找到矩陣相乘的結(jié)合方式。怎么樣更直觀、合理 地輸出結(jié)合過程？即算法的輸出能使用戶直接了解計算矩陣的過 程。 首先看一下com數(shù)組存儲的信息意義，它是一個二維數(shù)組，元 素comij存儲的是MiMj相乘的組合點k1，

33、也就是說： Mi*Mi+1*Mj是由 Mi*Mi+1*Mk和Mk+1*Mj 同樣，在數(shù)組com中我們也能找到MiMk相乘的組合點k2， Mk+1Mj相乘的組合點k3，。 從數(shù)組信息中找到了大規(guī)模問題與小規(guī)模問題的遞歸關(guān)系： 輸出算法輸出算法 記記k1=com1nk1=com1n，則最后一次運算的結(jié)合過程是，則最后一次運算的結(jié)合過程是 M1M1* * *Mk1Mk1和和Mk1+1Mk1+1* * *MnMn 記記k2=com1k1k2=com1k1，M1M1* * *Mk1Mk1的結(jié)合過程是的結(jié)合過程是 M1M1* * *Mk2Mk2和和Mk2+1Mk2+1* * *Mk1Mk1 combine

34、(int i, int j) if ( i=j) return; combine (i, comij); combine (comij+1, j); print（M,i ,“*M”，comij）; print（ and M,comij+1, “*M”，j ）; 上節(jié) 下節(jié) 這一節(jié)問題的這一節(jié)問題的設(shè)計角度是從遞推思想進(jìn)行設(shè)計角度是從遞推思想進(jìn)行的的, ,設(shè)計中只要找設(shè)計中只要找 出大規(guī)模問題與小規(guī)模問題出大規(guī)模問題與小規(guī)模問題( (子問題子問題) )之間的遞推關(guān)系之間的遞推關(guān)系, ,最后一個最后一個 子問題所得最優(yōu)解就是原問題的最優(yōu)解。子問題所得最優(yōu)解就是原問題的最優(yōu)解。 【例【例4 4】求兩

35、個字符序列的最長公共字符子序列求兩個字符序列的最長公共字符子序列。 【例【例5 5】最長不降子序列最長不降子序列。 上節(jié)上節(jié) 下節(jié)下節(jié) 4.5.4 4.5.4 突出遞推的動態(tài)規(guī)劃應(yīng)用突出遞推的動態(tài)規(guī)劃應(yīng)用 【例【例4】求兩個字符序列的最長公共字符子序 列。 問題分析 算法設(shè)計 算法(遞歸形式) 算法(非遞歸) 上節(jié) 下節(jié) 問題分析問題分析 若若A A的長度為的長度為n n，若，若B B的長度為的長度為m m，則，則 A A的子序列共有：的子序列共有： Cn1+Cn2+ Cn3+Cn1+Cn2+ Cn3+Cnn+Cnn=2n-1=2n-1 B B的子序列共有：的子序列共有： Cm1+Cm2+ C

36、m3+Cm1+Cm2+ Cm3+Cmm+Cmm=2m-1=2m-1 如采用枚舉策略，當(dāng)如采用枚舉策略，當(dāng)m=nm=n時，共進(jìn)行串比較：時，共進(jìn)行串比較： Cn1Cn1* *Cm1+Cn2Cm1+Cn2* *Cm2+Cn3Cm2+Cn3* *Cm3+Cm3+Cnn+Cnn* *CnnCnn22n 0,i,j0,且且ai-1=bj-1ai-1=bj-1； 3 3）cij=max(cij-1,ci-1j)cij=max(cij-1,ci-1j) 如果如果i,j0,i,j0,且且ai-1bj-1ai-1bj-1。 上節(jié)上節(jié) 下節(jié)下節(jié) 算法算法( (遞歸形式遞歸形式) ) int Num=100 cha

37、r aNum,bNum,strNum; main( ) int m,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é) 下節(jié)下節(jié) lcs_len(int i，j) /計算最優(yōu)值計算最優(yōu)值 if ( i=0 or j=0) cij=0; else if (ai-1=bj-1) cij= lcs_len(i-1，j-1)+1 ; else cij=max（lcs_len(i，j-1)，lcs_len(i-

38、1，j); buile_lcs (k,i,j); /構(gòu)造最長公共子序列構(gòu)造最長公共子序列 if （i=0 or j=0 ） return; if（ cij=ci-1j ） buile_lcs (k,i-1,j); else if （cij=cij-1 ） buile_lcs (k,i,j-1); else strk= ai-1; buile_lcs (k-1, i-1,j-1); 上節(jié)上節(jié) 下節(jié)下節(jié) 算法算法( (非遞歸非遞歸) ) n=100 char an,bn,strn; lcs_len(char a, char b, int c n) /計算最優(yōu)值計算最優(yōu)值 int m,n,i,j;

39、print (“Enter two string”); input(a,b); m=strlen(a); n=strlen(b); for (i=0;i=m;i+) ci0=0; for (i=0;i=n;i+) c0i=0; for (i=1;i=m;i+) for (j=1;j=cij-1) cij=ci-1j; else cij=cij-1; buile_lcs( ) /構(gòu)造最長公共子序列構(gòu)造最長公共子序列 int k, i=strlen(a), j=strlen(b); k=lcs_len( ); strk=; while (k0) if (cij=ci-1j) i=i-1; else

40、 if (cij=cij-1) j=j-1; else k=k-1; strk=ai-1; j=j-1; 上節(jié)上節(jié) 下節(jié)下節(jié) 【例【例5】最長不降子序列最長不降子序列 設(shè)有由設(shè)有由n n個不相同的整數(shù)組成的數(shù)列，記為個不相同的整數(shù)組成的數(shù)列，記為: : a(1) a(1)、a(2)a(2)、a(n)a(n)且且a(i)a(j) (ij)a(i)a(j) (ij) 若存在若存在i1i2i3 i1i2i3 ik ik 且有且有a(i1)a(i2) a(i1)a(i2) a(ik a(ik) )， 則稱為長度為則稱為長度為k k的不下降序列。請求出一個數(shù)列的最長不下降序列。的不下降序列。請求出一個數(shù)

41、列的最長不下降序列。 算法設(shè)計算法設(shè)計 算法算法( (逆推法逆推法) ) 上節(jié)上節(jié) 下節(jié)下節(jié) 算法設(shè)計算法設(shè)計 1. 1. 遞推關(guān)系遞推關(guān)系 1) 1) 對對a(n)a(n)來說，由于它是最后一個數(shù)，所以當(dāng)從來說，由于它是最后一個數(shù)，所以當(dāng)從a(n)a(n)開始查找開始查找 時時, ,只存在長度為只存在長度為1 1的不下降序列；的不下降序列； 2) 2) 若從若從a(n-1)a(n-1)開始查找，則存在下面的兩種可能性：開始查找，則存在下面的兩種可能性： (1)(1)若若a(n-1)a(n)a(n-1)a(n)a(n-1)a(n)則存在長度為則存在長度為1 1的不下降序列的不下降序列a(n-1

42、)a(n-1)或或a(n)a(n)。 3) 3) 一般若從一般若從a(i)a(i)開始開始, ,此時最長不下降序列應(yīng)該按下列方法求出此時最長不下降序列應(yīng)該按下列方法求出: : 在在a(i+1),a(i+2),a(i+1),a(i+2),a(n),a(n)中，找出一個比中，找出一個比a(i)a(i)大的且最大的且最 長的不下降序列，作為它的后繼。長的不下降序列，作為它的后繼。 上節(jié)上節(jié) 下節(jié)下節(jié) 算法算法( (逆推法逆推法) ) int maxn=100;int maxn=100; int amaxn,bmaxn,cmaxnint amaxn,bmaxn,cmaxn; main() main()

43、 int int n,i,j,max,p; n,i,j,max,p; input(n); input(n); for (i = 1;i n;i+) for (i = 1;i =1; i=i-1) max=0; p=0; for(j=i+1; j=n; j=j+1) if (aimax) max=bj; p=j; if( p0 ) bi=bp+1; ci=p ; max=0; p=0; for (i = 1;i max) max:=bi; p:=i ; print(maxlong=,max); print (result is:); while (p0 ) print(ap); p:=cp; 上

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

45、 4.6 4.6 算法策略間的比較算法策略間的比較 “貪婪算法貪婪算法” “遞推法遞推法” “遞歸法遞歸法” “枚舉法枚舉法” “遞歸回朔法遞歸回朔法” “分治法分治法” “動態(tài)規(guī)劃法動態(tài)規(guī)劃法” 上節(jié)上節(jié) 下節(jié)下節(jié) 4.6.1 4.6.1 不同算法策略特點小結(jié)不同算法策略特點小結(jié) “貪婪算法貪婪算法” 這些策略求解的是最簡單的一類問題，或者說是對問這些策略求解的是最簡單的一類問題，或者說是對問 題要求最嚴(yán)格的算法策略。題要求最嚴(yán)格的算法策略?！柏澙匪惴ㄘ澙匪惴ā苯鉀Q這類問題是解決這類問題是 按一定順序（從前向后或從后向前等）一定的策略，只需按一定順序（從前向后或從后向前等）一定的策略，只需

46、考慮當(dāng)前局部信息就能做出決策，即所謂局部最優(yōu)就是全考慮當(dāng)前局部信息就能做出決策，即所謂局部最優(yōu)就是全 局最優(yōu)。局最優(yōu)。 上節(jié)上節(jié) 下節(jié)下節(jié) “遞推法遞推法” “ “遞推法遞推法”和貪婪算法一樣也是由當(dāng)前問題的逐步解決和貪婪算法一樣也是由當(dāng)前問題的逐步解決 從而得到整個問題的解，只是依賴的是信息間本身的遞推關(guān)從而得到整個問題的解，只是依賴的是信息間本身的遞推關(guān) 系，每一步不需要策略參與到算法中，它們更多地用于計算。系，每一步不需要策略參與到算法中，它們更多地用于計算。 上節(jié)上節(jié) 下節(jié)下節(jié) “遞歸法遞歸法” 和遞推法類似，遞歸法是利用大問題與其子問題間的遞和遞推法類似，遞歸法是利用大問題與其子問題

47、間的遞 歸關(guān)系來解決問題的。能采用遞歸描述的算法通常有這樣的歸關(guān)系來解決問題的。能采用遞歸描述的算法通常有這樣的 特征：為求解規(guī)模為特征：為求解規(guī)模為N N的問題，設(shè)法將它分解成規(guī)模較小的的問題，設(shè)法將它分解成規(guī)模較小的 問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并問題，然后從這些小問題的解方便地構(gòu)造出大問題的解，并 且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分且這些規(guī)模較小的問題也能采用同樣的分解和綜合方法，分 解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模較解成規(guī)模更小的問題，并從這些更小問題的解構(gòu)造出規(guī)模較 大問題的解。特別地，當(dāng)規(guī)模大問題的解。特別地，當(dāng)規(guī)模N=1N

48、=1時，能直接得解。時，能直接得解。 上節(jié)上節(jié) 下節(jié)下節(jié) “枚舉法枚舉法” 枚舉法既是一個策略，也是一個算法，也是一個分析問枚舉法既是一個策略，也是一個算法，也是一個分析問 題的手段。枚舉法的求解思路很簡單題的手段。枚舉法的求解思路很簡單, ,就是對所有可能的解逐就是對所有可能的解逐 一嘗試，從而找出問題的真正解。當(dāng)然這就要求所解的問題一嘗試，從而找出問題的真正解。當(dāng)然這就要求所解的問題 可能的解是可能的解是有限的、固定的有限的、固定的，不會產(chǎn)生組合爆炸、容易枚舉，不會產(chǎn)生組合爆炸、容易枚舉 的。多用于決策類問題。這類問題都不易進(jìn)行問題的分解，的。多用于決策類問題。這類問題都不易進(jìn)行問題的分解

49、， 只能只能整體來求解整體來求解。 上節(jié)上節(jié) 下節(jié)下節(jié) “遞歸回朔法遞歸回朔法” 類似于枚舉法的思想類似于枚舉法的思想, ,遞歸回朔法通過遞歸嘗試遍問題遞歸回朔法通過遞歸嘗試遍問題 各個可能解的通路，發(fā)現(xiàn)此路不通時回朔到上一步繼續(xù)嘗試各個可能解的通路，發(fā)現(xiàn)此路不通時回朔到上一步繼續(xù)嘗試 別的通路。在下一章中對其應(yīng)用做詳細(xì)介紹。別的通路。在下一章中對其應(yīng)用做詳細(xì)介紹。 上節(jié)上節(jié) 下節(jié)下節(jié) “分治法分治法” 求解的則是較復(fù)雜的問題，這類問題是可以被分解成求解的則是較復(fù)雜的問題，這類問題是可以被分解成獨獨 立的子問題立的子問題來解決的，將兩個或兩個以上的獨立子問題的解來解決的，將兩個或兩個以上的獨立

50、子問題的解 “合成合成”，就得到較大的子問題的解，最后合成為總問題的，就得到較大的子問題的解，最后合成為總問題的 解。解。 上節(jié)上節(jié) 下節(jié)下節(jié) “動態(tài)規(guī)劃法動態(tài)規(guī)劃法” 動態(tài)規(guī)劃法與貪心法類似動態(tài)規(guī)劃法與貪心法類似，是通過多階段決策過程來解，是通過多階段決策過程來解 決問題的。但每個階段決策的結(jié)果是一個決策結(jié)果序列，這決問題的。但每個階段決策的結(jié)果是一個決策結(jié)果序列，這 個結(jié)果序列中最后采用哪一個結(jié)果取決于以后每個階段決策，個結(jié)果序列中最后采用哪一個結(jié)果取決于以后每個階段決策， 因此稱為因此稱為“動態(tài)動態(tài)”規(guī)劃法。當(dāng)然每一次的決策結(jié)果序列都必規(guī)劃法。當(dāng)然每一次的決策結(jié)果序列都必 須進(jìn)行存儲。因

51、此，可以說須進(jìn)行存儲。因此，可以說“動態(tài)規(guī)劃是高效率、高消費的動態(tài)規(guī)劃是高效率、高消費的 算法算法”。 另一方面，另一方面，動態(tài)規(guī)劃法與分治法類似動態(tài)規(guī)劃法與分治法類似，當(dāng)問題不能分解，當(dāng)問題不能分解 為獨立的子問題為獨立的子問題, ,但又符合最優(yōu)化原理但又符合最優(yōu)化原理( (最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)) )時時, , 用動態(tài)規(guī)劃，通過多階段決策過程從逐步找出子問題的最優(yōu)用動態(tài)規(guī)劃，通過多階段決策過程從逐步找出子問題的最優(yōu) 解，從而決策出問題的結(jié)果。解，從而決策出問題的結(jié)果。 上節(jié)上節(jié) 下節(jié)下節(jié) 1. 1. 對問題進(jìn)行分解的算法策略對問題進(jìn)行分解的算法策略-分治法分治法 與與 動態(tài)規(guī)劃法動態(tài)

52、規(guī)劃法 2. 2. 多階段過程多階段過程 貪婪算法貪婪算法 、 遞推法遞推法 、 遞歸法遞歸法 和和 動態(tài)規(guī)劃法動態(tài)規(guī)劃法 3. 3. 全面逐一嘗試、比較全面逐一嘗試、比較 蠻力法蠻力法 、 枚舉法枚舉法 、 遞歸回溯法遞歸回溯法 4 4算法策略的中心思想算法策略的中心思想 上節(jié)上節(jié) 下節(jié)下節(jié) 4.6.2 4.6.2 算法策略間的關(guān)聯(lián)算法策略間的關(guān)聯(lián) 1.對問題進(jìn)行分解的算法策略 -“分治法”與“動態(tài)規(guī)劃法” “分治法”與“動態(tài)規(guī)劃法”都是遞歸思想的應(yīng)用之一， 是找出大問題與小的子問題之間的關(guān)系,直到小的子問題很容 易解決，再由小的子問題的解導(dǎo)出大問題的解。區(qū)別在于： 上節(jié) 下節(jié) 分治法分治法

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

54、節(jié) 第一條特征是絕大多數(shù)問題都可以滿足的第一條特征是絕大多數(shù)問題都可以滿足的; ; 第二條特征是應(yīng)用分治法的前提第二條特征是應(yīng)用分治法的前提, ,它也是大多數(shù)問題可以滿足的它也是大多數(shù)問題可以滿足的; ; 第三條特征是關(guān)鍵。第三條特征是關(guān)鍵。 第四條特征涉及到分治法的效率。第四條特征涉及到分治法的效率。 動態(tài)規(guī)劃的動態(tài)規(guī)劃的實質(zhì)實質(zhì)是分治思想和解決冗余。是分治思想和解決冗余。 上節(jié)上節(jié) 下節(jié)下節(jié) 2 2多階段過程多階段過程“貪婪算法貪婪算法”、“遞推法遞推法”、 “遞歸法遞歸法”和和“動態(tài)規(guī)劃法動態(tài)規(guī)劃法” 多階段過程就是按一定順序多階段過程就是按一定順序( (從前向后或從后向前等從前向后或從

55、后向前等) )一一 定的策略定的策略, , 逐步解決問題的方法。逐步解決問題的方法。 “ “貪婪算法貪婪算法”每一步根據(jù)策略得到一個結(jié)果傳遞到下一每一步根據(jù)策略得到一個結(jié)果傳遞到下一 步，自頂向下，一步一步地作出貪心選擇。步，自頂向下，一步一步地作出貪心選擇。 上節(jié)上節(jié) 下節(jié)下節(jié) “動態(tài)規(guī)劃法動態(tài)規(guī)劃法”則根據(jù)一定的決策則根據(jù)一定的決策, , 每一步?jīng)Q策出的不每一步?jīng)Q策出的不 是一個結(jié)果，而只是使問題的規(guī)模不斷的縮小，如果決策比是一個結(jié)果，而只是使問題的規(guī)模不斷的縮小，如果決策比 較簡單較簡單, ,是一般的算法運算是一般的算法運算, ,則可找到不同規(guī)模問題間的關(guān)系，則可找到不同規(guī)模問題間的關(guān)系

56、， 使算法演變成使算法演變成“遞推法遞推法”、“遞歸法遞歸法”算法算法, ,所以說動態(tài)規(guī)劃所以說動態(tài)規(guī)劃 更側(cè)重算法設(shè)計策略，而不是算法。更側(cè)重算法設(shè)計策略，而不是算法。 “ “遞推法遞推法”、“遞歸法遞歸法”更注重每一步之間的關(guān)系更注重每一步之間的關(guān)系, ,決策決策 的因素較少。的因素較少?！斑f推法遞推法”根據(jù)關(guān)系從前向后推根據(jù)關(guān)系從前向后推, ,由小規(guī)模的結(jié)由小規(guī)模的結(jié) 論論, ,推解出問題的解。推解出問題的解?！斑f歸法遞歸法”根據(jù)關(guān)系先從后向前使大問根據(jù)關(guān)系先從后向前使大問 題，轉(zhuǎn)化為小問題，最后同樣由小規(guī)模結(jié)論，推解出問題的題，轉(zhuǎn)化為小問題，最后同樣由小規(guī)模結(jié)論，推解出問題的 解。解。

57、 上節(jié)上節(jié) 下節(jié)下節(jié) 3 3全面逐一嘗試、比較全面逐一嘗試、比較“蠻力法蠻力法”、 “枚舉法枚舉法”、“遞歸回溯法遞歸回溯法” 考慮到有這樣一類問題，問題中不易找到信息間的相互考慮到有這樣一類問題，問題中不易找到信息間的相互 關(guān)系，也不能分解為獨立的子問題關(guān)系，也不能分解為獨立的子問題, ,似乎只有把各種可能情況似乎只有把各種可能情況 都考慮到都考慮到, ,并把全部解都列出來之后并把全部解都列出來之后, ,才能判定和得到最優(yōu)解。才能判定和得到最優(yōu)解。 對于規(guī)模不大的問題，這些策略簡單方便對于規(guī)模不大的問題，這些策略簡單方便; ;而當(dāng)問題的計算復(fù)而當(dāng)問題的計算復(fù) 雜度高且計算量很大時雜度高且計算

58、量很大時, ,還是考慮采用還是考慮采用“動態(tài)規(guī)劃法動態(tài)規(guī)劃法”這個更這個更 有效的算法策略有效的算法策略。 上節(jié) 下節(jié) 枚舉法算法的實現(xiàn)枚舉法算法的實現(xiàn)依賴于循環(huán)依賴于循環(huán), ,通過循環(huán)嵌套枚舉問題中通過循環(huán)嵌套枚舉問題中 各種可能的情況各種可能的情況, ,如八皇后問題能用八重循環(huán)嵌套枚舉。而對如八皇后問題能用八重循環(huán)嵌套枚舉。而對 于規(guī)模于規(guī)模不固定不固定的問題就無法用固定重數(shù)的循環(huán)嵌套來枚舉了的問題就無法用固定重數(shù)的循環(huán)嵌套來枚舉了, , 有的問題可能通過變換枚舉對象也能用循環(huán)嵌套枚舉實現(xiàn)有的問題可能通過變換枚舉對象也能用循環(huán)嵌套枚舉實現(xiàn), ,但但 更多的任意指定規(guī)模的問題是靠遞歸回朔法來

59、更多的任意指定規(guī)模的問題是靠遞歸回朔法來“枚舉枚舉”或或 “遍歷遍歷”各種可能的情況。比如各種可能的情況。比如n n皇后問題只能用皇后問題只能用“遞歸回朔遞歸回朔 法法”通過遞歸實現(xiàn)（當(dāng)然可以通過棧通過遞歸實現(xiàn)（當(dāng)然可以通過棧, ,而不用遞歸）。而不用遞歸）。 上節(jié)上節(jié) 下節(jié)下節(jié) 4 4算法策略的中心思想算法策略的中心思想 所有算法策略的中心思想就是用算法的基本工具循環(huán)所有算法策略的中心思想就是用算法的基本工具循環(huán) 機制和遞歸機制實現(xiàn)算法。遞推法自然不用多說，貪婪算法機制和遞歸機制實現(xiàn)算法。遞推法自然不用多說，貪婪算法 就是逐步?jīng)Q策解決問題，動態(tài)規(guī)劃也是。就是逐步?jīng)Q策解決問題，動態(tài)規(guī)劃也是。

60、上節(jié) 下節(jié) 4.6.3 4.6.3 算法策略側(cè)重的問題類型算法策略側(cè)重的問題類型 一般我們在實際應(yīng)用中遇到的問題主要分為四類一般我們在實際應(yīng)用中遇到的問題主要分為四類: :判定性問題、判定性問題、 計算問題、最優(yōu)化問題和構(gòu)造性問題。計算問題、最優(yōu)化問題和構(gòu)造性問題。 遞推法遞推法 、 遞歸法遞歸法 算法較適合解決判定性問題、計算問題。算法較適合解決判定性問題、計算問題。 “貪婪算法貪婪算法”、“分治法分治法” ” 、“動態(tài)規(guī)劃法動態(tài)規(guī)劃法” ” 與與“枚舉法枚舉法” ” 較適合較適合 解最優(yōu)化問題。解最優(yōu)化問題。 構(gòu)造性問題更多地依賴于人的經(jīng)驗和抽象能力，算法一般是構(gòu)造性問題更多地依賴于人的經(jīng)