算法設(shè)計(jì)和分析課程論文

1、湖南理工學(xué)院課程論文論文題目 貪心法的應(yīng)用 課程名稱(chēng) 算法設(shè)計(jì)與分析 姓 名 學(xué) 號(hào) 專(zhuān) 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 年 級(jí) 學(xué) 院 計(jì)算機(jī) 日期（2014年4月10日） 課程論文評(píng)價(jià)標(biāo)準(zhǔn)指標(biāo)評(píng)價(jià)內(nèi)容評(píng)價(jià)等級(jí)（分值）得分ABCD選題選題是否新穎；是否有意義；是否與本門(mén)課程相關(guān)。20-1615-1110-65-0論證思路是否清晰；邏輯是否嚴(yán)密；結(jié)構(gòu)是否嚴(yán)謹(jǐn)；研究方法是否得當(dāng)；論證是否充分。20-1615-1110-65-0文獻(xiàn)文獻(xiàn)資料是否翔實(shí)；是否具有代表性。20-1615-1110-65-0規(guī)范文字表達(dá)是否準(zhǔn)確、流暢；是否符合學(xué)術(shù)道德規(guī)范。20-1615-1110-65-0能力是否運(yùn)用了本門(mén)課程的有

2、關(guān)理論知識(shí)；是否體現(xiàn)了科學(xué)研究能力。20-1615-1110-65-0 評(píng)閱教師簽名： 年 月 日 總分： 貪心法的應(yīng)用摘要：在解決問(wèn)題的過(guò)程中，通過(guò)逐步獲得最優(yōu)解從而獲得整體最優(yōu)解的策略就是貪心策略，在已經(jīng)學(xué)會(huì)在解的范圍可以確定的情況下，可以采用枚舉或遞歸策略，一一比較它們最后找到最優(yōu)解；但當(dāng)解的范圍非常大時(shí)，枚舉和遞歸的效率會(huì)非常低。這時(shí)就可以考慮用貪心策略。貪心算法沒(méi)有固定的框架，算法設(shè)計(jì)的關(guān)鍵是貪心策略的選擇，貪心策略要具有無(wú)后向性，即某階段狀態(tài)一旦確定以后，不受這個(gè)狀態(tài)以后的策略的影響。當(dāng)一個(gè)問(wèn)題有好幾種解決方法時(shí)，貪心法應(yīng)該是最好的選擇之一。本文講述了貪心算法的含義、基本思路以及貪

3、心算法在實(shí)例中的應(yīng)用。關(guān)鍵詞：貪心算法；刪數(shù)問(wèn)題；最小生成樹(shù)1、 引言在平時(shí)解決問(wèn)題的過(guò)程中，當(dāng)一個(gè)問(wèn)題就有無(wú)后向性和貪心選擇性質(zhì)時(shí)，貪心算法通常會(huì)給出一個(gè)簡(jiǎn)單、直觀和高效的解法。貪心算法通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解。它所做的每一個(gè)選擇都是當(dāng)前狀態(tài)下就有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問(wèn)題化解為一個(gè)更小的與原問(wèn)題具有相同形式的子問(wèn)題。盡管貪心算法對(duì)于很多問(wèn)題不能總是產(chǎn)生整體最優(yōu)解，但對(duì)于最短路徑、最小生成樹(shù)問(wèn)題，以及刪數(shù)問(wèn)題等卻可以獲得整體最優(yōu)解，而且所給出的算法一般比動(dòng)態(tài)規(guī)劃算法更為簡(jiǎn)單、直觀和高效。2、 貪心算法的含義和特點(diǎn)（1） 貪心算法的含義 貪心算法是通過(guò)

4、一系列的選擇來(lái)得到問(wèn)題解的過(guò)程。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法，它總是做出在當(dāng)前看來(lái)是最有的選擇，也就是說(shuō)貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解算法。（2） 貪心算法的特點(diǎn) 1、從全局來(lái)看，運(yùn)用貪心策略解決的問(wèn)題在程序運(yùn)行過(guò)程中無(wú)回溯過(guò)程，后面的每一步都是當(dāng)前看似最佳的選擇，這種選擇依賴(lài)已作出的選擇，但并不依賴(lài)未作出的選擇。 2、不能保證最后求出的解是最佳的。由于貪心策略總是采用從局部看來(lái)是最優(yōu)的選擇 ，并不從整體上加以考慮 。另外貪心算法只能用來(lái)求某些最大或最小解的問(wèn)題，因?yàn)楫?dāng)遇到求解權(quán)值最小路徑等問(wèn)題采用貪心算法得到的結(jié)果并不

5、是最佳。2、 貪心算法在實(shí)例中的應(yīng)用（1） 刪數(shù)問(wèn)題給定n位正整數(shù)a，去掉其中任意k個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的位正整數(shù)和正整數(shù)，設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。、 算法原理從最高位開(kāi)始，依次向低位搜索，一旦遇到前一位（高數(shù)）的數(shù)大于當(dāng)前位，則刪去前一位，直到刪除個(gè)數(shù)，如果到達(dá)末尾還沒(méi)有刪除個(gè)，則說(shuō)明現(xiàn)在這個(gè)數(shù)已經(jīng)是從小到大排列了，則從最低位開(kāi)始刪除要求的位數(shù)。、 過(guò)程分析 k=3比大刪除比大刪除 6比3大刪除 只看這個(gè)實(shí)例，有可能歸納不出正確的算法，看下一個(gè)實(shí)例，再進(jìn)一步解釋。 n2=2 k=33比1大刪除 2 2比1大刪除 8比3大刪除

6、由實(shí)例n1，相鄰數(shù)字只需從前向后比較；而從實(shí)例n2 中可以看出當(dāng)?shù)趇位與第i+1位比較，若刪除第i位后，必須向前考慮第i-1位與第i+1位進(jìn)行比較，才能保真結(jié)果的真確性。（2） 最小生成樹(shù)設(shè)G = (V, E)是一個(gè)無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E的每條邊(v, w)的權(quán)為cvw。如果G的一個(gè)子圖G是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G為G的生成樹(shù)。生成樹(shù)的各邊的權(quán)的總和稱(chēng)為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱(chēng)為G的最小(優(yōu))生成樹(shù)。1、 算法原理（1） Prim算法 基本思想：在保證連通的前提下依次選出權(quán)重較小的n 1條邊。G=(V, E)為無(wú)向連通帶權(quán)圖，令V=1, 2, ,

7、n。設(shè)置一個(gè)集合S ，初始化S = 1，T = 。貪心策略：如果VS中的頂點(diǎn)j與S中的某個(gè)點(diǎn)i連接且(i, j)是E中的權(quán)重最小的邊，于是就選擇j(將j加入S)，并將(i, j) 加入T中 。重復(fù)執(zhí)行貪心策略，直至VS為空。（2） Kruskal算法 基本思想：在保證無(wú)回路的前提下依次選出權(quán)重較小的n 1條邊。 貪心策略：如果(i, j)是E中尚未被選中的邊中權(quán)重最小的，并且(i, j)不會(huì)與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇 (i, j)。若邊(i, j) 的兩個(gè)端點(diǎn)i和j屬于同一個(gè)連通分支，則選擇(i, j) 會(huì)造成回路，反之則不會(huì)造成回路。因此初始時(shí)將圖的n個(gè)頂點(diǎn)看成n個(gè)孤立分支。（3）

8、兩種算法的異同兩種算法不同之處在于，Prim算法是在在保證連通的前提下依次選出權(quán)重較小的n 1條邊。而Kruskal算法在保證無(wú)回路的前提下依次選出權(quán)重較小的n 1條邊。兩種算法的相同之處在于都是在各自的前提條件下采取依次取出權(quán)值最小n-1條邊的貪心策略。2、分析過(guò)程（1）Prim算法給定一個(gè)聯(lián)通帶權(quán)圖如下： 初始時(shí)S=1，T= ；第一次選擇：(1,3)權(quán)最小， S=1,3， T= (1,3) ；第二次選擇：(3,6)權(quán)最小， S=1,3,6， T= (1,3)（3,6） ；第三次選擇：(4,6)權(quán)最小， S=1,3,6,4， T= (1,3)（3,6）（6,4） ；第四次選擇：(2, 3)權(quán)

9、最小， S=1,3,6,4,2， T= (1,3)（3,6）（6,4）（2,3） ；第五次選擇：(2,5)權(quán)最小， S=1,3,6,4,2,5， T= (1,3)（3,6）（6,4）（2,3）（2,5） ；（2） Kruskal算法 給定一個(gè)聯(lián)通帶權(quán)圖如下： 初始時(shí)為六個(gè)孤立的點(diǎn)，選擇了1，于是1、3點(diǎn)合并為同一個(gè)集合；選擇了2，于是4、6點(diǎn)合并為同一個(gè)集合；選擇了3，于是2、5點(diǎn)合并為同一個(gè)集合；選擇了4，于是1、3、4、6點(diǎn)合并為同一個(gè)集合；考察邊5，因?yàn)?、4為同一集合，故被放棄；選擇了6，于是1、3、4、6、2、5點(diǎn)合并為同一個(gè)集合；選擇了1，于是1、3點(diǎn)合并為同一個(gè)集合；已經(jīng)選擇邊了

10、n1條邊，算法結(jié)束。結(jié)果如圖所示： 3、 算法設(shè)計(jì)（1） Prim算法Prim(int n, Type *c) int j = 1; sj = true; /初始化將節(jié)點(diǎn)1放入s并初始化closest和lowcostfor (int i = 2; i = n; i+) closesti = 1; lowcosti=c1i; si=false;for (int i = 1; i n; i+) / /執(zhí)行以下操作n-1次 min= inf; for (int k = 2; k = n; k+) /依據(jù)lowcost找出與s最近的點(diǎn)j并放入S if (lowcostkmin&!sk) min = l

11、owcostk; j = k sj = true; for (int k = 2; k = n; k+) /調(diào)整closest和lowcost if (cjk lowcostk&!sk) lowcostk = cjk; closestk = j （2） Kruskal算法 Kruskal(int n, *e) Sort(e, w); /將邊按權(quán)重從小到大排序 initialize(n); /初始時(shí)每個(gè)頂點(diǎn)為一個(gè)集合 k = 1; /k累計(jì)已選邊的數(shù)目， j = 1; /j為所選的邊在e中的序號(hào) while (k n) /選擇n 1條邊 a = Find(eju); b = Find(ejv);

12、 /找出第j條邊兩個(gè)端點(diǎn)所在的集合 if (a != b) tk+ = j; Union(a, b) /若不同，第j條邊放入樹(shù)中并合并這兩個(gè)集合 j+ /繼續(xù)考察下一條邊4、 Prim和kruskal算法兩者的復(fù)雜性 Prim算法為兩重循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)為O(n)，因此其復(fù)雜性為O(n2)。Kruskal算法中，設(shè)邊數(shù)為e，則邊排序的時(shí)間為O(e)，確定邊的時(shí)間為O(loge)，所以整個(gè)時(shí)間復(fù)雜性為O(eloge)。當(dāng)e = (n2)時(shí)，Kruskal算法要比Prim算法差；當(dāng)e = (n2)時(shí)，Kruskal算法比Prim算法好得多。3、 總結(jié)與展望（一）總結(jié) 貪心算法是很常見(jiàn)的

13、算法，貪心策略是最接近人的日常思維的一種解題策略，雖然它不能保證求得的最后解一定是最佳的，但是它可以為某些問(wèn)題確定一個(gè)可行性范圍。貪心算法所作的選擇依賴(lài)于以往所作過(guò)的選擇，但決不依賴(lài)于將來(lái)的選擇，這使得算法在編碼和執(zhí)行過(guò)程中都有一定的速度優(yōu)勢(shì)。對(duì)于一個(gè)問(wèn)題的最優(yōu)解只能用窮舉法得到時(shí)，用貪心算法是尋找問(wèn)題最優(yōu)解的較好算法。對(duì)一個(gè)問(wèn)題可以同時(shí)用幾種方法解決，貪心算法并不是對(duì)所有的問(wèn)題都能得到整體最優(yōu)解或是最理想的近似解時(shí)，就需判斷貪心性質(zhì)的正確性了。與回溯法、動(dòng)態(tài)規(guī)劃法等比較，它的適用區(qū)域相對(duì)狹窄許多?？傊绻粋€(gè)貪心解決方案存在，就可以使用它。 （二）展望對(duì)于貪心算法的應(yīng)用，如果某個(gè)問(wèn)題具有貪心算法的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，那么，它就可以采用貪心策略進(jìn)行分析，進(jìn)而求解，貪心算法的應(yīng)用舉例不僅只有本論文中的那幾個(gè)，他對(duì)于背包問(wèn)題、最優(yōu)裝載問(wèn)題、硬幣找錢(qián)問(wèn)題等都是十分方便有效的算法，貪心算法在科學(xué)計(jì)算和工程中的應(yīng)用也越來(lái)越廣泛，例如用貪心算法進(jìn)行三角剖分的指紋匹配方法、