PS:

??頭一次規(guī)規(guī)矩矩的按照論文的格式寫(xiě)文章，呵呵。雖然是小兒科的不能再小兒科的東西了。。不過(guò)。。也忽悠了6000多字~~嘿嘿。。肯定寫(xiě)的不好，第一次嘛。。所以。。接受大家一切批評(píng)哈！。。。文章NOI專(zhuān)刊的編輯正在審。。還不知道能不能發(fā)。。嘿嘿。。期待啊。。先發(fā)我BLOG里。。大家批評(píng)下。。

?

?

?

貪心、遞歸、遞推以及動(dòng)態(tài)規(guī)劃算法的分析與對(duì)比

王喆 天津市第五十五中學(xué)

【關(guān)鍵字】

動(dòng)態(tài)規(guī)劃 貪心 遞歸 遞推 分析 說(shuō)明 NOIP

【摘要】

本文通過(guò)典型例題分析出貪心算法、遞歸算法、遞推算法以及動(dòng)態(tài)規(guī)劃算法的區(qū)別和相似處。以及對(duì)這幾種算法的思考方法，編程方法以及“遞歸節(jié)省時(shí)間浪費(fèi)空間，遞推滾動(dòng)節(jié)省空間浪費(fèi)時(shí)間”的解釋和舉例論證。

【正文】

一、各算法的介紹

1.1貪心算法

貪心的思想可以用一句話來(lái)歸納，“每步取優(yōu)”。很好理解，假設(shè)你的程序要走I=1~N共N步，那么保證你的第I步走出的是當(dāng)前這一步的最優(yōu)值。這樣的解題方法叫做貪心算法。可見(jiàn)貪心算法并不是一個(gè)全面的枚舉方法而是若干結(jié)果中的一種，僅僅一種而已。但這種算法是不是最優(yōu)解它就不能完全保證了。

1.2遞歸算法

一般每個(gè)可以使用遞歸算法求解的題目都可以寫(xiě)出一個(gè)遞歸函數(shù)。假設(shè)這個(gè)函數(shù)是F（），那么F（）應(yīng)該為你可以表示你的解。而題目的主要問(wèn)題就是把一個(gè)大問(wèn)題轉(zhuǎn)換為若干個(gè)性質(zhì)相同的子問(wèn)題。注意是性質(zhì)相同，因?yàn)橹挥行再|(zhì)相同我們才能使用同一個(gè)函數(shù)來(lái)表示。而求解的過(guò)程是從最后一步，當(dāng)然每一步都會(huì)用到比自己要小的子問(wèn)題的值，那么要調(diào)用程序來(lái)求出這些子問(wèn)題的解，一步步返回最后得到最后的問(wèn)題的解。也可以理解為求解過(guò)程是“反向”的。因?yàn)樽兞繒?huì)是逐漸變小的。

1.3遞推算法

與遞歸算法一樣，必定會(huì)寫(xiě)出一個(gè)轉(zhuǎn)移方程，而每個(gè)可以用遞歸方法解決的問(wèn)題都可以用遞推方法解決。我們要做的依然是把大問(wèn)題轉(zhuǎn)變?yōu)?strong>性質(zhì)相同的子問(wèn)題的過(guò)程。而求解過(guò)程與遞歸方法正好相反，是從最小規(guī)模的子問(wèn)題開(kāi)始求解，最后求到最大規(guī)模的解。與遞歸不一樣的是，遞歸可以只求我們所需要的子問(wèn)題的解，而遞推算法在每一步計(jì)算求解的過(guò)程中并不知道下一步需要用什么樣的子問(wèn)題的值，于是程序必須把所有的可能性都求出來(lái)。造成了很多的計(jì)算浪費(fèi)。但遞推算法有一個(gè)遞歸算法永遠(yuǎn)做不到的優(yōu)勢(shì)就是“滾動(dòng)性”。當(dāng)遞推算法求解完第一行的子問(wèn)題的時(shí)候進(jìn)行第二行的處理，第二行會(huì)用到上一行的子問(wèn)題值。當(dāng)處理第三行的時(shí)候第一行的值就沒(méi)有用了，所以我們可以把單數(shù)行的值都存到第一各數(shù)組里，雙數(shù)行的值都存到第二個(gè)數(shù)組里。這樣可以就可以實(shí)現(xiàn)滾動(dòng)，原來(lái)原本要開(kāi)[1..n,1..n]大小的數(shù)組現(xiàn)在就可以只開(kāi)[1..n,1..2]大小的數(shù)組了，把空間復(fù)雜度從O(N²)的復(fù)雜度變?yōu)镺(2N)的復(fù)雜度。這就是所謂的“遞推省空間費(fèi)時(shí)間，遞歸省時(shí)間費(fèi)空間”的道理。

1.4動(dòng)態(tài)規(guī)劃算法

動(dòng)態(tài)規(guī)劃算法，動(dòng)態(tài)規(guī)劃算法可以理解為是遞歸算法的一個(gè)延伸。因?yàn)閱渭兊倪f歸算法是會(huì)出現(xiàn)很多子問(wèn)題的重疊的，這樣還是會(huì)造成同一問(wèn)題的重復(fù)運(yùn)算。所以我們要找一個(gè)辦法來(lái)避免重復(fù)的運(yùn)算。于是就出現(xiàn)了動(dòng)態(tài)規(guī)劃。簡(jiǎn)單地說(shuō)，動(dòng)態(tài)規(guī)劃依然是把一個(gè)大問(wèn)題分為若干性質(zhì)相同的子問(wèn)題，而這些子問(wèn)題里面會(huì)有若干的重疊。（下面的例題舉例）。為了當(dāng)出現(xiàn)子問(wèn)題重疊的時(shí)候不重復(fù)運(yùn)算。我們就需要把所有的已經(jīng)求出的子問(wèn)題都存下來(lái)，判斷這個(gè)子問(wèn)題是否已經(jīng)算過(guò)，算過(guò)了就不要再算了。如果沒(méi)算過(guò)就算一遍下次在遇到這個(gè)子問(wèn)題就可以不算了。因此我們必須開(kāi)出一個(gè)大小為[1..N,1..N]的數(shù)組來(lái)存儲(chǔ)，又因?yàn)槊看味加锌赡軙?huì)遇到不同的行的子問(wèn)題，所以我們必須把數(shù)組全部留住，所以就不能實(shí)現(xiàn)遞推算法的“滾動(dòng)性”。但動(dòng)態(tài)規(guī)劃算法可以節(jié)省大量的時(shí)間。假設(shè)所有的子問(wèn)題都不重疊它的時(shí)間復(fù)雜度會(huì)和遞歸一樣。而如果優(yōu)有大量的子問(wèn)題重疊，那么會(huì)發(fā)現(xiàn)時(shí)間復(fù)雜度會(huì)有明顯的降低。可以提高運(yùn)算效率，縮短運(yùn)算時(shí)間。

二、???????????用樹(shù)狀圖直觀體現(xiàn)動(dòng)態(tài)規(guī)劃的子問(wèn)題分配

?

（圖一）

?

???????從上面的樹(shù)狀圖我們可以很清楚的看到，每一個(gè)大的問(wèn)題是會(huì)被當(dāng)作樹(shù)根劃分為若干個(gè)子問(wèn)題的，每個(gè)子問(wèn)題又會(huì)作為一個(gè)子樹(shù)的樹(shù)根被劃分為若干個(gè)子問(wèn)題。只有找到最后一層的問(wèn)題時(shí)才會(huì)停止，我們把這樣的最后一層稱(chēng)為“邊界”。一般都是當(dāng)變量為0或1或什么值時(shí)返回一個(gè)固定的值。使用遞歸就要加上一句判斷，如果使用遞推的話就要單獨(dú)初始化，單獨(dú)賦值。

下面就對(duì)典型的例題來(lái)分析貪心法的不足與動(dòng)態(tài)規(guī)劃子對(duì)于重疊子問(wèn)題的計(jì)算。

三、???????????典型例題分析

采藥

(medic.pas/c/cpp)
【問(wèn)題描述】
辰辰是個(gè)天資聰穎的孩子，他的夢(mèng)想是成為世界上最偉大的醫(yī)師。為此，他想拜附近最有威望的醫(yī)師為師。醫(yī)師為了判斷他的資質(zhì)，給他出了一個(gè)難題。醫(yī)師把他帶到一個(gè)到處都是草藥的山洞里對(duì)他說(shuō)：“孩子，這個(gè)山洞里有一些不同的草藥，采每一株都需要一些時(shí)間，每一株也有它自身的價(jià)值。我會(huì)給你一段時(shí)間，在這段時(shí)間里，你可以采到一些草藥。如果你是一個(gè)聰明的孩子，你應(yīng)該可以讓采到的草藥的總價(jià)值最大。”?
如果你是辰辰，你能完成這個(gè)任務(wù)嗎？
【輸入文件】
輸入文件medic.in的第一行有兩個(gè)整數(shù)T（1 <= T <= 1000）和M（1 <= M <= 100），用一個(gè)空格隔開(kāi)，T代表總共能夠用來(lái)采藥的時(shí)間，M代表山洞里的草藥的數(shù)目。接下來(lái)的M行每行包括兩個(gè)在1到100之間（包括1和100）的整數(shù)，分別表示采摘某株草藥的時(shí)間和這株草藥的價(jià)值。
【輸出文件】
輸出文件medic.out包括一行，這一行只包含一個(gè)整數(shù)，表示在規(guī)定的時(shí)間內(nèi)，可以采到的草藥的最大總價(jià)值。
【樣例輸入】
70 3
71 100
69 1
1 2
【樣例輸出】
3
【數(shù)據(jù)規(guī)模】
對(duì)于30%的數(shù)據(jù)，M <= 10；
對(duì)于全部的數(shù)據(jù)，M <= 100。

3、1對(duì)貪心算法的反例

首先我們用貪心的思想來(lái)規(guī)劃這道題的話，我們會(huì)按照順序每次取優(yōu)解假設(shè)我們現(xiàn)在有這樣的一組數(shù)據(jù)：

100 5

50 100

1 50

2 80

1 50

96 50

無(wú)論我們是按照價(jià)值的大小排序還是按照價(jià)值于時(shí)間的比值排序我們都得不到最優(yōu)解。所以，貪心法并不適用于這道題。于是貪心方法被直接PASS。所以我們?cè)囍褂眠f歸和動(dòng)態(tài)規(guī)劃方法來(lái)解決。

3.2對(duì)遞歸遞推算法的數(shù)學(xué)模型介紹

根據(jù)題目我門(mén)可以把總的大問(wèn)題寫(xiě)成一個(gè)函數(shù)F(T,M)。我們可以把這個(gè)函數(shù)這樣定義，F（I,J）表示擁有T時(shí)間，有J個(gè)未采藥材所可以獲得的最大價(jià)值。

如果把函數(shù)像上面的樣子定義的話，很容易我們就可以把一個(gè)大問(wèn)題分解成若干個(gè)性質(zhì)相同的子問(wèn)題，從而我們就可以用地歸和動(dòng)態(tài)規(guī)劃來(lái)解決。這樣呢，我們就可以寫(xiě)出一個(gè)遞歸轉(zhuǎn)移方程，來(lái)解釋F（I,J）

解釋一下，對(duì)于每一個(gè)藥材都有采它所需要的時(shí)間，當(dāng)這個(gè)時(shí)間比整個(gè)子問(wèn)題的J也就是所剩余的時(shí)間要大的時(shí)候我們就沒(méi)有時(shí)間去采這個(gè)藥材，無(wú)論整個(gè)藥材是多么的有價(jià)值。所以，在方程中規(guī)定，只要是a[i-1,j]>j則我們就硬性結(jié)束，直接返回F[i-1,j]的值。當(dāng)這個(gè)采這個(gè)藥材所需要的時(shí)間小于剩余的時(shí)間時(shí)，我們就出現(xiàn)了兩種解決辦法。第一采這個(gè)藥，第二不采。而我們要做的是在這兩個(gè)值里面挑一個(gè)最大的來(lái)作為這個(gè)子問(wèn)題的解。而由于這道題由于藥的順序和不影響最后的解，所以我們可以忽略最后的順序。我們可以從第M個(gè)開(kāi)始一直到第1個(gè)。

3.3?介紹單純遞歸方法的函數(shù)實(shí)現(xiàn)

根據(jù)上面的轉(zhuǎn)移方程我們很容易的就可以寫(xiě)出遞歸函數(shù)

???????示例函數(shù)：

???????Function try1(i,j:Integer):Longint;（*定義函數(shù)*）

Var（*共需要兩個(gè)局部變量*）

????????????max1,max2:Longint;

Begin

????????????If (i=0) Or (j=0) Then Begin（*邊界判斷*）

??????????????????try1:=0;（*滿足邊界則返回0，直接退出*）

???????????????????Exit;

????????????End;

????????????If i>=a[j].t Then max1:=try1(i-a[j].t,j-1)+a[j].v Else max1:=0;（*判斷時(shí)間是否足夠，足夠則求出采這個(gè)藥之后的最大價(jià)值*）

????????????max2:=try1(i,j-1);（*直接求不采的最大價(jià)值，（多說(shuō)下，這里J-1一定不會(huì)減到小于0的情況因?yàn)榍懊嬗羞吔鐥l件限制了）*）

????????????If max1>max2 Then try1:=max1 Else try1:=max2;（*判斷出個(gè)最大值然后返回*）

End;

3.4?解釋單純遞歸方法的計(jì)算浪費(fèi)和效率低的原因

???????根據(jù)上面的轉(zhuǎn)移方程我們假設(shè)樣例為

100 5

1 50

2 80

1 50

50 100

96 50

用樹(shù)狀圖來(lái)表示就會(huì)很清晰

很容易看出來(lái)在這棵樹(shù)的第四層就出現(xiàn)了重復(fù)情況。子問(wèn)題出現(xiàn)了重疊，如果我們這個(gè)樣例的話這棵樹(shù)只有7層。可想而知當(dāng)一個(gè)數(shù)據(jù)M=100的時(shí)候。會(huì)出現(xiàn)多少同樣的情況。如果都算一遍，我們是不是浪費(fèi)了很多很多時(shí)間呢？

???????所以我們才要想辦法避免這種情況的出現(xiàn)，否則很多的時(shí)間都會(huì)浪費(fèi)在“無(wú)用功”上，使得我們程序的效率會(huì)降低很多。很好的一個(gè)解決辦法就是把每次所求出來(lái)的子問(wèn)題的值都用一個(gè)數(shù)組存下來(lái)，這樣我們可以判斷這個(gè)子問(wèn)題是否處理過(guò)，如果處理過(guò)了我們就不要再去處理，如果沒(méi)處理我們就處理它。這就是動(dòng)態(tài)規(guī)劃的思想。所以我們必須要開(kāi)出一個(gè)大小為[0..100,0..1000]的數(shù)組來(lái)存儲(chǔ)這些子問(wèn)題。

3.5??給出動(dòng)態(tài)規(guī)劃方法解決的樣例程序程序

樣例程序解決：

Program medic;

（**************************medic.pas **************************）

（********WangZhe,55^Th?senior high school of Tianjin********）

（**************************2008-8-21***************************）

Type (*定義數(shù)組類(lèi)型，.t表示時(shí)間，.v表示價(jià)值*)

???????????????????re=record

???????????????????????t:Integer;

???????????????????????v:integer;

????????????????????End;

Const (*關(guān)聯(lián)輸入輸出文件*)

????????????Infile='medic.in';

outfile='medic.out';

Var （*變量定義*）

????????????m,t,i:Integer;

??????????data,s:Array[0..100,0..1000] Of integer;（*動(dòng)態(tài)規(guī)劃存儲(chǔ)數(shù)組*）

??????????a:Array[0..100] Of re;（*輸入數(shù)據(jù)數(shù)組*）

Procedure try1(i,j:Integer);（*動(dòng)態(tài)規(guī)劃主過(guò)程*）

Var

max,max1,l:integer;（*所需要的兩個(gè)局部變量*）

Begin

??If (i=0) Or (j=0) Then Begin（*判斷邊界*）

????Data[i,j]:=0;（*處理邊界*）

????Exit;

??End;

??If data[i-1,j]=-1 Then Try1(i-1,j);（*很關(guān)鍵的一步判斷問(wèn)題是否已經(jīng)求過(guò)，其中-1僅僅是一個(gè)空標(biāo)記，因?yàn)檫@道題不可能出現(xiàn)負(fù)值所以我們就定義-1為標(biāo)記，這個(gè)標(biāo)記不一定要用多少只要是解題中不可能出現(xiàn)的標(biāo)記就好*）

??Max:=Data[i-1,j];（*求出不采這個(gè)藥的最大價(jià)值*）

?

??If j>=a[i].t Then Begin（*判斷時(shí)間是否足夠，足夠則求出采這藥的最優(yōu)值*）

????If Data[i-1,j-a[i].t]=-1 Then try1(i-1,j-a[I].t);

Max1:=data[i-1,j-a[i].t]+a[i].v;

Else

??Max1:=0;(*不夠就付個(gè)0就可以了*)

End;

????If max< max1 Then max:=max1;(*判斷出一個(gè)最大值來(lái)*)

??data[i,j]:=max;（*把最大值付給DATA*）

??End;

Begin(*主程序*)

??Assign(input,infile);（*文件關(guān)聯(lián)*）

??Assign(output,outfile);

??reset(input);

??rewrite(output);

??fillchar(data,sizeof(data),$ff);（*數(shù)組清零！這步很重要！！多打幾個(gè)嘆號(hào)！這個(gè)如果不標(biāo)記那么是求不出值的。*）

??readln(t,m);（*讀入兩個(gè)控制值*）

??For i:=1 To m Do readln(a[i].t,a[i].v);（*讀入數(shù)據(jù)*）

??try1(M,t);（*動(dòng)態(tài)規(guī)劃求解*）

??writeln(data[m,t]);（*輸出最優(yōu)解*）

??close(input);（*關(guān)閉文件*）

??close(output)

End.

3.6遞推方法樣例程序的介紹和注釋

從這個(gè)程序和上面給出的遞歸的程序?qū)Ρ纫幌戮涂吹某鰜?lái)，動(dòng)態(tài)規(guī)劃的程序就是加入了一個(gè)存儲(chǔ)和判斷。其他的思想上和數(shù)學(xué)模型上都是一樣的。

???下面給出一個(gè)遞推滾動(dòng)的程序大家對(duì)比看看。（上面注釋過(guò)的我就不注釋了，只注釋出區(qū)別）

Program medic;

Type re=record

?????t:Integer;

?????v:integer;

End;

Const infile='medic.in';

??????outfile='medic2.out';

Var m,t,i,j,n,k,max1:Integer;

????data:Array[0..2,0..1000] Of integer;（*因?yàn)闈L動(dòng)，開(kāi)數(shù)組只需要開(kāi)2個(gè)就行了*）

????a:Array[0..100] Of re;

Begin

??Assign(input,infile);

??Assign(output,outfile);

??reset(input);

??rewrite(output);

??fillchar(data,sizeof(data),$ff);（*可以不清零，不過(guò)保險(xiǎn)起見(jiàn)還是清*）

??readln(t,m);

??For i:=1 To m Do readln(a[i].t,a[i].v);

??For i:=0 To t Do（*處理邊界，也可以叫做“預(yù)處理”*）

????If a[1].t<=i Then Data[1,i]:=a[1].v Else data[1,i]:=0;

??For i:=2 To m Do（*遞推用循環(huán)就可以實(shí)現(xiàn)，不用再寫(xiě)過(guò)程了*）

????For j:=0 To T Do Begin

??????If i mod 2 =1 then n:=1 Else n:=2;（*控制滾動(dòng)，這一步很重要，單數(shù)用1數(shù)組，雙數(shù)用2數(shù)組*）

??????If n=1 Then k:=2 Else k:=1;（*還是滾動(dòng)控制*）

??????Data[n,j]:=Data[k,j];

??????If (j>=a[i].t) Then Begin（*這個(gè)地方的思想是一樣的，判斷時(shí)間是否足夠*）

????????max1:=Data[k,j-a[i].t]+a[i].v;

????????If max1>data[n,j] Then Data[n,j]:=max1;（*求最大值保存*）

??????End;

??End;

??writeln(data[n,t]);

??close(input);

??close(output)

End.

3.7動(dòng)態(tài)規(guī)劃遞歸和遞推方法的區(qū)別與聯(lián)系

從上面的程序我們可以看的出來(lái)數(shù)學(xué)模型上，遞歸遞推沒(méi)有什么區(qū)別，而遞推可以實(shí)現(xiàn)滾動(dòng)，我們可以節(jié)省空間復(fù)雜度，使空間復(fù)雜度降低了50倍。而時(shí)間上勢(shì)必會(huì)多浪費(fèi)些。

【結(jié)語(yǔ)】

???????通過(guò)作者的介紹，我想讀者會(huì)很容易的看出來(lái)這集中方法的區(qū)別和聯(lián)系。從作者自己的經(jīng)驗(yàn)來(lái)講，我覺(jué)得處理一道這樣的題。我們首先要想想是否可以適用貪心算法來(lái)解決，由于貪心算法是“一條鏈”式的處理算法，所以無(wú)論空間復(fù)雜度還是時(shí)間復(fù)雜度都是很低的。拿到一道題我們可以先試著用貪心算法試驗(yàn)一下是否可以用別的反例來(lái)推翻貪心算法。判斷題目不可以用貪心算法來(lái)解決了以后我們就要靜下心來(lái)，再仔細(xì)看一遍題目，總結(jié)遞歸轉(zhuǎn)移方程。因?yàn)榭偨Y(jié)轉(zhuǎn)移方程是解題的最重要的一步。如果你的編程技巧和熟練度足夠的話，只要你的轉(zhuǎn)移方程寫(xiě)對(duì)，剩下來(lái)的就只剩“抄”程序了，會(huì)很快完成題目的。作者也是每年都要參加NOIP的選手，所以我很希望能與各位讀者有交流的機(jī)會(huì)。貼出我的博客，歡迎大家來(lái)交流！http://skysummerice.programfan.com

【特別鳴謝】

感謝天津FNOI的教練藤偉老師給予作者的指導(dǎo)與啟發(fā)

總結(jié)

以上是生活随笔為你收集整理的贪心、递归、递推以及动态规划算法的分析与对比的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。