信息與計算科學(xué)畢業(yè)論文--貪心法及其應(yīng)用

1、<p><b>　　本科畢業(yè)論文</b></p><p>　　論文題目： 貪心法算法及其應(yīng)用 </p><p>　　專業(yè)： 信息與計算科學(xué) </p><p>　　班級：

2、 </p><p>　　學(xué)號： </p><p>　　學(xué)生姓名： </p><p>　　指導(dǎo)教師姓名： <

3、/p><p><b>　　2011年5月</b></p><p><b>　　貪心法及其應(yīng)用</b></p><p><b>　　摘要</b></p><p>　　以貪心法算法理論為背景，依據(jù)貪心法算法的兩個重要性質(zhì)，貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，來解決最小生成樹問題、背包問題、帶

4、有期限的作業(yè)順序問題及刪數(shù)問題，找到具體問題最優(yōu)解。</p><p><b>　　關(guān)鍵字</b></p><p>　　最優(yōu)解近似解； 子問題； 可行解；局部最優(yōu)選擇；整體最優(yōu)解；最優(yōu)子結(jié)構(gòu)； 貪心標(biāo)準(zhǔn)</p><p>　　Greedy method and its application</p><p><b>

5、;　　Abstract</b></p><p>　　Algorithm theory in the context of greedy method, based on greedy method are two important properties of the algorithm, the greedy choice of the nature and properties of the op

6、timal sub-structure to solve the minimum spanning tree problem, knapsack problem, with an operating period of the order of the number of questions and delete questions find the optimal solution of specific problems.</

7、p><p><b>　　朗讀</b></p><p>　　顯示對應(yīng)的拉丁字符的拼音</p><p><b>　　字典</b></p><p><b>　　朗讀</b></p><p>　　顯示對應(yīng)的拉丁字符的拼音</p><p>&l

8、t;b>　　字典</b></p><p><b>　　Keyword</b></p><p>　　Optimal approximate solution；subproblem,；feasible solution； local optimal choice；the overall optimal solution；optimal substruct

9、ure； greedy criteria；mathematical models</p><p><b>　　朗讀</b></p><p>　　顯示對應(yīng)的拉丁字符的拼音</p><p><b>　　字典</b></p><p><b>　　目錄</b></p>&

10、lt;p>　　緒論…………………………………………………………………………………………1</p><p>　　一、貪心算法的背景及理論依據(jù)…………………………………………………………1</p><p>　　二、貪心算法解題思路……………………………………………………………………1</p><p>　　三、實現(xiàn)該算法的過程……………………………………………………

11、………… 1</p><p>　　四、貪心算法的性質(zhì)…………………………………………………………………2</p><p>　　五、運用貪心法解決具體問題……………………………………………………………3</p><p>　　六、總結(jié)……………………………………………………………………………………9</p><p>　　致謝……………………………

12、……………………………………………………………9</p><p>　　參考文獻………………………………………………………………………………9</p><p>　　緒論：主要是根據(jù)貪心法算法的解題思路及具體實現(xiàn)算法的過程，解決涉及到該算法的幾個具體實際問題，從中找到解決問題的整體最優(yōu)解或是整體最優(yōu)解的近似解，最后總結(jié)貪心算法的思想---只顧眼前利益，每次都是選最好的。</p>

13、<p>　　一、貪心算法的背景及理論依據(jù)</p><p>　　貪心算法（又稱貪婪算法）是指，在對問題求解時，總是做出在當(dāng)前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。它省去了為查找最優(yōu)解而去窮盡所有可能而耗費的大量時間。</p>&

14、lt;p>　　二、貪心算法解題思路</p><p>　　1.建立數(shù)學(xué)模型來描述問題。 </p><p>　　2.把求解的問題分成若干個子問題。 </p><p>　　3.對每一子問題求解，得到子問題的局部最優(yōu)解。 </p><p>　　4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。 </p><p>　　三、

15、實現(xiàn)該算法的過程 </p><p>　　1.從問題的某一初始解出發(fā)； </p><p>　　2.while 能朝給定總目標(biāo)前進一步 </p><p>　　3.do 求出可行解的一個解元素； </p><p>　　4.由所有解元素組合成問題的一個可行解。 </p><p><b>　　四、貪心算法的性質(zhì)<

16、/b></p><p><b>　　1、貪心選擇性質(zhì)</b></p><p>　　所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。在動態(tài)規(guī)劃算法中，每步所做的往往依賴于相關(guān)子問題的解。因而只有在解出相關(guān)子問題后，才能做出選擇。而在貪心算法中，僅在當(dāng)前狀態(tài)

17、下做出最好選擇，即局部最優(yōu)選擇。然后再去解作出這個選擇后產(chǎn)生的相應(yīng)的子問題。</p><p>　　貪心算法所作的貪心選擇可以依賴于以往所做過的選擇，但決不依賴于將來所做的選擇，也不依賴于子問題的解。正是由于這種差別，動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式做出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為一個規(guī)模更小的子問題。</p><

18、;p>　　對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所做出的貪心選擇最終導(dǎo)致問題的一個整體最優(yōu)解。通?？梢杂梦覀冊谧C明活動安排問題的貪心選擇性質(zhì)時所采用的方法來證明。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。而且作了貪心選擇后，原問題簡化為一個規(guī)模更小的類似子問題。然后，用數(shù)學(xué)歸納法證明，通過每一步作貪心選擇，最終得到一個整體最優(yōu)解。其中，證明貪心選擇后的問題就簡化為規(guī)模更小

19、的類似子問題的關(guān)鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。</p><p><b>　　2、最優(yōu)子結(jié)構(gòu)性質(zhì)</b></p><p>　　當(dāng)一個問題的最優(yōu)解包括著它的子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題所具有的這個性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的一個關(guān)鍵特征。</p><p>　　五、運用貪心法解決具體問題</p>

20、<p><b>　　1、最小生成樹問題</b></p><p>　　(1)問題描述及分析</p><p>　　討論無向圖的最小生成樹問題。構(gòu)造最小生成樹可以有多種算法，其中大多數(shù)構(gòu)造算法都是利用了最小生成樹的下述性質(zhì)：設(shè)G = (V, E) 是一個連通網(wǎng)絡(luò)，U是頂點集V的一個真子集。</p><p>　　若（u, v）是G中所有的一

21、個斷電在U（即u∈U）里、另一個端點不再U（即v∈V-U）里的邊中，具有最小權(quán)值的一條邊，則一定存在G的一棵最小生成樹包括邊（u, v）。這個性質(zhì)稱為MST性質(zhì)。</p><p>　　MST性質(zhì)可用反證法證明：假設(shè)G的任何一顆最小生成樹總都不包含邊（u，v）。設(shè)T是G的一顆最小生成樹，但不包含邊（u, v）。由于T是樹，且是連通的，因此有有一條u到v的路徑；且該路徑上必有一條連接兩個頂點集Ｕ和Ｖ－Ｕ的邊（u`,v

22、`）,其中u`∈U,v`∈V-U,否則u和v不連通。當(dāng)把邊（u, v）加入樹T時，得到一個包含有邊（u, v）的回路，見圖1。刪去邊（u`, v`）,上述回路即被消除，由此得到另一顆生成樹T`,T`和T的區(qū)別僅在于用邊（u, v）取代了T中的邊（u`,v`）。因為（u, v）的權(quán)<=(u`, v`)的權(quán)，故T`的權(quán)<=T的權(quán)，因此T`也是G的最小生成樹，它包含邊（u, v）,與假設(shè)矛盾！</p><p&g

23、t;　　那么如何利用MST性質(zhì)來構(gòu)造最小生成樹呢？下面我們介紹prim這樣的一中貪心算法</p><p>　　圖（1） 包含邊（u，v）的回路</p><p><b>　　(2)算法描述</b></p><p>　　假設(shè)G = (V, E)是連通網(wǎng)絡(luò)，為簡單起見，我們用序號1至 n來表示頂點集合，即V = ｛1，2，… ，n｝。設(shè)所求的最小生成

24、樹為T = （U , TE）,其中U是T的頂點集，TE 是T的邊集。并且將G中邊上的權(quán)看做是長度。</p><p>　　Prim算法的基本思想是：首先從V中人去一個頂點u。，將生成樹T置為僅有一個結(jié)點u。的樹，即置U = ｛ u。｝；然后只要U是V的真子集，就在所有那些其一個端點u已在T，另一個端點v還未在T的邊中，找一條最短的邊（u，v），并把該條邊（u, v）和其不在T中的頂點v,分別并入T的邊集TE和頂點集

25、U。如此進行下去，每次往生成樹里并入一個頂點和一條邊，知道哦啊把所有頂點包括進生成樹T為止。此時，必有U = V ,TE 中有n-1條邊。MST性質(zhì)保證上述過程求的的T = (U ,TE)是G的一顆最小生成樹。于是不難推出完整的算法。</p><p><b>　　算法程序如下：</b></p><p><b>　　PRIM( )</b><

26、/p><p><b>　　{ </b></p><p>　　int j，k, m, v, min, max =10000；</p><p><b>　　float d；</b></p><p><b>　　edge e；</b></p><p>　　for

27、(j =1； j<n；j++)</p><p><b>　　{ </b></p><p>　　T[j-1]. Formvex =1 ；</p><p>　　T[j-1].endvex = j+1；</p><p>　　T[j-1].length = dist[0] [j ]；</p><p>

28、;<b>　　}</b></p><p>　　for(k =0； k< n- 1； k++)</p><p><b>　　{ </b></p><p>　　min = max；</p><p>　　for ( j =k ； j<n-1； k++)</p><p&

29、gt;　　if (T[ j ].length<min)</p><p><b>　　{</b></p><p>　　min = T[ j].length；</p><p><b>　　m = j ；</b></p><p><b>　　}</b></p>&

30、lt;p>　　e = T[ m ]； T[ m] = T [ k ]； T[ k ]= e；</p><p>　　V = T[ k].endvex；</p><p>　　for (j=k+1； j<n-1； j++)</p><p><b>　　{</b></p><p>　　d= dist [v-1] [T

31、[j] .endvex-1 ]；</p><p>　　if(d<T[ j]. length)；</p><p><b>　　{</b></p><p>　　T[j].length = d；</p><p>　　T [j].fromvex = v；</p><p><b>　　}&l

32、t;/b></p><p><b>　　}</b></p><p><b>　　}</b></p><p><b>　　}</b></p><p>　　2、背包問題(1)問題描述及分析</p><p>　　我們試著用貪心算法來解決背包問題。己知一

33、個容量為weight的背包?，F(xiàn)在要從n種物品中選取若干裝入背包中，每種物品的重量為w(i) 、價值為p(i) 。定義一種可行的背包裝載為：背包中物品的總重量不能超過背包的容量，并且一個物品要么全部選取，要么不選取。采取怎樣的裝包方案才會使裝入背包的物品總效益值最大?  </p><p><b>　　(2)算法描述</b></p><p&g

34、t;　　如果所有重量的總和小于等于m，那么x(i)=1(1<=i<=n)為最優(yōu)解。另外，所有最優(yōu)解都使得背包剛好填滿?？偪梢岳^續(xù)填充一些物品i直到總重量恰好等于m。注意到背包問題要求選擇物品的子集，因此滿足子結(jié)構(gòu)模式。下面找一個算法，以試圖在價值提高率和容量使用率之間達到一個平衡。每一步填充的物品使得每占用單位容量帶來最大價值。這就意味著物品按p(i)/w(i)的比列順序進行填充。如果物品已經(jīng)以p(i)/w(i) 的非遞增順

35、序進行排序方式，那么GreedyKnapsack函數(shù)應(yīng)用這種策略得到解。</p><p><b>　　下面是算法程序。</b></p><p>　　Void Greedyknapsack(float m， int n)</p><p>　　p[1: n] and w[1:n] contain the profits and weig

36、hts</p><p>　　//respectively of the n objects orderd such that</p><p>　　//p[i]/w[i] >=p[i+1]/w[i+1] .m is the knapsack</p><p>　　//size and x[1:n] is the solution vector.</p&

37、gt;<p><b>　　{</b></p><p>　　for (int i=1；i<=n；i++)</p><p><b>　　x[i]=0.0；</b></p><p>　　initialize x；</p><p>　　float U = m；</p>&l

38、t;p>　　for(i=1；i<=n；i++)</p><p><b>　　{</b></p><p>　　if (w[i] >U) break；</p><p>　　x[i] =1.0；</p><p><b>　　u=w[i]；</b></p><p>

39、;<b>　　}</b></p><p><b>　　}</b></p><p>　　3、帶有期限的作業(yè)順序問題(1)問題描述及分析</p><p>　　給定一個有n項作業(yè)的集合。處理時間ti和di 與每項作業(yè)i關(guān)聯(lián)。一個可行解是作業(yè)的一個排列使得作業(yè)按照順序進行處理，且每項作業(yè)按時完成。定義一個貪心調(diào)度使得作業(yè)按照期限

40、的非遞減順序進行處理。證明存在一個可行性調(diào)度，那么所有的貪心調(diào)度都是可行解。</p><p><b>　　(2)算法描述：</b></p><p>　　Void FJS (int d [ ]，int n， int b，int j [ ])</p><p>　　//find an optiomal solution J [1: K]. It i

41、s assumed that </p><p>　　//p[1] >= p [2] >=…>=p[n] and that b = min{n, max(d[i])}.</p><p><b>　　{ </b></p><p>　　//initially there are b+1 single node trees.</

42、p><p>　　sets set(b)；</p><p>　　for (int i=0; i<=b;i++ )</p><p><b>　　f[i] = i；</b></p><p>　　int k = 0；</p><p>　　//initialize.</p><p>

43、;　　for(i=1; i<n; i++ )</p><p><b>　　{</b></p><p>　　//ude greedy rule .</p><p>　　int q = set.Collapsingfind(min(n, d[i]));</p><p><b>　　if (f[q])</

44、b></p><p><b>　　{</b></p><p><b>　　k++；</b></p><p><b>　　j[k] = I；</b></p><p>　　//select job i.</p><p>　　int m = set.co

45、llapsingfind(f[q]-1)；</p><p>　　set.weightedunion(m ,q)；</p><p>　　f [q] = f[m]；</p><p>　　//q maybe new root.</p><p><b>　　}</b></p><p><b>　

46、　}</b></p><p><b>　　}</b></p><p>　　4、刪數(shù)問題:（1）問題描述及分析：鍵盤輸入一個高精度的正整數(shù)N（此整數(shù)中沒有‘0’），去掉其中任意S個數(shù)字后剩下的數(shù)字按原左右次序?qū)⒔M成一個新的正整數(shù)。編程對給定的N和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。 　　輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)。（N不超過

47、240位） 　　輸入數(shù)據(jù)均不需判錯。 （2）算法描述://代碼(C++) #include <iostream.h> #include <string.h> int main() { char a[241]; int s; int i,j,k; int f

48、lag[241]; int flag2; cin>>a; cin>>s; for (i=0;i<strlen(a);i++) flag[i]=1; for (i=0;i<s;i++) { flag2=1; for (j=0

49、;j<</p><p><b>　　六、總結(jié) </b></p><p>　　貪心法(greedy method)就是只顧眼前利益，每次都選最好的。  </p><p><b>　　１、解向量 </b></p><p>　　把可行解寫成一個N元組的形式，就是解向量。 <

50、/p><p><b>　　2、貪心標(biāo)準(zhǔn) </b></p><p>　　就是眼前“最好”的標(biāo)準(zhǔn)。例如《背包問題》，標(biāo)準(zhǔn)可以是價值，重量或“性價比” </p><p><b>　　3、貪心算法 </b></p><p>　　對于解向量的每一維，用貪心標(biāo)準(zhǔn)在所有可能值中選擇一個加入到解向量中。 </p&

51、gt;<p>　　4、什么樣的問題可以考慮用貪心？ </p><p>　　貪心選擇性質(zhì)：選擇具有無后效性，即不依賴與以后將要作出的選擇。 </p><p>　　最優(yōu)子結(jié)構(gòu)：全局最優(yōu)包含局部最優(yōu)。</p><p>　　致謝：此片論文得以完成,首先要感謝xx老師的細心指導(dǎo)。xx老師開闊的視野，為我提供了極大的發(fā)揮空間，在這段時間里讓我明白了做任何事情要嚴謹

52、細致、一絲不茍，對人要寬容、寬厚，xx老師寬厚待人的學(xué)者風(fēng)范更是令我無比感動。</p><p>　　感謝各位老師在這幾年一直在生活中、組織上給予我的教導(dǎo)和無私的幫助，讓我在上饒師范學(xué)院這個大舞臺上有鍛煉的能力、自我完善的平臺。在此文即將完成之際，我衷心的感謝在此過程中幫助過我的每個人，在這里請接收我最誠摯的謝意！</p><p><b>　　參考文獻</b></