(精品論文)貪心算法論文終稿

本科畢業(yè)論文（設計）題 目 貪心算法設計及其實際應用研究 系 別 信 息 管 理 系 專 業(yè) 計算機科學與技術 年 級 2006級 學 號 222006602054062 姓 名 蔣 遠 麗 指 導 教 師 汪 維 清 成 績 _ 二一年五月十五日 nn目 錄西南大學本科畢業(yè)論文（設計）任務書I文獻綜述i西南大學本科畢業(yè)論文（設計）開題報告- 1 -正文1摘要1第1章 引言21.1研究背景21.2研究內(nèi)容21.3研究目標21.4研究意義21.5 本文組織3第2章 貪心算法的基本知識概述42.1 貪心算法定義42.2 貪心算法的基本思路及實現(xiàn)過程42.3貪心算法的核心42.4貪心算法的基本要素52.5 貪心算法的理論基礎62.6貪心算法存在的問題7第3章 經(jīng)典問題解決及其優(yōu)缺點83.1 哈夫曼編碼83.2單源最短路徑問題(Dijkstra算法)103.3最小生成樹問題(Prim算法、Kruskal算法)12第4章 多處最優(yōu)服務次序問題154.1 問題的提出154.2 貪心選擇策略154.3 問題的貪心選擇性質(zhì)154.4 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)154.5 算法結(jié)果分析16第5章 刪數(shù)問題175.1 問題的提出175.2 貪心算法策略175.3 問題的貪心選擇性質(zhì)175.4 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)175.5 編碼18第6章 汽車加油問題196.1 問題的提出196.2 編碼分析196.3 貪心算法策略196.4 貪心算法正確性證明206.5 貪心算法時間復雜度分析20第7章 最優(yōu)合并問題217.1 問題的提出217.2 原理分析217.3 算法時間復雜度分析21第8章 會場安排問題228.1 問題的提出228.2 編碼分析228.3 貪心算法228.4 最優(yōu)解證明238.5 算法時間復雜度分析23第9章 貪心算法的C+實現(xiàn)249.1 C+語言概述249.2 具體實現(xiàn)步驟259.3程序編碼與程序調(diào)試29第10章 總結(jié)與展望3110.1總結(jié)3110.2展望31參考文獻32附錄33致謝41本科畢業(yè)論文（設計）指導教師評閱表a本科畢業(yè)論文（設計）交叉評閱表b本科畢業(yè)論文（設計）答辯記錄c西南大學本科畢業(yè)論文（設計）任務書論文（設計）題目 貪心算法設計及其實際應用研究 系別、專業(yè) 信息管理系計算機科學與技術 學生姓名 蔣遠麗 學號 222006602054062 指導教師姓名 汪維清 開題日期 2009年11月28日 論文（設計）的主要內(nèi)容（技術指標）與要求：本文講述了貪心算法的含義、基本思路及實現(xiàn)過程，貪心算法的核心、基本性質(zhì)、特點及其存在的問題。并通過貪心算法的性質(zhì)，通過研究幾個經(jīng)典問題，將貪心算法應用到實際中。進 度 安 排研究進度安排：2009年10月-2009年11月，根據(jù)課題研究的內(nèi)容，收集資料2009年11月- 2009年12月，深入探討該算法中的幾個經(jīng)典問題2009年12月- 2010年1月，整理研究內(nèi)容，并作進一步的修改2010年1月- 2010年2月，歸納總結(jié)，形成一份完整的課題論文系意見：注：1、任務書由指導老師填寫。 2、任務書必須在第七學期13周前下達給學生。文獻綜述貪心算法設計及其實際應用研究蔣遠麗西南大學榮昌校區(qū)信息管理系，重慶榮昌 402460摘 要：在求最優(yōu)解問題的過程中，依據(jù)某種貪心標準，從問題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過若干次的貪心選擇，最終得出整個問題的最優(yōu)解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問題自身的特性決定了該題運用貪心算法可以得到最優(yōu)解。貪心算法所作的選擇可以依賴于以往所作過的選擇，但決不依賴于將來的選擇，也不依賴于子問題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢。如果一個問題可以同時用幾種方法解決，貪心算法應該是最好的選擇之一。本文講述了貪心算法的含義、基本思路及實現(xiàn)過程，貪心算法的核心、基本性質(zhì)、特點及其存在的問題。并通過貪心算法的特點舉例列出了以往研究過的幾個經(jīng)典問題，對于實際應用中的問題，也希望通過貪心算法的特點來解決。關鍵詞：貪心算法；哈夫曼編碼；最小生成樹；多處最優(yōu)服務次序問題；刪數(shù)問題0 引言為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實際問題，計算機算法學得到了飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型紛紛運用到計算機算法學中，產(chǎn)生了解決各種現(xiàn)實問題的有效算法。雖然設計一個好的求解算法更像是一門藝術而不像是技術 ,但仍然存在一些行之有效的、能夠用于解決許多問題的算法設計方法 ,你可以使用這些方法來設計算法 ,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對算法進行細致的調(diào)整。但是在某些情況下,算法經(jīng)過調(diào)整之后性能仍無法達到要求,這時就必須尋求另外的方法來求解該問題。當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時，貪心算法通常會給出一個簡單、直觀和高效的解法。貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是在當前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問題化簡為一個更小的與原問題具有相同形式的子問題。盡管貪心算法對許多問題不能總是產(chǎn)生整體最優(yōu)解，但對諸如最短路徑問題、最小生成樹問題，以及哈夫曼編碼問題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動態(tài)規(guī)劃算法更加簡單、直觀和高效。（1）基本知識貪心算法的含義貪心算法是通過一系列的選擇來得到問題解的過程。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級處理方法，它總是做出在當前看來是最優(yōu)的選擇，也就是說貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解算法。（2）貪心算法特點及存在的問題1)貪心算法的特點從全局來看，運用貪心策略解決的問題在程序的運行過程中無回溯過程，后面的每一步都是當前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。2)貪心算法存在的問題不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來是最優(yōu)的選擇，因此并不從整體上加以考慮。 貪心算法只能用來求某些最大或最小解的問題。例如找零錢問題要求得到最小數(shù)量，就可以采用貪心算法，但是在另外一個求解權值最小路徑時采用貪心算法得到的結(jié)果并不是最佳。 貪心算法只能確定某些問題的可行性范圍。（3）經(jīng)典問題解決及其優(yōu)缺點1）哈夫曼編碼問題提出：哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式?；驹恚簩γ恳粋€字符規(guī)定一個0，1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡單。由于任一字符的代碼都不是其他字符代碼的前綴，從編碼文件中不斷取出代表某一字符的前綴碼，轉(zhuǎn)換為原字符，即可逐個譯出文件中的所有字符?？梢杂枚鏄渥鳛榍熬Y編碼的數(shù)據(jù)結(jié)構(gòu)。在表示前綴碼的二叉樹中，樹葉代表給定的字符，并將每個字符的前綴碼看做是從樹根到代表該字符的樹葉的一條道路。代碼中每一位的0或1分別作為指示某結(jié)點到左兒子或右兒子的“路標”。優(yōu)點：哈夫曼編碼是無損壓縮當中最好的方法。它使用預先二進制描述來替換每個符號，長度由特殊符號出現(xiàn)的頻率決定。常見的符號需要很少的位來表示，而不常見的符號需要很多位來表示。哈夫曼算法在改變?nèi)魏畏柖M制編碼引起少量密集表現(xiàn)方面是最佳的。然而，它并不處理符號的順序和重復或序號的序列。缺點：慢位流實現(xiàn)相當慢的解碼（比編碼慢）最大的樹深度是32（編碼器在任何超過32位大小的時候退出）。2）單源最短路徑問題提出：給定帶權有向圖G=(V,E)，其中每條邊的權是非負實數(shù)。另外，還給定V中的一個頂點，稱為源?，F(xiàn)在要計算從源到所有其它各頂點的最短路長度。這里路的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。Dijkstra算法基本思想：設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，數(shù)組dist就記錄了從源到所有其它頂點之間的最短路徑長度。優(yōu)點：Dijkstra的思想是按遞增長度來產(chǎn)生路徑,每次選出當前已經(jīng)找到的最短的一條路徑,它必然是一條最終的最短路徑。因此每次找出當前距離數(shù)組中最小的,必然是一條最終的最短路徑缺點：對于具有n個頂點和e條邊的帶權有向圖，如果用帶權鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要O(n)時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O（n2）時間。算法的其余部分所需要時間不超過O（n2）。3）最小生成樹問題提出：設G=(V,E)是無向連通帶權圖，即一個網(wǎng)絡。E中每條邊(v,w)的權為cvw。如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹上各邊權的總和稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。Prim算法基本思想：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jv-s，且cij最小的邊，將頂點j添加到S中。這個過程一直進行到S=V時為止。在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。優(yōu)點：該算法的特點是當前形成的集合T始終是一棵樹。將T中U和TE分別看作紅點和紅邊集，V-U看作藍點集。算法的每一步均是在連接紅、藍點集的紫邊中選擇一條輕邊擴充進T中。MST性質(zhì)保證了此邊是安全的。T從任意的根r開始，并逐漸生長直至U=V，即T包含了C中所有的頂點為止。MST性質(zhì)確保此時的T是G的一棵MST。因為每次添加的邊是使樹中的權盡可能小，因此這是一種“貪心”的策略。缺點：該算法的時間復雜度為O(n2)。與圖中邊數(shù)無關，該算法適合于稠密圖。 Kruskal算法基本思想：首先將G的n個頂點看成n個孤立的連通分支。將所有的邊按權從小到大排序。然后從第一條邊開始，依邊權遞增的順序查看每一條邊，并按下述方法連接兩個不同的連通分支：當查看到第k條邊(v,w)時，如果端點v和w分別是當前兩個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；如果端點v和w在當前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進行到只剩下一個連通分支時為止。此時，這個連通分支就是G的一棵最小生成樹。優(yōu)點：當輸入的連通帶權圖有e條邊時，則將這些邊依其權組成優(yōu)先隊列需要O(e)時間，在上述算法的while循環(huán)中，DeleteMin運算需要O(loge)時間，因此關于優(yōu)先隊列所作運算的時間為O(eloge)。實現(xiàn)UnionFind所需的時間為O(eloge)或O(elog*e)。所以Kruskal算法所需的計算時間為O(eloge)。缺點：當e=(n2)時，Kruskal算法比Prim算法差，但當e=O(n2)時，Kruskal算法卻比Prim算法好得多。Kruskal算法的時間主要取決于邊數(shù)。它較適合于稀疏圖。1 本課程研究的內(nèi)容通過資料收集、實際調(diào)查分析，最終形成自己的觀點和見解，擬定以下內(nèi)容進行探析：（1）基本知識1）貪心算法的含義2）貪心算法的基本思路及實現(xiàn)過程3）貪心算法的核心4）貪心算法的基本性質(zhì)5）貪心算法的特點6）貪心算法存在的問題（2）經(jīng)典問題解決及其優(yōu)缺點1）哈夫曼編碼2）單源最短路徑問題(Dijkstra算法)3）最小生成樹問題(Prim算法、Kruskal算法)（3）貪心算法的實際應用1）多處最優(yōu)服務次序問題2）刪數(shù)問題3）汽車加油問題4）最優(yōu)合并問題5）會場安排問題2 總結(jié)貪心算法是很常見的算法，貪心策略是最接近人的日常思維的一種解題策略，雖然它不能保證求得的最后解一定是最佳的，但是它可以為某些問題確定一個可行性范圍，因此貪心策略在各級各類信息學競賽，尤其在對NPC類問題的求解中發(fā)揮著越來越重要的作用。對于一個問題的最優(yōu)解只能用窮舉法得到時，用貪心算法是尋找問題最優(yōu)解的較好算法?？傊浞掷秘澬乃惴ǖ膬?yōu)勢，從局部最優(yōu)出發(fā)，構(gòu)造貪心策略比較容易，且簡單易行。參考文獻： 1 嚴蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(c語言版)M.北京:清華大學出版社,1997 2 M.H.ALSUWAIYEL.算法設計技巧與分析M.北京:電子工業(yè)出版社,2004 3 譚浩強.C+面向?qū)ο蟪绦蛟O計M.北京:清華大學出版社,20064 常友渠.貪心算法的探討與研究M.重慶電力高等專科學報,第13卷，第13期，2008.9.5 龔雄興,堆與貪心算法M,湖北襄樊學院，2003.6 張潔,朱莉娟.貪心算法與動態(tài)規(guī)劃的比較M.新鄉(xiāng)師范高等?？瓶茖W學報,第19卷，第五期，2005.9.7 殷建平.關于貪心算法的正確性證明M.江西師范大學學報（自然科學版）,第22卷增刊,1998.10.8 王曉東.計算機算法設計與分析(第3版)M北京：電子工業(yè)出版社,2007 9 余祥宣,崔國華,鄒海明.計算機算法基礎M.武漢:華中科技大學出版社,2000 10 盧開澄.計算機算法導引設計與分析M.北京:清華大學出版社,200311 M.H.ALSUWAIYEL.算法設計技巧與分析M.北京電子工業(yè)出版社（影印版）,51-52.12 朱洪.算法設計和分析M.上海科學技術文獻出版社,1989,162-163.13 王曉東.計算算法設計與分析（第二版）M.北京:電子工業(yè)出版社,2OO4.14 王曉東.算法設計與分析M.北京:清華大學出版社,2O04.15 蘇德富,鐘誠.計算機算法設計與分析M.北京:電子工業(yè)出版社,2001:60-62.16URL /view/298415.htm?fr=ala017URL /forums/threads/134122.aspx18URL /s/blog_5cd377280100artn.html19URL /question/45158704.html?fr=ala020URL /club/showtxt.asp?id=9179421 MelhiM,Ipson S S,Boothw.A novel triangulation procedure for thinning hand written textJ.Pattern Recognition Letters,2001,22(10):1059-1071.22 Florescu D,Grunhagen A,Kossmann D.XL:A Platform for Web ServicesC.Proc.of the 1st Biennial Conference on innovative Data Systems Research, 2003.西南大學本科畢業(yè)論文（設計）開題報告論文題目貪心算法設計及其實際應用研究系別專業(yè)信息管理系計算機科學與技術年 級2006級開題日期2009年11月28日學 號222006602054062姓 名蔣遠麗指導教師汪維清1.本課題研究意義：為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實際問題，計算機算法學得到了飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型紛紛運用到計算機算法學中，產(chǎn)生了解決各種現(xiàn)實問題的有效算法。雖然設計一個好的求解算法更像是一門藝術而不像是技術，但仍然存在一些行之有效的、能夠用于解決許多問題的算法設計方法，你可以使用這些方法來設計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細致的調(diào)整。但是在某些情況下，算法經(jīng)過調(diào)整之后性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時，貪心算法通常會給出一個簡單、直觀和高效的解法。貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是在當前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問題化簡為一個更小的與原問題具有相同形式的子問題。盡管貪心算法對許多問題不能總是產(chǎn)生整體最優(yōu)解，但對諸如最短路徑問題、最小生成樹問題，以及哈夫曼編碼問題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動態(tài)規(guī)劃算法更加簡單、直觀和高效。2.研究內(nèi)容：（1）基本知識1）貪心算法的含義2）貪心算法的基本思路及實現(xiàn)過程3）貪心算法的核心4）貪心算法的基本性質(zhì)5）貪心算法的特點6）貪心算法存在的問題（2）經(jīng)典問題解決及其優(yōu)缺點1）哈夫曼編碼2）單源最短路徑問題(Dijkstra算法)3）最小生成樹問題(Prim算法、Kruskal算法)（3）貪心算法的實際應用1）多處最優(yōu)服務次序問題2）刪數(shù)問題3）汽車加油問題4）最優(yōu)合并問題5）會場安排問題3.技術路線、研究方法和研究進度：（1）技術路線題目分析收集資料（網(wǎng)絡和圖書館）閱讀資料規(guī)劃論文結(jié)構(gòu)整理資料詳細分析整理（貪心算法的基本含義、原理、實現(xiàn)過程、性質(zhì)、特點、算法優(yōu)缺點等）分析該算法的實例及其優(yōu)缺點（哈夫曼編碼、單源最短路徑問題(Dijkstra算法)、最小生成樹問題(Prim算法、Kruskal算法)）挑選幾個經(jīng)典實例研究并用c+實現(xiàn)（多處最優(yōu)服務次序問題、刪數(shù)問題、汽車加油問題、最優(yōu)合并問題）總結(jié)。（2）研究方法1）文獻研究法：通過查詢資料來收集研究所需要的基礎知識；資料收集方式：利用網(wǎng)絡資源、查找相關書籍、收集有關研究課題內(nèi)容的報刊雜志等；2）個案研究法、實驗法：在資料收集完成之上，建立課題研究結(jié)構(gòu)，思路清楚地對貪心算法的各方面進行分析、探討、研究；包括：貪心算法的基本含義、基本原理和實現(xiàn)過程，其及貪心算法的性質(zhì)、貪心算法的特點及優(yōu)缺點等，分析由貪心算法解決的幾個經(jīng)典問題的理論以及它們各自的優(yōu)缺點。從現(xiàn)實實際出發(fā)，從中選擇幾例進行深入研究，并以C+語言實現(xiàn)完成。3）將所研究的內(nèi)容按合理的思路組合及實例實現(xiàn)完成一篇完整的課題論文；（3）研究進度2009年10月-2009年11月， 根據(jù)課題研究的內(nèi)容，收集資料2009年11月- 2009年12月， 深入探討該算法中的幾個經(jīng)典問題2009年12月- 2010年1月， 整理研究內(nèi)容，并作進一步的修改2010年1月- 2010年2月， 歸納總結(jié)，運行程序成功后，形成一份完整的課題論文4.導師意見： 指導教師（簽名）：年 月 日5.系意見： 系（蓋章） 年 月 日說明：開題報告應在教師指導下由學生獨立撰寫。在畢業(yè)論文（畢業(yè)設計）開始二周內(nèi)完成，交指導教師審閱，并接受學校和學院檢查。正文貪心算法設計及其實際應用研究蔣遠麗西南大學榮昌校區(qū)信息管理系，重慶榮昌 402460摘要：貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇,也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相當廣泛的許多問題也能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。本文首先介紹了貪心算法的核心、特點及算法本身存在的問題，接下來介紹了前人已經(jīng)研究出來的成果，包括哈夫曼編碼、單源最短路徑、最小生成樹等。然后結(jié)合實踐，研究了多處最優(yōu)服務次序問題、刪數(shù)問題、汽車加油問題、最優(yōu)合并問題、會場安排問題等。最后用代碼實現(xiàn)其中的兩個問題，對貪心算法的具體實現(xiàn)方法做了詳細說明。關鍵字：貪心算法；哈夫曼編碼；最小生成樹；最優(yōu)服務次序；汽車加油問題Greedy algorithm design and its practical applicationJiang YuanliDepartment of Information Management, Southwest University, Rongchang, ChongqingAbstract：Greedy algorithm is that, in the problem solving, it always made in the current appears to be the best option. In other words, not the best on the whole to be considered, he made only a local optimal solution in a sense. Greedy algorithm is not a right that all problems can be the overall optimal solution, but it covers a wide range of issues that he could produce an overall optimal solution or approximate solution of the overall optimal solution. This paper describes the core of the greedy algorithm, characteristics and algorithms inherent problems, then presented the results of our predecessors has been studied out, including Huffman coding, single-source shortest path, minimum spanning tree and so on. Then with practice, study the various optimal service order issues, delete a few issues, car fuel, the optimal merger, venue arrangements and so on. At last, the code to achieve two of them on the greedy algorithm to do the concrete implementation method in detail.Key words：greedy algorithm；Huffman coding；MST；Optimal service order;Automobile refueling第1章 引言1.1研究背景為了滿足人們對大數(shù)據(jù)量信息處理的渴望，為解決各種實際問題，計算機算法學得到了飛速的發(fā)展，線性規(guī)劃、動態(tài)規(guī)劃、貪心策略等一系列運籌學模型紛紛運用到計算機算法學中，產(chǎn)生了解決各種現(xiàn)實問題的有效算法。雖然設計一個好的求解算法更像是一門藝術而不像是技術，但仍然存在一些行之有效的、能夠用于解決許多問題的算法設計方法，你可以使用這些方法來設計算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對算法進行細致的調(diào)整。但是在某些情況下，算法經(jīng)過調(diào)整之后性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。當一個問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時，貪心算法通常會給出一個簡單、直觀和高效的解法。貪心算法通過一系列的選擇來得到一個問題的解。它所作的每一個選擇都是在當前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問題化簡為一個更小的與原問題具有相同形式的子問題。盡管貪心算法對許多問題不能總是產(chǎn)生整體最優(yōu)解，但對諸如最短路徑問題、最小生成樹問題，以及哈夫曼編碼問題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動態(tài)規(guī)劃算法更加簡單、直觀和高效。1.2研究內(nèi)容貪心算法的定義（是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法），貪心算法的基本要素（最優(yōu)子結(jié)構(gòu)性質(zhì)、貪心選擇性質(zhì)）、貪心算法的思路及過程，貪心算法的核心（貪心策略）及特性（無回溯）、探討貪心算法存在的問題。然后分析已有成果運用貪心策略的解法（哈夫曼編碼、單源最短路徑問題、最小生成樹等），結(jié)合實際中的例子（多處最優(yōu)服務次序問題、刪數(shù)問題、汽車加油問題、會場安排問題、最優(yōu)合并問題），對貪心算法進行分析與運用。1.3研究目標通過本課題的研究來探討貪心算法理論基礎以及對貪心策略在更多實例中的運用做可行的研究，為貪心算法能夠運用到更多的實際中的問題作示范。1.4研究意義貪心算法是計算機算法策略中常用的一個，往往在需要解決一些最優(yōu)性問題時，都可以應用貪心算法。貪心算法的用法特點有：一是明顯的貪心，一般此類應用問題本身就是貪心；二是貪心數(shù)據(jù)結(jié)構(gòu)，如：堆，最小樹；三是可證明貪心策略的貪心，這是我們最常見的；四是博弈、游戲策略，這些策略大多是貪心；五是求較優(yōu)解或多次逼近最優(yōu)解。通過用貪心算法求解以上問題，可以找到解決這些問題的最優(yōu)算法，為其它的類似問題的解決有示范和例證作用。1.5 本文組織本文從如下方面進行組織：先提出貪心算法的基本知識，再從貪心算法的幾個現(xiàn)有的成果研究探討，然后對貪心算法中的幾個經(jīng)典問題進行研究，寫出其中兩個問題的代碼，最后進行總結(jié)。第2章 貪心算法的基本知識概述2.1 貪心算法定義貪心算法可以簡單描述為：對一組數(shù)據(jù)進行排序，找出最小值，進行處理，再找出最小值，再處理。也就是說貪心算法是一種在每一步選擇中都采取在當前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級處理方法，通過一系列的選擇來得到一個問題的解，而它所做的每一次選擇都是當前狀態(tài)下某種意義的最好選擇，即貪心選擇。即希望通過問題的局部最優(yōu)解來求出整個問題的最優(yōu)解。這種策略是一種很簡潔的方法，對許多問題它能產(chǎn)生整體最優(yōu)解，但不能保證總是有效，因為它不是對所有問題都能得到整體最優(yōu)解，只能說其解必然是最優(yōu)解的很好近似值。2.2 貪心算法的基本思路及實現(xiàn)過程2.2.1 貪心的基本思想用局部解構(gòu)造全局解，即從問題的某一個初始解逐步逼近給定的目標，以盡可能快地求得更好的解。當某個算法中的某一步不能再繼續(xù)前進時，算法停止。貪心算法思想的本質(zhì)就是分治，或者說：分治是貪心的基礎。每次都形成局部最優(yōu)解，換一種方法說，就是每次都處理出一個最好的方案。利用貪心策略解題，需要解決兩個問題：（1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標準，以得到問題的最優(yōu)/較優(yōu)解。2.2.2 貪心算法的實現(xiàn)過程（1）應用同一規(guī)則F，將原問題變?yōu)橐粋€相似的、但規(guī)模更小的子問題；（2）從問題的某一初始解出發(fā)：While（能朝給定目標前進一步） 求出可行解的一個解元素；（3）由所有解元素組合成問題的一個可行解。2.3貪心算法的核心貪心算法的核心問題是選擇能產(chǎn)生問題最優(yōu)解的最優(yōu)度量標準，即具體的貪心策略。貪心策略是指從問題的初始狀態(tài)出發(fā)，通過若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。其實，從“貪心策略”一詞我們便可以看出，貪心策略總是做出在當前看來是最優(yōu)的選擇，也就是說貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問題自身的特性決定了該題運用貪心策略可以得到最優(yōu)解或較優(yōu)解。2.4貪心算法的基本要素2.4.1貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達到。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。在動態(tài)規(guī)劃算法中，每步所做的選擇往往依賴于相關子問題的解。因而只有在解出相關子問題后，才能做出選擇。而在貪心算法中，僅在當前狀態(tài)下做出最好選擇，即局部最優(yōu)選擇。然后再去解做出這個選擇后產(chǎn)生的相應的子問題。貪心算法所做的貪心選擇可以依賴于以往所做過的選擇，但決不依賴于將來所做的選擇，也不依賴于子問題的解。正是由于這種差別，動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進行，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終導致問題的整體最優(yōu)解。首先考察問題的一個整體最優(yōu)解，并證明可修改這個最優(yōu)解，使其以貪心選擇開始。做了貪心選擇后，原問題簡化為規(guī)模更小的類似子問題。然后，用數(shù)學歸納法證明，通過每一步做貪心選擇，最終可得到問題的整體最優(yōu)解。其中，證明貪心選擇后的問題簡化為規(guī)模更小的類似子問題的關鍵在于利用該問題的最優(yōu)子結(jié)構(gòu)性質(zhì)。2.4.2最優(yōu)子結(jié)構(gòu)性質(zhì)當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運用貪心策略在每一次轉(zhuǎn)化時都取得了最優(yōu)解。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用貪心算法或動態(tài)規(guī)劃算法求解的關鍵特征。貪心算法的每一次操作都對結(jié)果產(chǎn)生直接影響，而動態(tài)規(guī)劃則不是。貪心算法對每個子問題的解決方案都做出選擇，不能回退；動態(tài)規(guī)劃則會根據(jù)以前的選擇結(jié)果對當前進行選擇，有回退功能。動態(tài)規(guī)劃主要運用于二維或三維問題，而貪心一般是一維問題。2.4.3貪心算法的特點貪心算法的最大特點就是快，通常是線性二次式，不需要多少額外的內(nèi)存。一般二次方級的存儲要浪費額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時，這些空間可以幫助算法更容易實現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用。因為它容易編寫，容易調(diào)試，速度極快，并且節(jié)約空間。幾乎可以說，此時它是所有算法中最好的。但是應該注意，貪心算法有兩大難點：（1）如何貪心怎樣用一個小規(guī)模的解構(gòu)造更大規(guī)模的解呢?總體上，這與問題本身有關。但是大部分都是有規(guī)律的。正因為貪心有如此性質(zhì)，它才能比其他算法快。具有應當采用貪心算法的問題，當“貪心序列”中的每項互異且當問題沒有重疊性時，看起來總能通過貪心算法取得（近似）最優(yōu)解的?；蛘?，總有一種直覺在引導我們對一些問題采用貪心算法。其中“找零錢”這個問題就是一個例子。題中給出的硬幣面值事實上具有特殊性，如果面值發(fā)生變化，可能貪心算法就不能返回最優(yōu)解了。但是，值得指出的是，當一個問題具有多個最優(yōu)解時，貪心算法并不能求出所有最優(yōu)解。另外，我們經(jīng)過實踐發(fā)現(xiàn)，單純的貪心算法是順序處理問題的；而且每個結(jié)果是可以在處理完一個數(shù)據(jù)后即時輸出的。（2）貪心的正確性要證明貪心性質(zhì)的正確性，才是貪心算法的真正挑戰(zhàn)，因為并不是每次局部最優(yōu)解都會與整體最優(yōu)解之間有聯(lián)系，往往靠貪心算法生成的解不是最優(yōu)解。這樣，貪心性質(zhì)的證明就成了貪心算法正確的關鍵。對某些問題貪心性質(zhì)也許是錯的，即使它在大部分數(shù)據(jù)中都是可行的，但還必須考慮到所有可能出現(xiàn)的特殊情況，并證明該貪心性質(zhì)在這些特殊情況中仍然正確。而這樣容易陷入證明不正確貪心性質(zhì)的泥塘中無法自拔，因為貪心算法的適用范圍并不大，而且有一部分極難證明，若是沒有把握，最好不要冒險，還有其他算法會比它要保險。2.5 貪心算法的理論基礎正如前文所說的那樣，貪心策略是最接近人類認知思維的一種解題策略。但是，越是顯而易見的方法往往越難以證明。下面我們就來介紹貪心策略的理論擬陣?！皵M陣”理論是一種能夠確定貪心策略何時能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問題時發(fā)揮著越來越重要的作用。擬陣M定義為滿足下面3個條件的有序?qū)Γ⊿，I）：（1）S是非空有限集；（2）I是S的一類具有遺傳性質(zhì)的獨立子集族，即若BI，則B是S的獨立子集，且B的任意子集也都是S的獨立子集?？占貫镮的成員；（3）I滿足交換性質(zhì)，即若AI，BI且|A|B|，則存在某一元素xB-A，使得AxI。定理2.1 擬陣M中所有極大獨立子集具有相同大小。引理2.1 （擬陣的貪心選擇性質(zhì)）設M=（S，I）是具有權函數(shù)M的帶權擬陣，且S中元素依權值從大到小排列，又設xS是S中第一個使得x是獨立子集元素，則存在S的最優(yōu)子集A使得xA。引理2.2 設M=(S，I)是擬陣。若S中元素x不是空集的一個可擴元素，則x也不可能是S中任一獨立子集A的可擴展元素。引理2.3 （擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì)）設x是求帶權擬陣M=（S，I）的最優(yōu)子集的貪心算法Greedy所選擇的S中的第一個元素。那么，原問題可簡化為求帶權擬陣M=（S，I）的最優(yōu)子集問題，其中S=y|yS且x，yII=B|BS-x且BxIM的權函數(shù)是M的權函數(shù)在S上的限制（稱M為M關于元素x的收縮）。定理2.4（帶權擬陣貪心算法的正確性）高M=（S，I）是具有權函數(shù)W的帶權擬陣，算法Greedy返回M的最優(yōu)子集。適宜于用貪心策略來求解的許多問題都可以歸結(jié)為在加權擬陣中找一個具有最大權值的獨立子集的問題，即給定一個加權擬陣M=（S，I），若能找出一個獨立且具有最大可能權值的子集A，且A不被M中比它更大的獨立子集所包含，那么A為最優(yōu)子集，也是一個最大的獨立子集。我們認為，針對絕大多數(shù)的信息學問題，只要它具備了“擬陣”的結(jié)構(gòu)，便可用貪心策略求解。擬陣理論對于我們判斷貪心策略是否適用于某一復雜問題是十分有效的。2.6 貪心算法存在的問題（1）不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來是最優(yōu)的選擇，因此并不從整體上加以考慮；（2）貪心算法只能用來求某些最大或最小解的問題；（3）貪心算法只能確定某些問題的可行性范圍。第3章 經(jīng)典問題解決及其優(yōu)缺點3.1 哈夫曼編碼3.1.1 問題描述哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。3.1.2 編碼原理對每一個字符規(guī)定一個0，1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡單。由于任一字符的代碼都不是其他字符代碼的前綴，從編碼文件中不斷取出代表某一字符的前綴碼，轉(zhuǎn)換為原字符，即可逐個譯出文件中的所有字符。可以用二叉樹作為前綴編碼的數(shù)據(jù)結(jié)構(gòu)。在表示前綴碼的二叉樹中，樹葉代表給定的字符，并將每個字符的前綴碼看做是從樹根到代表該字符的樹葉的一條道路。代碼中每一位的0或1分別作為指示某結(jié)點到左兒子或右兒子的“路標”。3.1.3 貪心算法策略設C是編碼字符集，C中字符c的頻率為f(c)。又設x和y是C中具有最小頻率的兩個字符，則存在C的最優(yōu)前綴碼使x和y具有相同碼長且僅最后一位編碼不同。證明：設二叉樹T表示C的任意一個最優(yōu)前綴碼。下面證明可以對T做適當修改后得到一棵新的二叉樹T，使得在新樹中，x和y是最深葉子且為兄弟。同時新樹T表示的前綴碼也是C的最優(yōu)前綴碼。如果能做到這一點，則x和y在T表示的最優(yōu)前綴碼中就具有相同的碼長且僅最后一位編碼不同。設b和c是二叉樹T的最深葉子且為兄弟。不失一般性，可設f(b)f(c)，f(x)f(y)。由于x和y是C中具有最小頻率的兩個字符，故f(x)f(b)，f(y)f(c)。首先在樹T中交換葉子b和x的位置得到樹T，然后在樹T中再交換葉子c和y的位置。得到樹T。如圖3.1所示。xybcbyxcyccbTTTFig. 3.1 Counterchange the Coding-tree T圖3.1 編碼樹T的變換由此可知，樹T和T表示的前綴碼的平均碼長之差為B(T)-B(T)= =f(x)dT(x)+f(b)dT(b)-f(x)dT(x)-f(b)dT(b) =f(x)dT(x)+f(b)dT(b)-f(x)dT(b)-f(b)dT(x) =(f(b)-f(x)(dT(b)-dT(x)0最后一個不等式是因為f(b)-f(x)和dT(b)-dT(x)均為非負。類似地，可以證明在T中交換y與c的位置也不增加平均碼長，即B(T)-B(T)也是非負的。由此可知，B(T)B(T)B(T)。另一方面，由于T所表示的前綴碼是最優(yōu)的，故B(T)B(T)。因此，B(T)=B(T)，即T表示的前綴碼也是最優(yōu)前綴碼，且x和y具有最長的碼長，同時僅最后一位編碼不同。3.1.4 最優(yōu)子結(jié)構(gòu)性質(zhì)設T是表示字符集C的一個最優(yōu)前綴碼的完全二叉樹。C中字符c的出現(xiàn)頻率為f(c)。設x和y是樹T中的兩個葉子且為兄弟，z是它們的父親。若將z看做是具有頻率f(z)=f(x)+f(y)的字符，則樹T=T-x，y表示字符集C=C-x，yz的一個最優(yōu)前綴碼。證明：首先證明T的平均碼長B(T)要用T的平均碼長B(T)來表示。事實上，對任意cC-x，y有dT(c)=dT(c)，故f(c)dT(c)=f(c)dT(c)。另一方面，dT(x)=dT(y)=dT(z)+1，故f(x)dT(x)+f(y)dT(y)=(f(x)+f(y)(dT(z)+1) =f(x)+f(y)+f(z)dT(z)由此即知，B(T)=B(T)+f(x)+f(y)。若T所表示的字符集C的前綴碼不是最優(yōu)的，則有T表示的C的前綴碼使得B(T)B(T)。由于z被看做是C中的一個字符，故z在T中是一樹葉。若將x和y加入樹T中作為z的兒子，則得到表示字符集C的前綴碼的二叉樹T，且有B（T）=B（T）+f(x)+f(y) B(T)+f(x)+f(y) =B(T)這與T的最優(yōu)性矛盾。故T所表示的C的前綴碼是最優(yōu)的。由貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)立即可推出：哈夫曼算法是正確的，即HuffmanTree產(chǎn)生C的一棵最優(yōu)前綴編碼樹。3.1.5 計算復雜性算法HuffmanTree用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O（n）計算時間，由于最小堆的DeleteMin和Insert運算均需O(logn)時間，n-1次的合并總共需要O(nlogn)計算時間。因此，關于n個字符的哈夫曼算法的計算時間為O(nlogn)。3.2單源最短路徑問題(Dijkstra算法)3.2.1 問題描述給定一個帶權有向圖G=(V，E)，其中每條邊的權是一個非負實數(shù)。另外，還給定V中的一個頂點，稱為源。現(xiàn)在我們要計算從源到所有其他各頂點的最短路徑長度。這里的長度是指路上各邊權之和。這個問題通常稱為單源最短路徑問題。3.2.2 編碼原理設置頂點集合S并不斷地作貪心選擇來擴充這個集合。一個頂點屬于集合S當且僅當從源到該頂點的最短路徑長度已知。初始時，S中僅含有源。設u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當前每個頂點所對應的最短特殊路徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。3.2.3 貪心算法策略Dijkstra算法是應用貪心算法設計策略的一個典型例子。它所作的貪心選擇是從V-S中選擇具有最短特殊路徑的頂點u，從而確定從源到u的最短路徑長度distu。這種貪心選擇為什么能導致最優(yōu)解呢？換句話說，為什么從源到u沒有更短的其他