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

1、第 四 章 基本的算法策略,貪婪法又叫登山法, 它的根本思想是逐步到達(dá)山頂,即逐步獲得最優(yōu)解。貪婪算法沒有固定的算法框架，算法設(shè)計(jì)的關(guān)鍵是貪婪策略的選擇。一定要注意，選擇的貪婪策略要具有無后向性。某狀態(tài)以后的過程和不會影響以前的狀態(tài),只與當(dāng)前狀態(tài)或以前的狀態(tài)有關(guān),稱這種特性為無后效性。 上節(jié) 下節(jié),4.4 貪婪算法,【例1】鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意S個(gè)數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。 輸入數(shù)據(jù)均不需判錯(cuò)。輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)（N不超過240位）。 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)：對高精度正

2、整數(shù)的運(yùn)算在上一節(jié)我們剛剛接觸過，和那里一樣，將輸入的高精度數(shù)存儲為字符串格式。根據(jù)輸出要求設(shè)置數(shù)組，在刪除數(shù)字時(shí)記錄其位置。 上節(jié) 下節(jié),4.4.1 可絕對貪婪問題,問題分析 在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)此貪婪策略就可以解決這個(gè)問題。 怎么樣根據(jù)貪婪策略刪除數(shù)字呢？總目標(biāo)是刪除高位較大的數(shù)字，具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過“枚舉歸納”設(shè)計(jì)算法的細(xì)節(jié)，看一個(gè)實(shí)例（s=3） ： n1=“1 2 4 3 5 8 6 3” 4比3大 刪除 “1 2 3 5 8 6 3” 8比6大 刪除 “1 2 3 5 6 3” 6比3大 刪除 “1 2 3 5 3”

3、 只看這個(gè)實(shí)例，有可能“歸納”出不正確的算法，先看下一個(gè)實(shí)例，我們再進(jìn)一步解釋： n2=”2 3 1 1 8 3” 3比1大 刪除 “2 1 1 8 3” 2比1大 刪除 “ 1 1 8 3” 8比3大 刪除 “ 1 1 3”,由實(shí)例n1，相鄰數(shù)字只需要從前向后比較；而從實(shí)例n2中可以看出當(dāng)?shù)趇位與第i+1位比較，若刪除第i位后，必須向前考慮第i-1位與第i+1位進(jìn)行比較，才能保證結(jié)果的正確性。 由此可知通過實(shí)例設(shè)計(jì)算法時(shí)，枚舉的實(shí)例一定要有全面性，實(shí)例最好要能代表所有可能的情況，或者在必要時(shí)多列舉幾個(gè)不同的實(shí)例。再看以下兩個(gè)實(shí)例又可總結(jié)出一些需要算法特殊處理的情況。 n3=”1 2 3 4

4、5 6 7” s=3 由這個(gè)實(shí)例看出，經(jīng)過對n3相鄰比較一個(gè)數(shù)字都沒有刪除，這就要考慮將后三位進(jìn)行刪除，當(dāng)然還有可能，在相鄰比較的過程中刪除的位數(shù)小于s時(shí)，也要進(jìn)行相似的操作。 n4=”1 2 0 0 8 3” 3比0大 刪除 “1 0 0 8 3” 2比0大 刪除 “ 0 0 8 3” 8比3大 刪除 “ 0 0 3” 得到的新數(shù)數(shù)據(jù)是3,由這個(gè)實(shí)例子又能看出，當(dāng)刪除掉一些數(shù)字后，結(jié)果的高位有可能出現(xiàn)數(shù)字“0”，直接輸出這個(gè)數(shù)據(jù)不合理，要將結(jié)果中高位的數(shù)字“0”全部刪除掉，再輸出。特別地還要考慮若結(jié)果串是“0000”時(shí)，不能將全部“0”都刪除，而要保留一個(gè)“0”最后輸出。 由此可以看出進(jìn)行算

5、法設(shè)計(jì)時(shí)，從具體到抽象的歸納一定要選取大量不同的實(shí)例，充分了解和體會解決問題的過程、規(guī)律和各種不同情況，才能設(shè)計(jì)出正確的算法。 算法設(shè)計(jì)1： 根據(jù)以上實(shí)例分析，算法主要由四部分組成：初始化、相鄰數(shù)字比較（必要時(shí)刪除）、處理比較過程中刪除不夠s位的情況和結(jié)果輸出。 其中刪除字符的實(shí)現(xiàn)方法很多，如：,1）物理進(jìn)行字符刪除，就是用后面的字符覆蓋已刪除的字符，字符串長度改變。這樣可能會有比較多字符移動操作，算法效率不高。 1） 可以利用數(shù)組記錄字符的存在狀態(tài)，元素值為“1”表示對應(yīng)數(shù)字存在，元素值為“0”表示對應(yīng)數(shù)字已刪除。這樣避免了字符的移動，字符串長度不會改變，可以省略專門記錄刪除數(shù)字的位置。但這

6、樣做前后數(shù)字的比較過程和最后的輸出過程相對復(fù)雜一些。 2） 同樣還是利用數(shù)組，記錄未刪除字符的下標(biāo)，粗略的過程如下： n=“1 2 4 3 5 8 3 3” 0 0 0 0 0 0 4比3大 刪除 “1 2 3 5 8 3 3” 1 2 4 5 0 0 8比3大 刪除 “1 2 3 5 3 3” 1 2 4 5 0 5比3大 刪除 “1 2 3 3 3” 1 2 4 7 8 這時(shí)數(shù)組好象是數(shù)據(jù)庫中的索引文件。此方式同樣存在操作比較復(fù)雜的問題。,我們采用方法1）。 一種簡單的控制相鄰數(shù)字比較的方法是每次從頭開始，最多刪除s次，也就從頭比較s次。按題目要求設(shè)置數(shù)組data記錄刪除的數(shù)字所在位置 d

7、elete(char n,int b,int k) int i; for(i=b;ilen) print(“data error”); return;,j1=0; for (i=0;inj+1) /貪婪選擇 delete(n,j,1); if (jj1) datai=j+i; /記錄刪除數(shù)字位置 else /實(shí)例2向前刪除的情況實(shí)例 datai=datai-1-1; j1=j; break; if( jlength(n) break; for (i=i;i=s;i=i+1) j=len-i+1;delete(n,j,1); datai=j;,while (n1=0 and length(n)

8、1) delete(n,1,1); /將字符串首的若干個(gè)“0”去掉 print(n); for (i=1;i=s;i=i+1) print(datai, ); 算法說明1：注意記錄刪除位置不一定是要刪除數(shù)字d的下標(biāo)，因?yàn)橛锌赡躣的前或后有可能已經(jīng)有字符被刪除，d的前面已經(jīng)有元素刪除容易想到，但一定不要忽略了其后也有可能已刪除了字符，實(shí)例2中刪除1時(shí)，其后的2已被刪除。要想使記錄刪除的位置操作簡便，使用算法設(shè)計(jì)1中的介紹第二種刪除方式最簡單，請讀者嘗試實(shí)現(xiàn)這個(gè)設(shè)計(jì)。,算法設(shè)計(jì)2：刪除字符的方式同算法1，只是刪除字符后不再從頭開始比較，而是向前退一位進(jìn)行比較，這樣設(shè)計(jì)的算法2的效率較算法1要高一些

9、。delete()函數(shù)同前不再重復(fù)。 算法2如下： Delete_digit（） char n100; int s,i,j,c,data100,len; input(n); input(s); len=length(n); if(slen) print(“data error”); return; i=0; j=1; j1=0; while(ij1) datai=j+i; else datai=datai-1-1; i=i+1; j1=j; j=j-1; ,for (i=i;i1) delete(n,1,1); print(n); for (i=1;i=s;i=i+1) print(datai

10、, ); 算法說明2：同算法1一樣，變量i控制刪除字符的個(gè)數(shù)，變量j控制相鄰比較操作的下標(biāo)，當(dāng)刪除了第j個(gè)字符后，j賦值為j-1，以保證實(shí)例2（字符串n2）出現(xiàn)的情況得到正確的處理。,【例2】數(shù)列極差問題 在黑板上寫了N個(gè)正整數(shù)作成的一個(gè)數(shù)列，進(jìn)行如下操作:每一次擦去其中的兩個(gè)數(shù)a和b，然后在數(shù)列中加入一個(gè)數(shù)ab+1，如此下去直至黑板上剩下一個(gè)數(shù)，在所有按這種操作方式最后得到的數(shù)中，最大的記作max，最小的記作min，則該數(shù)列的極差定義為M=max-min。 問題分析 算法設(shè)計(jì) 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 算法分析 上節(jié) 下節(jié),問題分析 和上一個(gè)例題一樣，我們通過實(shí)例來認(rèn)識題目中描述的計(jì)算過程。對三個(gè)具體的

11、數(shù)據(jù)3，5，7討論，可能有以下三種結(jié)果： （3*5+1）*7+1=113、（3*7+1）*5+1=111、（5*7+1）*3+1=109 由此可見，先運(yùn)算小數(shù)據(jù)得到的是最大值，先運(yùn)算大數(shù)據(jù)得到的是最小值。 上節(jié) 下節(jié),下面再以三個(gè)數(shù)為例證明此題用貪心策略求解的合理性,不妨假設(shè)：a0，則有以下幾種組合計(jì)算結(jié)果： 1)(a*b+1)*c+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+k2+1 2)(a*c+1)*b+1=a*a*a+(2k1+k2)a*a+(k1(k1+k2)+1)*a+k1+1 3)(b*c+1)*a+1=a*a*a+(2k1+k2)a*a+(k1

12、(k1+k2)+1)*a+1 顯然此問題適合用貪婪策略,不過在求最大值時(shí)，要先選擇較小的數(shù)操作。反過來求最小值時(shí)，要先選擇較大的數(shù)操作。這是一道兩次運(yùn)用貪心策略解決的問題。 上節(jié) 下節(jié),算法設(shè)計(jì) 1）由以上分析，大家可以發(fā)現(xiàn)這個(gè)問題的解決方法和哈夫曼樹的構(gòu)造過程相似，不斷從現(xiàn)有的數(shù)據(jù)中，選取最大和最小的兩個(gè)數(shù)，計(jì)算后的結(jié)果繼續(xù)參與運(yùn)算，直到剩余一個(gè)數(shù)算法結(jié)束。 2) 選取最大和最小的兩個(gè)數(shù)較高效的算法是用二分法完成， 這里僅僅用簡單的逐個(gè)比較的方法來求解。 注意到由于找到的兩個(gè)數(shù)將不再參與其后的運(yùn)算，其中一個(gè)自然地是用它們的計(jì)算結(jié)果代替，另一個(gè)我們用當(dāng)前的最后一個(gè)數(shù)據(jù)覆蓋即可。所以不但要選取最

13、大和最小，還必須記錄它們的位置，以便將其覆蓋。 3）求max、min的過程必須獨(dú)立，也就是說求max和min都必須從原始數(shù)據(jù)開始,否則不能找到真正的max和min。 上節(jié) 下節(jié),數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 1) 由設(shè)計(jì)2）、3）知，必須用兩個(gè)數(shù)組同時(shí)存儲初始數(shù)據(jù)。 2) 求最大和最小的兩個(gè)數(shù)的函數(shù)至少要返回兩個(gè)數(shù)據(jù)，為方便起見我們用全局變量實(shí)現(xiàn)。 int s1,s2; main（ ） int j,n,a100,b100,max,min; print(“How mang data?”); input(n); print(“input these data”); for (j=1;j=n;j=j+1) inpu

14、t(aj); bj=aj; min= calculatemin(a,n); max= calculatemax(b,n); print(“max-min=”, max-min) ,calculatemin(int a,int n) int j; while (n2) max2(a,n); as1= as1* as2+1; as2=an; n=n-1; return(a1* a2+1); max2(int a,int n) int j; if(a1=a2) s1=1; s2=2; else s1=2; s2=1; for (j=3;jas1) s2=s1; s1=j; else if (ajas

15、2) s2=j; 上節(jié) 下節(jié),calculatemax(int a,int n) int j; while (n2) min2(a,n); as1= as1* as2+1; as2=an; n=n-1; return(a1* a2+1); min2(int a ,int n) int j; if(a1=a2) s1=1; s2=2; else s1=2; s2=1; for (j=3;j=n;j+) if (ajas1) s2=s1; s1=j; else if (ajas2) s2=j; 上節(jié) 下節(jié),算法分析 算法中的主要操作就是比較查找和計(jì)算，它們都是線性的，因此算法的時(shí)間復(fù)雜度為O(n)

16、。由于計(jì)算最大結(jié)果和計(jì)算最小結(jié)果需要獨(dú)立進(jìn)行,所以算法的空間復(fù)雜度為O(2n)。 貪婪策略不僅僅可以應(yīng)用于最優(yōu)化問題中，有時(shí)在解決構(gòu)造類問題時(shí)，用這種策略可以盡快地構(gòu)造出一組解，如下面的例子： 上節(jié) 下節(jié),【例3】: 設(shè)計(jì)一個(gè)算法， 把一個(gè)真分?jǐn)?shù)表示為埃及分?jǐn)?shù)之和的形式。所謂埃及分?jǐn)?shù)，是指分子為1的形式。如：7/8=1/2+1/3+1/24。 問題分析 數(shù)學(xué)模型 算法設(shè)計(jì) 算法 上節(jié) 下節(jié),問題分析 基本思想是， 逐步選擇分?jǐn)?shù)所包含的最大埃及分?jǐn)?shù)， 這些埃及分?jǐn)?shù)之和就是問題的一個(gè)解。 如：7/81/2， 7/8-1/21/3， 7/8-1/2-1/3=1/24。 過程如下： 1)找最小的n（也

17、就是最大的埃及分?jǐn)?shù)），使分?jǐn)?shù)f1/n； 2)輸出1/n； 3)計(jì)算f=f-1/n； 4)若此時(shí)的f是埃及分?jǐn)?shù)，輸出f,算法結(jié)束,否則返回1）。 上節(jié) 下節(jié),數(shù)學(xué)模型 記真分?jǐn)?shù)F=A/B；對B/A進(jìn)行整除運(yùn)算,商為D, 余數(shù)為0KA，它們之間的關(guān)系及導(dǎo)出關(guān)系如下： B=A*D+K，B/A=D+K/AD+1，A/B1/(D+1)，記C=D+1。 這樣我們就找到了分?jǐn)?shù)F所包含的“最大的”埃及分?jǐn)?shù)就是1/C。進(jìn)一步計(jì)算： A/B-1/C=（A*C-B）/B*C 也就是說繼續(xù)要解決的是有關(guān)分子為A=A*C-B,分母為B=B*C的問題。 上節(jié) 下節(jié),算法設(shè)計(jì) 由以上數(shù)學(xué)模型，真正的算法過程如下： 1)設(shè)某

18、個(gè)真分?jǐn)?shù)的分子為A(1），分母為B； 2)把B除以A的商的整數(shù)部分加1后的值作為埃及 分?jǐn)?shù)的一個(gè)分母C; 3)輸出1/C； 4)將A乘以C減去B作為新的A； 5)將B乘以C作為新的B； 6)如果A大于1且能整除B,則最后一個(gè)分母為B/A； 7)如果A1,則最后一個(gè)分母為B;否則轉(zhuǎn)步驟(2). 上節(jié) 下節(jié),例：7/8=1/2+1/3+1/24的解題步驟： 同樣用變量A表示分子，變量B表示分母； C=8+1=2 /說明7/81/2， 打印1/2 A=7*2-8=6，B=B*C=16 /在計(jì)算7/8-1/2=(7*2-8)/(7*2)=6/16=A/B C=16/6+1=3 /說明16/61/3，

19、打印1/3 A=6*3-16=2，B=B*C=16*3=48 /在計(jì)算6/16-1/3=(6*3-16)/(16*3)=2/48=A/B A1但B/A為整數(shù)24，打印1/24 結(jié)束. 上節(jié) 下節(jié),算法,main（） int a,b,c; print(“input element”); input(a); print(“input denominator”); input(b); if(ab) print(“input error”); else if (a=1 or b mod a=0) print( a, /,b, = 1, /,b/a); else 上節(jié) 下節(jié),while(a1) c =

20、b a + 1 a = a * c - b: b = b * c print( 1/,c); if (b mod a =0 ) print (+1/; b / a); a=1; if( a 1) print(+); ,【例4】 幣種統(tǒng)計(jì)問題 【例5】 取數(shù)游戲 上節(jié) 下節(jié),4.4.2 相對或近似貪婪問題,4.4.1節(jié)的三個(gè)例子對于輸入的任何數(shù)據(jù)，貪婪策略都是適用的，因此我們稱它們?yōu)椤翱山^對貪婪問題”?？聪乱还?jié)的例子就明白，有的問題就不一定如此了。,【例4】幣種統(tǒng)計(jì)問題 某單位給每個(gè)職工發(fā)工資（精確到元）。為了保證不要臨時(shí)兌換零錢, 且取款的張數(shù)最少，取工資前要統(tǒng)計(jì)出所有職工的工資所需各種幣值(

21、100,50,20,10,5,2,1元共七種)的張數(shù)。請編程完成。 算法設(shè)計(jì) 算法說明 算法分析 貪婪策略 上節(jié) 下節(jié),算法設(shè)計(jì) 1) 從鍵盤輸入每人的工資。 2) 對每一個(gè)人的工資，用“貪婪”的思想，先盡量多地取大面額的幣種，由大面額到小面額幣種逐漸統(tǒng)計(jì)。 3) 利用數(shù)組應(yīng)用技巧,將七種幣值存儲在數(shù)組B。這樣，七種 幣值就可表示為Bi,i=1,2,3,4,5,6,7。為了能實(shí)現(xiàn)貪婪策略，七種幣應(yīng)該從大面額的幣種到小面額的幣種依次存儲。 4) 利用數(shù)組技巧,設(shè)置一個(gè)有7個(gè)元素的累加器數(shù)組S。 上節(jié) 下節(jié),算法,main( ) int i,j,n,GZ,A； int B8=0,100,50,20

22、,10,5,2,1,S8; input(n); for(i=1;i=n;i+) input(GZ); for(j=1,j=7;j+) A=GZ/Bj; Sj=Sj+A; GZ=GZ-A*Bj; for(i=1;i=7;i+) print(Bi, “-”, Si); 上節(jié) 下節(jié),算法說明 每求出一種面額所需的張數(shù)后， 一定要把這部分金額減去：“GZ=GZ-A*Bj;”,否則將會重復(fù)計(jì)算。 算法分析 算法的時(shí)間復(fù)雜性是O（n）。 上節(jié) 下節(jié),解決問題的貪婪策略： 以上問題的背景是在我國,題目中不提示我們也知道有哪些幣種,且這樣的幣種正好適合使用貪婪算法(感興趣的讀者可以證明這個(gè)結(jié)論)。假若,某國的

23、幣種是這樣的,共9種:100,70,50,20,10,7,5,2,1。在這樣的幣值種類下,再用貪婪算法就行不通了,比如某人工資是140,按貪婪算法140=100*(1張)+20*(2張)共需要3張,而事實(shí)上,只要取2張70面額的是最佳結(jié)果,這類問題可以考慮用動態(tài)規(guī)劃算法來解決。 由此，在用貪婪算法策略時(shí)，最好能用數(shù)學(xué)方法證明每一步的策略是否能保證得到最優(yōu)解。 上節(jié) 下節(jié),【例5】取數(shù)游戲 有2個(gè)人輪流取2n個(gè)數(shù)中的n個(gè)數(shù)，取數(shù)之和大者為勝。請編寫算法，讓先取數(shù)者勝，模擬取數(shù)過程。 問題分析 算法設(shè)計(jì) 算法說明 算法分析 上節(jié) 下節(jié),問題分析 這個(gè)游戲一般假設(shè)取數(shù)者只能看到2n個(gè)數(shù)中兩邊的數(shù),用

24、貪婪算法的情況: 若一組數(shù)據(jù)為：6,16,27,6,12,9,2,11,6,5。用貪婪策略每次兩人都取兩邊的數(shù)中較大的一個(gè)數(shù),先取者勝.以A先取為例： 取數(shù)結(jié)果為： A 6,27,12,5,11=61 勝 B 16,6,9,6,2=39 上節(jié) 下節(jié),但若選另一組數(shù)據(jù)：16,27,7,12,9,2,11,6。仍都用貪婪算法，先取者A敗。 取數(shù)結(jié)果為： A 16,7,9,11=43 B 27,12,6,2=47 勝 其實(shí)，若我們只能看到兩邊的數(shù)據(jù)，則此題無論先取還是后取都無必勝的策略。這時(shí)一般的策略是用近似貪婪算法。 但若取數(shù)者能看到全部2n個(gè)數(shù)，則此問題可有一些簡單的方法，有的雖不能保證所取數(shù)的

25、和是最大，但確是一個(gè)先取者必勝的策略。 上節(jié) 下節(jié),數(shù)學(xué)模型建立：N個(gè)數(shù)排成一行，我們給這N個(gè)數(shù)從左到右編號，依次為1，2，N，因?yàn)镹為偶數(shù)，又因?yàn)槭俏覀兿热?shù)，計(jì)算機(jī)后取數(shù)，所以一開始我們既可以取到一個(gè)奇編號的數(shù)（最左邊編號為1的數(shù)）又可以取到一個(gè)偶編號的數(shù)（最右邊編號為N的數(shù)）。 如果我們第一次取奇編號（編號為1）的數(shù)，則接著計(jì)算機(jī)只能取到偶編號（編號為2或N）的數(shù)； 如果我們第一次取偶編號（編號為N）的數(shù)，則接著計(jì)算機(jī)只能取到奇編號（編號為1或N-1）的數(shù)； 即無論我們第一次是取奇編號的數(shù)還是取偶編號的數(shù)，接著計(jì)算機(jī)只能取到另一種編號（偶編號或奇編號）的數(shù)。,這是對第一個(gè)回合的分析，顯然

26、對以后整個(gè)取數(shù)過程都適用。也就是說，我們能夠控制讓計(jì)算機(jī)自始自終只取一種編號的數(shù)。這樣，我們只要比較奇編號數(shù)之和與偶編號數(shù)之和誰大，以決定最開始我們是取奇編號數(shù)還是偶編號數(shù)即可。（如果奇編號數(shù)之和與偶編號數(shù)之和同樣大，我們第一次可以任意取數(shù)，因?yàn)楫?dāng)兩者所取數(shù)和相同時(shí)，先取者為勝。,算法設(shè)計(jì)：有了以上建立的高效數(shù)學(xué)模型，算法就很簡單了，算法只需要分別計(jì)算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就先了取數(shù)者就可以確定必勝的取數(shù)方式了。 以下面一排數(shù)為例： 1 2 3 10 5 6 7 8 9 4 奇編號數(shù)之和為25（=1+3+5+7+9），小于偶編號數(shù)之和為30（=2+10+6+8+4）。我們第一次

27、取4，以后，計(jì)算機(jī)取哪邊的數(shù)我們就取哪邊的數(shù)（如果計(jì)算機(jī)取1，我們就取2；如果計(jì)算機(jī)取9，我們就取8）。這樣可以保證我們自始自終取到偶編號的數(shù)，而計(jì)算機(jī)自始自終取到奇編號的數(shù)。,main( ) int i,s1,s2,data; input(n); s1=0； s2=0; for(i=1;is2) print(“first take left”); else print(“first take right”); 這個(gè)例題又一次說明，解決問題時(shí)數(shù)學(xué)模型的選擇是非常重要的。,1.貪心法的基本思路： 從問題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，每一步都作一個(gè)不可回溯的決策,盡可能地求得最好的解。當(dāng)達(dá)

28、到某算法中的某一步不需要再繼續(xù)前進(jìn)時(shí)，算法停止。 上節(jié) 下節(jié),4.4.3 關(guān)于貪婪策略討論,2.該算法適用的問題： 貪婪算法對問題只需考慮當(dāng)前局部信息就要做出決策，也就是說使用貪婪算法的前提是“局部最優(yōu)策略能導(dǎo)致產(chǎn)生全局最優(yōu)解”。 該算法的適用范圍較小, 若應(yīng)用不當(dāng), 不能保證求得問題的最佳解。一般情況下通過一些實(shí)際的數(shù)據(jù)例子(當(dāng)然要有一定的普遍性),就能從直觀上就能判斷一個(gè)問題是否可以用貪婪算法，如本節(jié)的例2。更準(zhǔn)確的方法是通過數(shù)學(xué)方法證明問題對貪婪策略的選用性。 上節(jié) 下節(jié),3.該策略下的算法框架： 從問題的某一初始解出發(fā)； while能朝給定總目標(biāo)前進(jìn)一步do; 利用可行的決策，求出可行

29、解的一個(gè)解元素; 由所有解元素組合成問題的一個(gè)可行解。 上節(jié) 下節(jié),4.貪婪策略選擇: 首先貪婪算法的原理是通過局部最優(yōu)來達(dá)到全局最優(yōu),采用的是逐步構(gòu)造最優(yōu)解的方法。在每個(gè)階段，都作出一個(gè)看上去最優(yōu)的（在一定的標(biāo)準(zhǔn)下），決策一旦作出，就不可再更改。用貪婪算法只能解決通過局部最優(yōu)的策略能達(dá)到全局最優(yōu)的問題。因此一定要注意判斷問題是否適合采用貪婪算法策略，找到的解是否一定是問題的最優(yōu)解。 上節(jié) 下節(jié),在動態(tài)規(guī)劃算法策略中，體現(xiàn)在它的決策不是線性的而是全面考慮不同的情況分別進(jìn)行決策, 并通過多階段決策來最終解決問題。在各個(gè)階段采取決策后, 會不斷決策出新的數(shù)據(jù),直到找到最優(yōu)解.每次決策依賴于當(dāng)前狀態(tài)

30、, 又隨即引起狀態(tài)的轉(zhuǎn)移。一個(gè)決策序列就是在變化的狀態(tài)中產(chǎn)生出來的，故有“動態(tài)”的含義。所以，這種多階段決策最優(yōu)化的解決問題的過程稱為動態(tài)規(guī)劃。 上節(jié) 下節(jié),4.5 動態(tài)規(guī)劃,我們通過一個(gè)簡單的例子來說明動態(tài)規(guī)劃的多階段決策與貪婪算法有什么區(qū)別。 【例1】 數(shù)塔問題 上節(jié) 下節(jié),4.5.1 認(rèn)識動態(tài)規(guī)劃,【例1】數(shù)塔問題 有形如圖4-11所示的一個(gè)數(shù)塔，從頂部出發(fā)，在每一結(jié)點(diǎn)可以選擇向左走或是向右走，一直走到底層，要求找出一條路徑，使路徑上的數(shù)值和最大。,問題分析 算法設(shè)計(jì) 算法 小結(jié),問題分析 這個(gè)問題用貪婪算法有可能會找不到真正的最大和。以圖4-11為例就是如此。用貪婪的策略，則路徑和分別

31、為： 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è)計(jì) 動態(tài)規(guī)劃設(shè)計(jì)過程如下： 1.階段劃分： 第一步對于第五層的數(shù)據(jù)，我們做如下五次決策： 對經(jīng)過第四層2的路徑選擇第五層的19， 對經(jīng)過第四層18的路徑選擇第五層的10， 對經(jīng)過第四層9的路徑也選擇第五層的10， 對經(jīng)過第四層5的路徑選擇第五層的16。 上節(jié) 下節(jié),以上的決策結(jié)果將五階數(shù)塔問題變?yōu)?階子問題，遞推 出第四層與第五層的和為:

32、21(2+19),28(18+10),19(9+10),21(5+16)。 用同樣的方法還可以將4階數(shù)塔問題,變?yōu)?階數(shù)塔問題。 最后得到的1階數(shù)塔問題，就是整個(gè)問題的最優(yōu)解。 上節(jié) 下節(jié),2存儲、求解： 1) 原始信息存儲 原始信息有層數(shù)和數(shù)塔中的數(shù)據(jù)，層數(shù)用一個(gè)整型 變量n存儲，數(shù)塔中的數(shù)據(jù)用二維數(shù)組data，存儲成如 下的下三角陣: 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 上節(jié) 下節(jié),2) 動態(tài)規(guī)劃過程存儲 必需用二維數(shù)組a存儲各階段的決策結(jié)果。二維數(shù)組a的存儲內(nèi)容如下： dnj=datanj j=1,2,n； i=n-1,n-2,1，j=1,2,i；時(shí)

33、 dij=max(di+1j，di+1j+1)+dataij 最后a11存儲的就是問題的結(jié)果。 上節(jié) 下節(jié),3) 最優(yōu)解路徑求解及存儲 僅有數(shù)組data和數(shù)組a可以找到最優(yōu)解的路徑， 但需要自頂向下比較數(shù)組data和數(shù)組a是可以找到。如圖4.5.2求解和輸出過程如下： 上節(jié) 下節(jié),輸出a119 b=d11-data11=59-9=50 b與d21,d22 比較 b與d21相等輸出data2112 b=d21-data21=50-12=38 b與d31,d32 比較 b與d31相等輸出data3110 b=a31-data31=38-10=28 b與d41,d42 比較 b與d42相等輸出dat

34、a4218 b=d42-data42=28-18=10 b與d52,d53 比較 b與d53相等輸出data5310“ 上節(jié) 下節(jié),數(shù)組data 數(shù)組d 9 59 12 15 50 49 10 6 8 38 34 29 2 18 9 5 21 28 19 21 19 7 10 4 16 19 7 10 4 16 圖4-12 數(shù)塔及動態(tài)規(guī)劃過程數(shù)據(jù) 上節(jié) 下節(jié),為了設(shè)計(jì)簡潔的算法，我們最后用三維數(shù)組a50503存儲以上確定的三個(gè)數(shù)組的信息。 a50501代替數(shù)組data， a50502代替數(shù)組d, a50503記錄解路徑。 上節(jié) 下節(jié),數(shù)塔問題的算法,main( ) int a50503,i,j

35、,n; print( please input the number of rows:); input(n);for( i=1 ;i=n;i+) for j=1 to i do input(aij1); aij2=aij1; aij3=0; 上節(jié) 下節(jié),for (i=n-1 ; i=1;i-) for (j=1 ;j= i ;j+)if (ai+1j2ai+1j+12) aij2=aij2+ai+1j2; aij3=0; else aij2=aij2+ai+1j+12; aij3=1;print(max=,a112);j=1;for( i=1 ;i); j=j+aij3; print (anj

36、1); 上節(jié) 下節(jié),從例子中可以看到： 動態(tài)規(guī)劃=貪婪策略+遞推(降階)+存儲遞推結(jié)果 貪婪策略、遞推算法都是在“線性”地解決問題，而動態(tài)規(guī)劃則是全面分階段地解決問題?？梢酝ㄋ椎卣f動態(tài)規(guī)劃是“帶決策的多階段、多方位的遞推算法”。 上節(jié) 下節(jié),1.適合動態(tài)規(guī)劃的問題特征 動態(tài)規(guī)劃算法的問題及決策應(yīng)該具有三個(gè)性質(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ī)劃方法的基本思想是，把求解的問題分成許多階段或多個(gè)子問題，然后按順序求解各子問

37、題。最后一個(gè)子問題就是初始問題的解。 由于動態(tài)規(guī)劃的問題有重疊子問題的特點(diǎn)，為了減少重復(fù)計(jì)算，對每一個(gè)子問題只解一次，將其不同階段的不同狀態(tài)保存在一個(gè)二維數(shù)組中。 上節(jié) 下節(jié),3. 設(shè)計(jì)動態(tài)規(guī)劃算法的基本步驟 設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法的步驟： 1) 劃分階段 2) 選擇狀態(tài) 3) 確定決策并寫出狀態(tài)轉(zhuǎn)移方程 但是,實(shí)際應(yīng)用當(dāng)中的簡化步驟： 1) 分析最優(yōu)解的性質(zhì)，并刻劃其結(jié)構(gòu)特征。 2) 遞推地定義最優(yōu)值。 3) 以自底向上的方式或自頂向下的記憶化方法(備忘錄 法)計(jì)算出最優(yōu)值. 4) 根據(jù)計(jì)算最優(yōu)值時(shí)得到的信息，構(gòu)造問題的最優(yōu)解。 上節(jié) 下節(jié),4. 標(biāo)準(zhǔn)動態(tài)規(guī)劃的基本框架 for( j=1

38、 ;j=1;i=i-1) /其它n-1個(gè)階段 for (j=1 ;j=f(i) ;j=j+1)/ f(i)與 i有關(guān)的表達(dá)式 xij=j=max(或min)g(xi-1j1j2)， g(xi-1jkjk+1)； t=g(x1j1j2); /由最優(yōu)解求解最優(yōu)解的方案print(x1j1);for( i=2 ;i=f(i) ;j=j+1) if(t= xiji) break; 上節(jié) 下節(jié),【例2】 資源分配問題。 【例3】 n個(gè)矩陣連乘的問題。 上節(jié) 下節(jié),4.5.3 突出階段性的動態(tài)規(guī)劃應(yīng)用,【例2】資源分配問題。 設(shè)有資源a,分配給n個(gè)項(xiàng)目,gi(x)為第i個(gè)項(xiàng)目分得資源x所得到的利潤。求總利

39、潤最大的資源分配方案，也就是解下列問題： max z=g1(x1)+ g2(x2)+gn(xn) x1+xx2+x3+xn=a, xi0,i=1，2,3,n 函數(shù)gi(x)以數(shù)據(jù)表的形式給出. 例如：現(xiàn)有7萬元投資到A，B，C 三個(gè)項(xiàng)目，利潤見表,求問題總利潤最大的資源分配方案。 上節(jié) 下節(jié),算法設(shè)計(jì) 1階段劃分及決策 比較直觀的階段劃分就是逐步考慮每一個(gè)項(xiàng)目在不 同投資額下的利潤情況。 3. 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)： 1) 開辟一維數(shù)組q來存儲原始數(shù)據(jù)。 2) 另開辟一維數(shù)組f存儲當(dāng)前最大收益情況。 3) 開辟記錄中間結(jié)果的一維數(shù)組數(shù)組temp，記錄正在計(jì) 算的最大收益。 4) 開辟二維數(shù)組a。 5)

40、 數(shù)組gain存儲第i個(gè)工程投資數(shù)的最后結(jié)果。 上節(jié) 下節(jié),對于一般問題設(shè)計(jì)算法如下：,main( ) int i,j,k,m,n,rest; int a100100，gain100; float q100,f100,temp100; print(“How mang item? ”); input (m); print(“How mang money? ”); input (n); print(“input gain table:”); for( j=0;j= n;j+) input(qj); fj=qj; for( j=0;j= n;j+) a1,j=j; 上節(jié) 下節(jié),for( k=2;kt

41、empj） tempj=fj-i+qi; ak,j=i; for(j=0;j=1;i-) gaini=airest; rest=rest-gaini; for(i=1;i=m;i+) print(gaini,” ”); print(fn); ,【例3】n個(gè)矩陣連乘的問題。 問題分析 算法設(shè)計(jì) 算法1(遞歸算法) 算法1說明 算法2(遞歸算法) 算法3(非遞歸算法) 輸出算法 上節(jié) 下節(jié),問題分析 多個(gè)矩陣連乘運(yùn)算是滿足結(jié)合律的。 例: M15*20 * M220*50 * M350*1 * M41*100分別按 (M1*M2)*M3)*M4，M1*(M2*(M3*M4)，(M1*(M2*M3)

42、*M4 的次序相乘,各需進(jìn)行 5750, 115000, 1600次乘法。 這個(gè)問題要用“動態(tài)規(guī)劃”算法來完成: 首先,從兩個(gè)矩陣相乘的情況開始； 然后,嘗試三個(gè)矩陣相乘的情況； 最后,等到n個(gè)矩陣相乘所用的最少的乘法次數(shù)及結(jié)合方式。 上節(jié) 下節(jié),算法設(shè)計(jì) 1. 階段劃分 1）初始狀態(tài)為一個(gè)矩陣相乘的計(jì)算量為0; 2）第二階段,計(jì)算兩個(gè)相鄰矩陣相乘的計(jì)算量, 共n-1組 3）第三階段,計(jì)算兩個(gè)相鄰矩陣相乘的計(jì)算量, 共n-2組 4）最后一個(gè)階段,是n個(gè)相鄰矩陣相乘的計(jì)算量,共1組, 是問題解。 上節(jié) 下節(jié),2. 階段決策 一般地，計(jì)算M1*M2*M3*Mn 其中M1，M2，,Mi分別是 r1*

43、r2，r2*r3，,ri*ri+1階矩陣，i=1,2,3,n。 設(shè)mi,j是計(jì)算Mi*Mi+1*Mj的最少乘法次數(shù)(1ijn),對 mi,j有公式： 0 當(dāng)i=j時(shí) ri-1*ri*ri+1 當(dāng)j=i+1時(shí) min(mi,k+mk+1,j+rirk+1rj+1) ikj 當(dāng)ij時(shí) 以上動態(tài)規(guī)劃方法是按s=0,1,2,3,.,n-1的順序計(jì)算mi,i+s的。 3.記錄最佳期方案 用二維矩陣comij(n*n)來存儲使mij為最小值時(shí)的 k 值。 上節(jié) 下節(jié),算法1(遞歸算法),int r100,com100100; main（ ） int n,i; print(“How mang matrixe

44、s?”); input (n); peint(“How size every matrixe?”); for (i=1;i=n+1;i+) input (ri); print (“The least calculate quantity：”, course (1,n); for (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）

45、; 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 (tu) u= t; comij = k; return u; 上節(jié) 下節(jié),算法1說明 以上的遞歸算法雖然解決了問題，但效率很低，有子問題重疊，n=4時(shí)的遞歸過程如下圖： 上節(jié) 下節(jié),算法2(改進(jìn)后遞歸算法),int m100100,com100100,r100; matrix2（ ） int n,; print(“How ma

46、ng matrixes?”); input (n); print(“How size every matrixe?”); for (i=1;i=n+1;i+) input (ri); for (i=1;i=n;i+) /初始化化數(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;j=n;j+) print(comij); 上節(jié) 下節(jié),course (int i,int

47、 j) if （mij0） 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 (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(非遞歸算法),main（ ） int n,

48、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+) /初始化化數(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ī)劃過程/

49、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= 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è)計(jì) 以上算法中關(guān)于矩陣相乘的結(jié)合方式，只是簡單的輸出了數(shù)組com的內(nèi)容

50、，不容易直觀地被利用，還需要繼續(xù)進(jìn)行必要的人工處理，才能真正找到矩陣相乘的結(jié)合方式。怎么樣更直觀、合理地輸出結(jié)合過程？即算法的輸出能使用戶直接了解計(jì)算矩陣的過程。 首先看一下com數(shù)組存儲的信息意義，它是一個(gè)二維數(shù)組，元素comij存儲的是MiMj相乘的組合點(diǎn)k1，也就是說： Mi*Mi+1*Mj是由 Mi*Mi+1*Mk和Mk+1*Mj 同樣，在數(shù)組com中我們也能找到MiMk相乘的組合點(diǎn)k2，Mk+1Mj相乘的組合點(diǎn)k3，。 從數(shù)組信息中找到了大規(guī)模問題與小規(guī)模問題的遞歸關(guān)系：,輸出算法 記k1=com1n，則最后一次運(yùn)算的結(jié)合過程是 M1*Mk1和Mk1+1*Mn 記k2=com1k1，

51、M1*Mk1的結(jié)合過程是 M1*Mk2和Mk2+1*Mk1 ,combine(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é)問題的設(shè)計(jì)角度是從遞推思想進(jìn)行的,設(shè)計(jì)中只要找出大規(guī)模問題與小規(guī)模問題(子問題)之間的遞推關(guān)系,最后一個(gè)子問題所得最優(yōu)解就是原問題的最優(yōu)解。 【例4】求兩個(gè)字符序列的最長公共字符子序列。 【例5】最長不降子序列。 上節(jié) 下節(jié),4.5.4 突出遞

52、推的動態(tài)規(guī)劃應(yīng)用,【例4】求兩個(gè)字符序列的最長公共字符子序 列。 問題分析 算法設(shè)計(jì) 算法(遞歸形式) 算法(非遞歸) 上節(jié) 下節(jié),問題分析 若A的長度為n，若B的長度為m，則 A的子序列共有： Cn1+Cn2+ Cn3+Cnn=2n-1 B的子序列共有： Cm1+Cm2+ Cm3+Cmm=2m-1 如采用枚舉策略，當(dāng)m=n時(shí)，共進(jìn)行串比較： Cn1*Cm1+Cn2*Cm2+Cn3*Cm3+Cnn*Cnn22n 次，耗時(shí)太多,不可取。 此問題不可能簡單地分解成幾個(gè)獨(dú)立的子問題，也不能用分治法來解。所以，我們只能用動態(tài)規(guī)劃的方法去解決。 上節(jié) 下節(jié),算法設(shè)計(jì) 1遞推關(guān)系分析 設(shè) A=“a0，a1

53、，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”的一個(gè)最長公共子序列； 2）如果am-1bn-1，則若zk-1am-1，蘊(yùn)涵“z0，z1，zk-1”是a0,a1,am-2和b0,b1,bn-1的一個(gè)最長公共子 序列； 3）如果am-1bn-1，則若zk-1bn-1，蘊(yùn)涵“z0，z1， zk-1”是“a0，a1，am-1”和“b0，b1，bn-2”的一個(gè)最長公共子序列。 上節(jié) 下節(jié),2存儲、

54、子問題合并 定義cij為序列a0,a1,ai-2”和“b0,b1,bj-1”的 最長公共子序列的長度，計(jì)算cij可遞歸地表述如下： 1）cij=0 如果i=0或j=0； 2）cij=ci-1j-1+1 如果i,j0,且ai-1=bj-1； 3）cij=max(cij-1,ci-1j) 如果i,j0,且ai-1bj-1。 上節(jié) 下節(jié),算法(遞歸形式),int Num=100charaNum,bNum,strNum; main( ) int m,n,k; print(“Entertwostring”); input(a,b); m=strlen(a); n=strlen(b), k=lcs_len

55、(n,m); buile_lcs (k, n,m); print(str); 上節(jié) 下節(jié),lcs_len(inti，j) /計(jì)算最優(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-1，j); ,buile_lcs (k,i,j); /構(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); 上