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

本科畢業(yè)論文（設(shè)計(jì)）題 目 貪心算法設(shè)計(jì)及其實(shí)際應(yīng)用研究 系 別 信 息 管 理 系 專 業(yè) 計(jì)算機(jī)科學(xué)與技術(shù) 年 級(jí) 2006級(jí) 學(xué) 號(hào) 222006602054062 姓 名 蔣 遠(yuǎn) 麗 指 導(dǎo) 教 師 汪 維 清 成 績(jī) _ 二一年五月十五日 nn目 錄西南大學(xué)本科畢業(yè)論文（設(shè)計(jì)）任務(wù)書I文獻(xiàn)綜述i西南大學(xué)本科畢業(yè)論文（設(shè)計(jì)）開(kāi)題報(bào)告- 1 -正文1摘要1第1章 引言21.1研究背景21.2研究?jī)?nèi)容21.3研究目標(biāo)21.4研究意義21.5 本文組織3第2章 貪心算法的基本知識(shí)概述42.1 貪心算法定義42.2 貪心算法的基本思路及實(shí)現(xiàn)過(guò)程42.3貪心算法的核心42.4貪心算法的基本要素52.5 貪心算法的理論基礎(chǔ)62.6貪心算法存在的問(wèn)題7第3章 經(jīng)典問(wèn)題解決及其優(yōu)缺點(diǎn)83.1 哈夫曼編碼83.2單源最短路徑問(wèn)題(Dijkstra算法)103.3最小生成樹(shù)問(wèn)題(Prim算法、Kruskal算法)12第4章 多處最優(yōu)服務(wù)次序問(wèn)題154.1 問(wèn)題的提出154.2 貪心選擇策略154.3 問(wèn)題的貪心選擇性質(zhì)154.4 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)154.5 算法結(jié)果分析16第5章 刪數(shù)問(wèn)題175.1 問(wèn)題的提出175.2 貪心算法策略175.3 問(wèn)題的貪心選擇性質(zhì)175.4 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)175.5 編碼18第6章 汽車加油問(wèn)題196.1 問(wèn)題的提出196.2 編碼分析196.3 貪心算法策略196.4 貪心算法正確性證明206.5 貪心算法時(shí)間復(fù)雜度分析20第7章 最優(yōu)合并問(wèn)題217.1 問(wèn)題的提出217.2 原理分析217.3 算法時(shí)間復(fù)雜度分析21第8章 會(huì)場(chǎng)安排問(wèn)題228.1 問(wèn)題的提出228.2 編碼分析228.3 貪心算法228.4 最優(yōu)解證明238.5 算法時(shí)間復(fù)雜度分析23第9章 貪心算法的C+實(shí)現(xiàn)249.1 C+語(yǔ)言概述249.2 具體實(shí)現(xiàn)步驟259.3程序編碼與程序調(diào)試29第10章 總結(jié)與展望3110.1總結(jié)3110.2展望31參考文獻(xiàn)32附錄33致謝41本科畢業(yè)論文（設(shè)計(jì)）指導(dǎo)教師評(píng)閱表a本科畢業(yè)論文（設(shè)計(jì)）交叉評(píng)閱表b本科畢業(yè)論文（設(shè)計(jì)）答辯記錄c西南大學(xué)本科畢業(yè)論文（設(shè)計(jì)）任務(wù)書論文（設(shè)計(jì)）題目 貪心算法設(shè)計(jì)及其實(shí)際應(yīng)用研究 系別、專業(yè) 信息管理系計(jì)算機(jī)科學(xué)與技術(shù) 學(xué)生姓名 蔣遠(yuǎn)麗 學(xué)號(hào) 222006602054062 指導(dǎo)教師姓名 汪維清 開(kāi)題日期 2009年11月28日 論文（設(shè)計(jì)）的主要內(nèi)容（技術(shù)指標(biāo)）與要求：本文講述了貪心算法的含義、基本思路及實(shí)現(xiàn)過(guò)程，貪心算法的核心、基本性質(zhì)、特點(diǎn)及其存在的問(wèn)題。并通過(guò)貪心算法的性質(zhì)，通過(guò)研究幾個(gè)經(jīng)典問(wèn)題，將貪心算法應(yīng)用到實(shí)際中。進(jìn) 度 安 排研究進(jìn)度安排：2009年10月-2009年11月，根據(jù)課題研究的內(nèi)容，收集資料2009年11月- 2009年12月，深入探討該算法中的幾個(gè)經(jīng)典問(wèn)題2009年12月- 2010年1月，整理研究?jī)?nèi)容，并作進(jìn)一步的修改2010年1月- 2010年2月，歸納總結(jié)，形成一份完整的課題論文系意見(jiàn)：注：1、任務(wù)書由指導(dǎo)老師填寫。 2、任務(wù)書必須在第七學(xué)期13周前下達(dá)給學(xué)生。文獻(xiàn)綜述貪心算法設(shè)計(jì)及其實(shí)際應(yīng)用研究蔣遠(yuǎn)麗西南大學(xué)榮昌校區(qū)信息管理系，重慶榮昌 402460摘 要：在求最優(yōu)解問(wèn)題的過(guò)程中，依據(jù)某種貪心標(biāo)準(zhǔn)，從問(wèn)題的初始狀態(tài)出發(fā)，直接去求每一步的最優(yōu)解，通過(guò)若干次的貪心選擇，最終得出整個(gè)問(wèn)題的最優(yōu)解，這種求解方法就是貪心算法。從貪心算法的定義可以看出，貪心法并不是從整體上考慮問(wèn)題，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而由問(wèn)題自身的特性決定了該題運(yùn)用貪心算法可以得到最優(yōu)解。貪心算法所作的選擇可以依賴于以往所作過(guò)的選擇，但決不依賴于將來(lái)的選擇，也不依賴于子問(wèn)題的解，因此貪心算法與其它算法相比具有一定的速度優(yōu)勢(shì)。如果一個(gè)問(wèn)題可以同時(shí)用幾種方法解決，貪心算法應(yīng)該是最好的選擇之一。本文講述了貪心算法的含義、基本思路及實(shí)現(xiàn)過(guò)程，貪心算法的核心、基本性質(zhì)、特點(diǎn)及其存在的問(wèn)題。并通過(guò)貪心算法的特點(diǎn)舉例列出了以往研究過(guò)的幾個(gè)經(jīng)典問(wèn)題，對(duì)于實(shí)際應(yīng)用中的問(wèn)題，也希望通過(guò)貪心算法的特點(diǎn)來(lái)解決。關(guān)鍵詞：貪心算法；哈夫曼編碼；最小生成樹(shù)；多處最優(yōu)服務(wù)次序問(wèn)題；刪數(shù)問(wèn)題0 引言為了滿足人們對(duì)大數(shù)據(jù)量信息處理的渴望，為解決各種實(shí)際問(wèn)題，計(jì)算機(jī)算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動(dòng)態(tài)規(guī)劃、貪心策略等一系列運(yùn)籌學(xué)模型紛紛運(yùn)用到計(jì)算機(jī)算法學(xué)中，產(chǎn)生了解決各種現(xiàn)實(shí)問(wèn)題的有效算法。雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門藝術(shù)而不像是技術(shù) ,但仍然存在一些行之有效的、能夠用于解決許多問(wèn)題的算法設(shè)計(jì)方法 ,你可以使用這些方法來(lái)設(shè)計(jì)算法 ,并觀察這些算法是如何工作的。一般情況下,為了獲得較好的性能,必須對(duì)算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下,算法經(jīng)過(guò)調(diào)整之后性能仍無(wú)法達(dá)到要求,這時(shí)就必須尋求另外的方法來(lái)求解該問(wèn)題。當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時(shí)，貪心算法通常會(huì)給出一個(gè)簡(jiǎn)單、直觀和高效的解法。貪心算法通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解。它所作的每一個(gè)選擇都是在當(dāng)前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問(wèn)題化簡(jiǎn)為一個(gè)更小的與原問(wèn)題具有相同形式的子問(wèn)題。盡管貪心算法對(duì)許多問(wèn)題不能總是產(chǎn)生整體最優(yōu)解，但對(duì)諸如最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題，以及哈夫曼編碼問(wèn)題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問(wèn)題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動(dòng)態(tài)規(guī)劃算法更加簡(jiǎn)單、直觀和高效。（1）基本知識(shí)貪心算法的含義貪心算法是通過(guò)一系列的選擇來(lái)得到問(wèn)題解的過(guò)程。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法，它總是做出在當(dāng)前看來(lái)是最優(yōu)的選擇，也就是說(shuō)貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解算法。（2）貪心算法特點(diǎn)及存在的問(wèn)題1)貪心算法的特點(diǎn)從全局來(lái)看，運(yùn)用貪心策略解決的問(wèn)題在程序的運(yùn)行過(guò)程中無(wú)回溯過(guò)程，后面的每一步都是當(dāng)前看似最佳的選擇，這種選擇依賴于已做出的選擇，但不依賴于未做出的選擇。2)貪心算法存在的問(wèn)題不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來(lái)是最優(yōu)的選擇，因此并不從整體上加以考慮。 貪心算法只能用來(lái)求某些最大或最小解的問(wèn)題。例如找零錢問(wèn)題要求得到最小數(shù)量，就可以采用貪心算法，但是在另外一個(gè)求解權(quán)值最小路徑時(shí)采用貪心算法得到的結(jié)果并不是最佳。 貪心算法只能確定某些問(wèn)題的可行性范圍。（3）經(jīng)典問(wèn)題解決及其優(yōu)缺點(diǎn)1）哈夫曼編碼問(wèn)題提出：哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。基本原理：對(duì)每一個(gè)字符規(guī)定一個(gè)0，1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。由于任一字符的代碼都不是其他字符代碼的前綴，從編碼文件中不斷取出代表某一字符的前綴碼，轉(zhuǎn)換為原字符，即可逐個(gè)譯出文件中的所有字符。可以用二叉樹(shù)作為前綴編碼的數(shù)據(jù)結(jié)構(gòu)。在表示前綴碼的二叉樹(shù)中，樹(shù)葉代表給定的字符，并將每個(gè)字符的前綴碼看做是從樹(shù)根到代表該字符的樹(shù)葉的一條道路。代碼中每一位的0或1分別作為指示某結(jié)點(diǎn)到左兒子或右兒子的“路標(biāo)”。優(yōu)點(diǎn)：哈夫曼編碼是無(wú)損壓縮當(dāng)中最好的方法。它使用預(yù)先二進(jìn)制描述來(lái)替換每個(gè)符號(hào)，長(zhǎng)度由特殊符號(hào)出現(xiàn)的頻率決定。常見(jiàn)的符號(hào)需要很少的位來(lái)表示，而不常見(jiàn)的符號(hào)需要很多位來(lái)表示。哈夫曼算法在改變?nèi)魏畏?hào)二進(jìn)制編碼引起少量密集表現(xiàn)方面是最佳的。然而，它并不處理符號(hào)的順序和重復(fù)或序號(hào)的序列。缺點(diǎn)：慢位流實(shí)現(xiàn)相當(dāng)慢的解碼（比編碼慢）最大的樹(shù)深度是32（編碼器在任何超過(guò)32位大小的時(shí)候退出）。2）單源最短路徑問(wèn)題提出：給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。Dijkstra算法基本思想：設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，數(shù)組dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。優(yōu)點(diǎn)：Dijkstra的思想是按遞增長(zhǎng)度來(lái)產(chǎn)生路徑,每次選出當(dāng)前已經(jīng)找到的最短的一條路徑,它必然是一條最終的最短路徑。因此每次找出當(dāng)前距離數(shù)組中最小的,必然是一條最終的最短路徑缺點(diǎn)：對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要O(n)時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O（n2）時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)O（n2）。3）最小生成樹(shù)問(wèn)題提出：設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為cvw。如果G的子圖G是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱G為G的生成樹(shù)。生成樹(shù)上各邊權(quán)的總和稱為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱為G的最小生成樹(shù)。Prim算法基本思想：首先置S=1，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jv-s，且cij最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過(guò)程一直進(jìn)行到S=V時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹(shù)。優(yōu)點(diǎn)：該算法的特點(diǎn)是當(dāng)前形成的集合T始終是一棵樹(shù)。將T中U和TE分別看作紅點(diǎn)和紅邊集，V-U看作藍(lán)點(diǎn)集。算法的每一步均是在連接紅、藍(lán)點(diǎn)集的紫邊中選擇一條輕邊擴(kuò)充進(jìn)T中。MST性質(zhì)保證了此邊是安全的。T從任意的根r開(kāi)始，并逐漸生長(zhǎng)直至U=V，即T包含了C中所有的頂點(diǎn)為止。MST性質(zhì)確保此時(shí)的T是G的一棵MST。因?yàn)槊看翁砑拥倪吺鞘箻?shù)中的權(quán)盡可能小，因此這是一種“貪心”的策略。缺點(diǎn)：該算法的時(shí)間復(fù)雜度為O(n2)。與圖中邊數(shù)無(wú)關(guān)，該算法適合于稠密圖。 Kruskal算法基本思想：首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接兩個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前兩個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊；如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。此時(shí)，這個(gè)連通分支就是G的一棵最小生成樹(shù)。優(yōu)點(diǎn)：當(dāng)輸入的連通帶權(quán)圖有e條邊時(shí)，則將這些邊依其權(quán)組成優(yōu)先隊(duì)列需要O(e)時(shí)間，在上述算法的while循環(huán)中，DeleteMin運(yùn)算需要O(loge)時(shí)間，因此關(guān)于優(yōu)先隊(duì)列所作運(yùn)算的時(shí)間為O(eloge)。實(shí)現(xiàn)UnionFind所需的時(shí)間為O(eloge)或O(elog*e)。所以Kruskal算法所需的計(jì)算時(shí)間為O(eloge)。缺點(diǎn)：當(dāng)e=(n2)時(shí)，Kruskal算法比Prim算法差，但當(dāng)e=O(n2)時(shí)，Kruskal算法卻比Prim算法好得多。Kruskal算法的時(shí)間主要取決于邊數(shù)。它較適合于稀疏圖。1 本課程研究的內(nèi)容通過(guò)資料收集、實(shí)際調(diào)查分析，最終形成自己的觀點(diǎn)和見(jiàn)解，擬定以下內(nèi)容進(jìn)行探析：（1）基本知識(shí)1）貪心算法的含義2）貪心算法的基本思路及實(shí)現(xiàn)過(guò)程3）貪心算法的核心4）貪心算法的基本性質(zhì)5）貪心算法的特點(diǎn)6）貪心算法存在的問(wèn)題（2）經(jīng)典問(wèn)題解決及其優(yōu)缺點(diǎn)1）哈夫曼編碼2）單源最短路徑問(wèn)題(Dijkstra算法)3）最小生成樹(shù)問(wèn)題(Prim算法、Kruskal算法)（3）貪心算法的實(shí)際應(yīng)用1）多處最優(yōu)服務(wù)次序問(wèn)題2）刪數(shù)問(wèn)題3）汽車加油問(wèn)題4）最優(yōu)合并問(wèn)題5）會(huì)場(chǎng)安排問(wèn)題2 總結(jié)貪心算法是很常見(jiàn)的算法，貪心策略是最接近人的日常思維的一種解題策略，雖然它不能保證求得的最后解一定是最佳的，但是它可以為某些問(wèn)題確定一個(gè)可行性范圍，因此貪心策略在各級(jí)各類信息學(xué)競(jìng)賽，尤其在對(duì)NPC類問(wèn)題的求解中發(fā)揮著越來(lái)越重要的作用。對(duì)于一個(gè)問(wèn)題的最優(yōu)解只能用窮舉法得到時(shí)，用貪心算法是尋找問(wèn)題最優(yōu)解的較好算法?？傊?，充分利用貪心算法的優(yōu)勢(shì)，從局部最優(yōu)出發(fā)，構(gòu)造貪心策略比較容易，且簡(jiǎn)單易行。參考文獻(xiàn)： 1 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)(c語(yǔ)言版)M.北京:清華大學(xué)出版社,1997 2 M.H.ALSUWAIYEL.算法設(shè)計(jì)技巧與分析M.北京:電子工業(yè)出版社,2004 3 譚浩強(qiáng).C+面向?qū)ο蟪绦蛟O(shè)計(jì)M.北京:清華大學(xué)出版社,20064 常友渠.貪心算法的探討與研究M.重慶電力高等?？茖W(xué)報(bào),第13卷，第13期，2008.9.5 龔雄興,堆與貪心算法M,湖北襄樊學(xué)院，2003.6 張潔,朱莉娟.貪心算法與動(dòng)態(tài)規(guī)劃的比較M.新鄉(xiāng)師范高等?？瓶茖W(xué)學(xué)報(bào),第19卷，第五期，2005.9.7 殷建平.關(guān)于貪心算法的正確性證明M.江西師范大學(xué)學(xué)報(bào)（自然科學(xué)版）,第22卷增刊,1998.10.8 王曉東.計(jì)算機(jī)算法設(shè)計(jì)與分析(第3版)M北京：電子工業(yè)出版社,2007 9 余祥宣,崔國(guó)華,鄒海明.計(jì)算機(jī)算法基礎(chǔ)M.武漢:華中科技大學(xué)出版社,2000 10 盧開(kāi)澄.計(jì)算機(jī)算法導(dǎo)引設(shè)計(jì)與分析M.北京:清華大學(xué)出版社,200311 M.H.ALSUWAIYEL.算法設(shè)計(jì)技巧與分析M.北京電子工業(yè)出版社（影印版）,51-52.12 朱洪.算法設(shè)計(jì)和分析M.上?？茖W(xué)技術(shù)文獻(xiàn)出版社,1989,162-163.13 王曉東.計(jì)算算法設(shè)計(jì)與分析（第二版）M.北京:電子工業(yè)出版社,2OO4.14 王曉東.算法設(shè)計(jì)與分析M.北京:清華大學(xué)出版社,2O04.15 蘇德富,鐘誠(chéng).計(jì)算機(jī)算法設(shè)計(jì)與分析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.西南大學(xué)本科畢業(yè)論文（設(shè)計(jì)）開(kāi)題報(bào)告論文題目貪心算法設(shè)計(jì)及其實(shí)際應(yīng)用研究系別專業(yè)信息管理系計(jì)算機(jī)科學(xué)與技術(shù)年 級(jí)2006級(jí)開(kāi)題日期2009年11月28日學(xué) 號(hào)222006602054062姓 名蔣遠(yuǎn)麗指導(dǎo)教師汪維清1.本課題研究意義：為了滿足人們對(duì)大數(shù)據(jù)量信息處理的渴望，為解決各種實(shí)際問(wèn)題，計(jì)算機(jī)算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動(dòng)態(tài)規(guī)劃、貪心策略等一系列運(yùn)籌學(xué)模型紛紛運(yùn)用到計(jì)算機(jī)算法學(xué)中，產(chǎn)生了解決各種現(xiàn)實(shí)問(wèn)題的有效算法。雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門藝術(shù)而不像是技術(shù)，但仍然存在一些行之有效的、能夠用于解決許多問(wèn)題的算法設(shè)計(jì)方法，你可以使用這些方法來(lái)設(shè)計(jì)算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對(duì)算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下，算法經(jīng)過(guò)調(diào)整之后性能仍無(wú)法達(dá)到要求，這時(shí)就必須尋求另外的方法來(lái)求解該問(wèn)題。當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時(shí)，貪心算法通常會(huì)給出一個(gè)簡(jiǎn)單、直觀和高效的解法。貪心算法通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解。它所作的每一個(gè)選擇都是在當(dāng)前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問(wèn)題化簡(jiǎn)為一個(gè)更小的與原問(wèn)題具有相同形式的子問(wèn)題。盡管貪心算法對(duì)許多問(wèn)題不能總是產(chǎn)生整體最優(yōu)解，但對(duì)諸如最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題，以及哈夫曼編碼問(wèn)題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問(wèn)題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動(dòng)態(tài)規(guī)劃算法更加簡(jiǎn)單、直觀和高效。2.研究?jī)?nèi)容：（1）基本知識(shí)1）貪心算法的含義2）貪心算法的基本思路及實(shí)現(xiàn)過(guò)程3）貪心算法的核心4）貪心算法的基本性質(zhì)5）貪心算法的特點(diǎn)6）貪心算法存在的問(wèn)題（2）經(jīng)典問(wèn)題解決及其優(yōu)缺點(diǎn)1）哈夫曼編碼2）單源最短路徑問(wèn)題(Dijkstra算法)3）最小生成樹(shù)問(wèn)題(Prim算法、Kruskal算法)（3）貪心算法的實(shí)際應(yīng)用1）多處最優(yōu)服務(wù)次序問(wèn)題2）刪數(shù)問(wèn)題3）汽車加油問(wèn)題4）最優(yōu)合并問(wèn)題5）會(huì)場(chǎng)安排問(wèn)題3.技術(shù)路線、研究方法和研究進(jìn)度：（1）技術(shù)路線題目分析收集資料（網(wǎng)絡(luò)和圖書館）閱讀資料規(guī)劃論文結(jié)構(gòu)整理資料詳細(xì)分析整理（貪心算法的基本含義、原理、實(shí)現(xiàn)過(guò)程、性質(zhì)、特點(diǎn)、算法優(yōu)缺點(diǎn)等）分析該算法的實(shí)例及其優(yōu)缺點(diǎn)（哈夫曼編碼、單源最短路徑問(wèn)題(Dijkstra算法)、最小生成樹(shù)問(wèn)題(Prim算法、Kruskal算法)）挑選幾個(gè)經(jīng)典實(shí)例研究并用c+實(shí)現(xiàn)（多處最優(yōu)服務(wù)次序問(wèn)題、刪數(shù)問(wèn)題、汽車加油問(wèn)題、最優(yōu)合并問(wèn)題）總結(jié)。（2）研究方法1）文獻(xiàn)研究法：通過(guò)查詢資料來(lái)收集研究所需要的基礎(chǔ)知識(shí)；資料收集方式：利用網(wǎng)絡(luò)資源、查找相關(guān)書籍、收集有關(guān)研究課題內(nèi)容的報(bào)刊雜志等；2）個(gè)案研究法、實(shí)驗(yàn)法：在資料收集完成之上，建立課題研究結(jié)構(gòu)，思路清楚地對(duì)貪心算法的各方面進(jìn)行分析、探討、研究；包括：貪心算法的基本含義、基本原理和實(shí)現(xiàn)過(guò)程，其及貪心算法的性質(zhì)、貪心算法的特點(diǎn)及優(yōu)缺點(diǎn)等，分析由貪心算法解決的幾個(gè)經(jīng)典問(wèn)題的理論以及它們各自的優(yōu)缺點(diǎn)。從現(xiàn)實(shí)實(shí)際出發(fā)，從中選擇幾例進(jìn)行深入研究，并以C+語(yǔ)言實(shí)現(xiàn)完成。3）將所研究的內(nèi)容按合理的思路組合及實(shí)例實(shí)現(xiàn)完成一篇完整的課題論文；（3）研究進(jìn)度2009年10月-2009年11月， 根據(jù)課題研究的內(nèi)容，收集資料2009年11月- 2009年12月， 深入探討該算法中的幾個(gè)經(jīng)典問(wèn)題2009年12月- 2010年1月， 整理研究?jī)?nèi)容，并作進(jìn)一步的修改2010年1月- 2010年2月， 歸納總結(jié)，運(yùn)行程序成功后，形成一份完整的課題論文4.導(dǎo)師意見(jiàn)： 指導(dǎo)教師（簽名）：年 月 日5.系意見(jiàn)： 系（蓋章） 年 月 日說(shuō)明：開(kāi)題報(bào)告應(yīng)在教師指導(dǎo)下由學(xué)生獨(dú)立撰寫。在畢業(yè)論文（畢業(yè)設(shè)計(jì)）開(kāi)始二周內(nèi)完成，交指導(dǎo)教師審閱，并接受學(xué)校和學(xué)院檢查。正文貪心算法設(shè)計(jì)及其實(shí)際應(yīng)用研究蔣遠(yuǎn)麗西南大學(xué)榮昌校區(qū)信息管理系，重慶榮昌 402460摘要：貪心算法是指，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇,也就是說(shuō)，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。貪心算法不是對(duì)所有問(wèn)題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣泛的許多問(wèn)題也能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。本文首先介紹了貪心算法的核心、特點(diǎn)及算法本身存在的問(wèn)題，接下來(lái)介紹了前人已經(jīng)研究出來(lái)的成果，包括哈夫曼編碼、單源最短路徑、最小生成樹(shù)等。然后結(jié)合實(shí)踐，研究了多處最優(yōu)服務(wù)次序問(wèn)題、刪數(shù)問(wèn)題、汽車加油問(wèn)題、最優(yōu)合并問(wèn)題、會(huì)場(chǎng)安排問(wèn)題等。最后用代碼實(shí)現(xiàn)其中的兩個(gè)問(wèn)題，對(duì)貪心算法的具體實(shí)現(xiàn)方法做了詳細(xì)說(shuō)明。關(guān)鍵字：貪心算法；哈夫曼編碼；最小生成樹(shù)；最優(yōu)服務(wù)次序；汽車加油問(wèn)題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研究背景為了滿足人們對(duì)大數(shù)據(jù)量信息處理的渴望，為解決各種實(shí)際問(wèn)題，計(jì)算機(jī)算法學(xué)得到了飛速的發(fā)展，線性規(guī)劃、動(dòng)態(tài)規(guī)劃、貪心策略等一系列運(yùn)籌學(xué)模型紛紛運(yùn)用到計(jì)算機(jī)算法學(xué)中，產(chǎn)生了解決各種現(xiàn)實(shí)問(wèn)題的有效算法。雖然設(shè)計(jì)一個(gè)好的求解算法更像是一門藝術(shù)而不像是技術(shù)，但仍然存在一些行之有效的、能夠用于解決許多問(wèn)題的算法設(shè)計(jì)方法，你可以使用這些方法來(lái)設(shè)計(jì)算法，并觀察這些算法是如何工作的。一般情況下，為了獲得較好的性能，必須對(duì)算法進(jìn)行細(xì)致的調(diào)整。但是在某些情況下，算法經(jīng)過(guò)調(diào)整之后性能仍無(wú)法達(dá)到要求，這時(shí)就必須尋求另外的方法來(lái)求解該問(wèn)題。當(dāng)一個(gè)問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)和貪心選擇性質(zhì)時(shí)，貪心算法通常會(huì)給出一個(gè)簡(jiǎn)單、直觀和高效的解法。貪心算法通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解。它所作的每一個(gè)選擇都是在當(dāng)前狀態(tài)下具有某種意義的最好選擇，即貪心選擇；并且每次貪心選擇都能將問(wèn)題化簡(jiǎn)為一個(gè)更小的與原問(wèn)題具有相同形式的子問(wèn)題。盡管貪心算法對(duì)許多問(wèn)題不能總是產(chǎn)生整體最優(yōu)解，但對(duì)諸如最短路徑問(wèn)題、最小生成樹(shù)問(wèn)題，以及哈夫曼編碼問(wèn)題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問(wèn)題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動(dòng)態(tài)規(guī)劃算法更加簡(jiǎn)單、直觀和高效。1.2研究?jī)?nèi)容貪心算法的定義（是指從問(wèn)題的初始狀態(tài)出發(fā)，通過(guò)若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法），貪心算法的基本要素（最優(yōu)子結(jié)構(gòu)性質(zhì)、貪心選擇性質(zhì)）、貪心算法的思路及過(guò)程，貪心算法的核心（貪心策略）及特性（無(wú)回溯）、探討貪心算法存在的問(wèn)題。然后分析已有成果運(yùn)用貪心策略的解法（哈夫曼編碼、單源最短路徑問(wèn)題、最小生成樹(shù)等），結(jié)合實(shí)際中的例子（多處最優(yōu)服務(wù)次序問(wèn)題、刪數(shù)問(wèn)題、汽車加油問(wèn)題、會(huì)場(chǎng)安排問(wèn)題、最優(yōu)合并問(wèn)題），對(duì)貪心算法進(jìn)行分析與運(yùn)用。1.3研究目標(biāo)通過(guò)本課題的研究來(lái)探討貪心算法理論基礎(chǔ)以及對(duì)貪心策略在更多實(shí)例中的運(yùn)用做可行的研究，為貪心算法能夠運(yùn)用到更多的實(shí)際中的問(wèn)題作示范。1.4研究意義貪心算法是計(jì)算機(jī)算法策略中常用的一個(gè)，往往在需要解決一些最優(yōu)性問(wèn)題時(shí)，都可以應(yīng)用貪心算法。貪心算法的用法特點(diǎn)有：一是明顯的貪心，一般此類應(yīng)用問(wèn)題本身就是貪心；二是貪心數(shù)據(jù)結(jié)構(gòu)，如：堆，最小樹(shù)；三是可證明貪心策略的貪心，這是我們最常見(jiàn)的；四是博弈、游戲策略，這些策略大多是貪心；五是求較優(yōu)解或多次逼近最優(yōu)解。通過(guò)用貪心算法求解以上問(wèn)題，可以找到解決這些問(wèn)題的最優(yōu)算法，為其它的類似問(wèn)題的解決有示范和例證作用。1.5 本文組織本文從如下方面進(jìn)行組織：先提出貪心算法的基本知識(shí)，再?gòu)呢澬乃惴ǖ膸讉€(gè)現(xiàn)有的成果研究探討，然后對(duì)貪心算法中的幾個(gè)經(jīng)典問(wèn)題進(jìn)行研究，寫出其中兩個(gè)問(wèn)題的代碼，最后進(jìn)行總結(jié)。第2章 貪心算法的基本知識(shí)概述2.1 貪心算法定義貪心算法可以簡(jiǎn)單描述為：對(duì)一組數(shù)據(jù)進(jìn)行排序，找出最小值，進(jìn)行處理，再找出最小值，再處理。也就是說(shuō)貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。貪心算法是一種能夠得到某種度量意義下的最優(yōu)解的分級(jí)處理方法，通過(guò)一系列的選擇來(lái)得到一個(gè)問(wèn)題的解，而它所做的每一次選擇都是當(dāng)前狀態(tài)下某種意義的最好選擇，即貪心選擇。即希望通過(guò)問(wèn)題的局部最優(yōu)解來(lái)求出整個(gè)問(wèn)題的最優(yōu)解。這種策略是一種很簡(jiǎn)潔的方法，對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解，但不能保證總是有效，因?yàn)樗皇菍?duì)所有問(wèn)題都能得到整體最優(yōu)解，只能說(shuō)其解必然是最優(yōu)解的很好近似值。2.2 貪心算法的基本思路及實(shí)現(xiàn)過(guò)程2.2.1 貪心的基本思想用局部解構(gòu)造全局解，即從問(wèn)題的某一個(gè)初始解逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)某個(gè)算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。貪心算法思想的本質(zhì)就是分治，或者說(shuō)：分治是貪心的基礎(chǔ)。每次都形成局部最優(yōu)解，換一種方法說(shuō)，就是每次都處理出一個(gè)最好的方案。利用貪心策略解題，需要解決兩個(gè)問(wèn)題：（1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標(biāo)準(zhǔn)，以得到問(wèn)題的最優(yōu)/較優(yōu)解。2.2.2 貪心算法的實(shí)現(xiàn)過(guò)程（1）應(yīng)用同一規(guī)則F，將原問(wèn)題變?yōu)橐粋€(gè)相似的、但規(guī)模更小的子問(wèn)題；（2）從問(wèn)題的某一初始解出發(fā)：While（能朝給定目標(biāo)前進(jìn)一步） 求出可行解的一個(gè)解元素；（3）由所有解元素組合成問(wèn)題的一個(gè)可行解。2.3貪心算法的核心貪心算法的核心問(wèn)題是選擇能產(chǎn)生問(wèn)題最優(yōu)解的最優(yōu)度量標(biāo)準(zhǔn)，即具體的貪心策略。貪心策略是指從問(wèn)題的初始狀態(tài)出發(fā)，通過(guò)若干次的貪心選擇而得出最優(yōu)值(或較優(yōu)解)的一種解題方法。其實(shí)，從“貪心策略”一詞我們便可以看出，貪心策略總是做出在當(dāng)前看來(lái)是最優(yōu)的選擇，也就是說(shuō)貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問(wèn)題自身的特性決定了該題運(yùn)用貪心策略可以得到最優(yōu)解或較優(yōu)解。2.4貪心算法的基本要素2.4.1貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。在動(dòng)態(tài)規(guī)劃算法中，每步所做的選擇往往依賴于相關(guān)子問(wèn)題的解。因而只有在解出相關(guān)子問(wèn)題后，才能做出選擇。而在貪心算法中，僅在當(dāng)前狀態(tài)下做出最好選擇，即局部最優(yōu)選擇。然后再去解做出這個(gè)選擇后產(chǎn)生的相應(yīng)的子問(wèn)題。貪心算法所做的貪心選擇可以依賴于以往所做過(guò)的選擇，但決不依賴于將來(lái)所做的選擇，也不依賴于子問(wèn)題的解。正是由于這種差別，動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所做的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開(kāi)始。做了貪心選擇后，原問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題。然后，用數(shù)學(xué)歸納法證明，通過(guò)每一步做貪心選擇，最終可得到問(wèn)題的整體最優(yōu)解。其中，證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)。2.4.2最優(yōu)子結(jié)構(gòu)性質(zhì)當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。運(yùn)用貪心策略在每一次轉(zhuǎn)化時(shí)都取得了最優(yōu)解。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用貪心算法或動(dòng)態(tài)規(guī)劃算法求解的關(guān)鍵特征。貪心算法的每一次操作都對(duì)結(jié)果產(chǎn)生直接影響，而動(dòng)態(tài)規(guī)劃則不是。貪心算法對(duì)每個(gè)子問(wèn)題的解決方案都做出選擇，不能回退；動(dòng)態(tài)規(guī)劃則會(huì)根據(jù)以前的選擇結(jié)果對(duì)當(dāng)前進(jìn)行選擇，有回退功能。動(dòng)態(tài)規(guī)劃主要運(yùn)用于二維或三維問(wèn)題，而貪心一般是一維問(wèn)題。2.4.3貪心算法的特點(diǎn)貪心算法的最大特點(diǎn)就是快，通常是線性二次式，不需要多少額外的內(nèi)存。一般二次方級(jí)的存儲(chǔ)要浪費(fèi)額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時(shí)，這些空間可以幫助算法更容易實(shí)現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用。因?yàn)樗菀拙帉?，容易調(diào)試，速度極快，并且節(jié)約空間。幾乎可以說(shuō)，此時(shí)它是所有算法中最好的。但是應(yīng)該注意，貪心算法有兩大難點(diǎn)：（1）如何貪心怎樣用一個(gè)小規(guī)模的解構(gòu)造更大規(guī)模的解呢?總體上，這與問(wèn)題本身有關(guān)。但是大部分都是有規(guī)律的。正因?yàn)樨澬挠腥绱诵再|(zhì)，它才能比其他算法快。具有應(yīng)當(dāng)采用貪心算法的問(wèn)題，當(dāng)“貪心序列”中的每項(xiàng)互異且當(dāng)問(wèn)題沒(méi)有重疊性時(shí)，看起來(lái)總能通過(guò)貪心算法取得（近似）最優(yōu)解的?；蛘?，總有一種直覺(jué)在引導(dǎo)我們對(duì)一些問(wèn)題采用貪心算法。其中“找零錢”這個(gè)問(wèn)題就是一個(gè)例子。題中給出的硬幣面值事實(shí)上具有特殊性，如果面值發(fā)生變化，可能貪心算法就不能返回最優(yōu)解了。但是，值得指出的是，當(dāng)一個(gè)問(wèn)題具有多個(gè)最優(yōu)解時(shí)，貪心算法并不能求出所有最優(yōu)解。另外，我們經(jīng)過(guò)實(shí)踐發(fā)現(xiàn)，單純的貪心算法是順序處理問(wèn)題的；而且每個(gè)結(jié)果是可以在處理完一個(gè)數(shù)據(jù)后即時(shí)輸出的。（2）貪心的正確性要證明貪心性質(zhì)的正確性，才是貪心算法的真正挑戰(zhàn)，因?yàn)椴⒉皇敲看尉植孔顑?yōu)解都會(huì)與整體最優(yōu)解之間有聯(lián)系，往往靠貪心算法生成的解不是最優(yōu)解。這樣，貪心性質(zhì)的證明就成了貪心算法正確的關(guān)鍵。對(duì)某些問(wèn)題貪心性質(zhì)也許是錯(cuò)的，即使它在大部分?jǐn)?shù)據(jù)中都是可行的，但還必須考慮到所有可能出現(xiàn)的特殊情況，并證明該貪心性質(zhì)在這些特殊情況中仍然正確。而這樣容易陷入證明不正確貪心性質(zhì)的泥塘中無(wú)法自拔，因?yàn)樨澬乃惴ǖ倪m用范圍并不大，而且有一部分極難證明，若是沒(méi)有把握，最好不要冒險(xiǎn)，還有其他算法會(huì)比它要保險(xiǎn)。2.5 貪心算法的理論基礎(chǔ)正如前文所說(shuō)的那樣，貪心策略是最接近人類認(rèn)知思維的一種解題策略。但是，越是顯而易見(jiàn)的方法往往越難以證明。下面我們就來(lái)介紹貪心策略的理論擬陣?！皵M陣”理論是一種能夠確定貪心策略何時(shí)能夠產(chǎn)生最優(yōu)解的理論，雖然這套理論還很不完善，但在求解最優(yōu)化問(wèn)題時(shí)發(fā)揮著越來(lái)越重要的作用。擬陣M定義為滿足下面3個(gè)條件的有序?qū)Γ⊿，I）：（1）S是非空有限集；（2）I是S的一類具有遺傳性質(zhì)的獨(dú)立子集族，即若BI，則B是S的獨(dú)立子集，且B的任意子集也都是S的獨(dú)立子集?？占貫镮的成員；（3）I滿足交換性質(zhì)，即若AI，BI且|A|B|，則存在某一元素xB-A，使得AxI。定理2.1 擬陣M中所有極大獨(dú)立子集具有相同大小。引理2.1 （擬陣的貪心選擇性質(zhì)）設(shè)M=（S，I）是具有權(quán)函數(shù)M的帶權(quán)擬陣，且S中元素依權(quán)值從大到小排列，又設(shè)xS是S中第一個(gè)使得x是獨(dú)立子集元素，則存在S的最優(yōu)子集A使得xA。引理2.2 設(shè)M=(S，I)是擬陣。若S中元素x不是空集的一個(gè)可擴(kuò)元素，則x也不可能是S中任一獨(dú)立子集A的可擴(kuò)展元素。引理2.3 （擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì)）設(shè)x是求帶權(quán)擬陣M=（S，I）的最優(yōu)子集的貪心算法Greedy所選擇的S中的第一個(gè)元素。那么，原問(wèn)題可簡(jiǎn)化為求帶權(quán)擬陣M=（S，I）的最優(yōu)子集問(wèn)題，其中S=y|yS且x，yII=B|BS-x且BxIM的權(quán)函數(shù)是M的權(quán)函數(shù)在S上的限制（稱M為M關(guān)于元素x的收縮）。定理2.4（帶權(quán)擬陣貪心算法的正確性）高M(jìn)=（S，I）是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法Greedy返回M的最優(yōu)子集。適宜于用貪心策略來(lái)求解的許多問(wèn)題都可以歸結(jié)為在加權(quán)擬陣中找一個(gè)具有最大權(quán)值的獨(dú)立子集的問(wèn)題，即給定一個(gè)加權(quán)擬陣M=（S，I），若能找出一個(gè)獨(dú)立且具有最大可能權(quán)值的子集A，且A不被M中比它更大的獨(dú)立子集所包含，那么A為最優(yōu)子集，也是一個(gè)最大的獨(dú)立子集。我們認(rèn)為，針對(duì)絕大多數(shù)的信息學(xué)問(wèn)題，只要它具備了“擬陣”的結(jié)構(gòu)，便可用貪心策略求解。擬陣?yán)碚搶?duì)于我們判斷貪心策略是否適用于某一復(fù)雜問(wèn)題是十分有效的。2.6 貪心算法存在的問(wèn)題（1）不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來(lái)是最優(yōu)的選擇，因此并不從整體上加以考慮；（2）貪心算法只能用來(lái)求某些最大或最小解的問(wèn)題；（3）貪心算法只能確定某些問(wèn)題的可行性范圍。第3章 經(jīng)典問(wèn)題解決及其優(yōu)缺點(diǎn)3.1 哈夫曼編碼3.1.1 問(wèn)題描述哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來(lái)建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。3.1.2 編碼原理對(duì)每一個(gè)字符規(guī)定一個(gè)0，1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。由于任一字符的代碼都不是其他字符代碼的前綴，從編碼文件中不斷取出代表某一字符的前綴碼，轉(zhuǎn)換為原字符，即可逐個(gè)譯出文件中的所有字符。可以用二叉樹(shù)作為前綴編碼的數(shù)據(jù)結(jié)構(gòu)。在表示前綴碼的二叉樹(shù)中，樹(shù)葉代表給定的字符，并將每個(gè)字符的前綴碼看做是從樹(shù)根到代表該字符的樹(shù)葉的一條道路。代碼中每一位的0或1分別作為指示某結(jié)點(diǎn)到左兒子或右兒子的“路標(biāo)”。3.1.3 貪心算法策略設(shè)C是編碼字符集，C中字符c的頻率為f(c)。又設(shè)x和y是C中具有最小頻率的兩個(gè)字符，則存在C的最優(yōu)前綴碼使x和y具有相同碼長(zhǎng)且僅最后一位編碼不同。證明：設(shè)二叉樹(shù)T表示C的任意一個(gè)最優(yōu)前綴碼。下面證明可以對(duì)T做適當(dāng)修改后得到一棵新的二叉樹(shù)T，使得在新樹(shù)中，x和y是最深葉子且為兄弟。同時(shí)新樹(shù)T表示的前綴碼也是C的最優(yōu)前綴碼。如果能做到這一點(diǎn)，則x和y在T表示的最優(yōu)前綴碼中就具有相同的碼長(zhǎng)且僅最后一位編碼不同。設(shè)b和c是二叉樹(shù)T的最深葉子且為兄弟。不失一般性，可設(shè)f(b)f(c)，f(x)f(y)。由于x和y是C中具有最小頻率的兩個(gè)字符，故f(x)f(b)，f(y)f(c)。首先在樹(shù)T中交換葉子b和x的位置得到樹(shù)T，然后在樹(shù)T中再交換葉子c和y的位置。得到樹(shù)T。如圖3.1所示。xybcbyxcyccbTTTFig. 3.1 Counterchange the Coding-tree T圖3.1 編碼樹(shù)T的變換由此可知，樹(shù)T和T表示的前綴碼的平均碼長(zhǎng)之差為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最后一個(gè)不等式是因?yàn)閒(b)-f(x)和dT(b)-dT(x)均為非負(fù)。類似地，可以證明在T中交換y與c的位置也不增加平均碼長(zhǎng)，即B(T)-B(T)也是非負(fù)的。由此可知，B(T)B(T)B(T)。另一方面，由于T所表示的前綴碼是最優(yōu)的，故B(T)B(T)。因此，B(T)=B(T)，即T表示的前綴碼也是最優(yōu)前綴碼，且x和y具有最長(zhǎng)的碼長(zhǎng)，同時(shí)僅最后一位編碼不同。3.1.4 最優(yōu)子結(jié)構(gòu)性質(zhì)設(shè)T是表示字符集C的一個(gè)最優(yōu)前綴碼的完全二叉樹(shù)。C中字符c的出現(xiàn)頻率為f(c)。設(shè)x和y是樹(shù)T中的兩個(gè)葉子且為兄弟，z是它們的父親。若將z看做是具有頻率f(z)=f(x)+f(y)的字符，則樹(shù)T=T-x，y表示字符集C=C-x，yz的一個(gè)最優(yōu)前綴碼。證明：首先證明T的平均碼長(zhǎng)B(T)要用T的平均碼長(zhǎng)B(T)來(lái)表示。事實(shí)上，對(duì)任意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中的一個(gè)字符，故z在T中是一樹(shù)葉。若將x和y加入樹(shù)T中作為z的兒子，則得到表示字符集C的前綴碼的二叉樹(shù)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)前綴編碼樹(shù)。3.1.5 計(jì)算復(fù)雜性算法HuffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O（n）計(jì)算時(shí)間，由于最小堆的DeleteMin和Insert運(yùn)算均需O(logn)時(shí)間，n-1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。3.2單源最短路徑問(wèn)題(Dijkstra算法)3.2.1 問(wèn)題描述給定一個(gè)帶權(quán)有向圖G=(V，E)，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在我們要計(jì)算從源到所有其他各頂點(diǎn)的最短路徑長(zhǎng)度。這里的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。3.2.2 編碼原理設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。3.2.3 貪心算法策略Dijkstra算法是應(yīng)用貪心算法設(shè)計(jì)策略的一個(gè)典型例子。它所作的貪心選擇是從V-S中選擇具有最短特殊路徑的頂點(diǎn)u，從而確定從源到u的最短路徑長(zhǎng)度distu。這種貪心選擇為什么能導(dǎo)致最優(yōu)解呢？換句話說(shuō)，為什么從源到u沒(méi)有更短的其他