貪心算法論文.doc

山東省農(nóng)業(yè)管理干部學(xué)院畢業(yè)論文題 目： 貪心算法應(yīng)用研究 姓 名 ： 盛國(guó)選 畢業(yè)學(xué)院 ： 山東省農(nóng)業(yè)管理干部學(xué)院 專業(yè)班級(jí) ： 08級(jí)計(jì)算機(jī)系軟件1班 學(xué) 號(hào) ： 2008052001208 指導(dǎo)教師 ： 張艷君 日 期 ： 年 月 日 XIV目 錄1. 貪心算法的基本知識(shí)概述21.1 貪心算法定義21.2 貪心算法的基本思路及實(shí)現(xiàn)過(guò)程21.3貪心算法的核心21.4貪心算法的基本要素21.5 貪心算法的理論基礎(chǔ)41.6 貪心算法存在的問(wèn)題52.貪心算法經(jīng)典應(yīng)用舉例52.1刪數(shù)問(wèn)題52.2 汽車加油問(wèn)題72.3會(huì)場(chǎng)安排問(wèn)題93.總結(jié)13參考文獻(xiàn)13摘 要在求最優(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)題緒 論 為了滿足人們對(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í)概述1.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)解的很好近似值。1.2 貪心算法的基本思路及實(shí)現(xiàn)過(guò)程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貪心算法的實(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è)可行解。1.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)解。1.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最優(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)題。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)解的?；蛘撸傆幸环N直覺(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)。1.5 貪心算法的理論基礎(chǔ)正如前文所說(shuō)的那樣，貪心策略是最接近人類認(rèn)知思維的一種解題策略。但是，越是顯而易見(jiàn)的方法往往越難以證明。下面我們就來(lái)介紹貪心策略的理論擬陣。“擬陣”理論是一種能夠確定貪心策略何時(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)題是十分有效的。1.6 貪心算法存在的問(wèn)題（1）不能保證求得的最后解是最佳的。由于貪心策略總是采用從局部看來(lái)是最優(yōu)的選擇，因此并不從整體上加以考慮；（2）貪心算法只能用來(lái)求某些最大或最小解的問(wèn)題；（3）貪心算法只能確定某些問(wèn)題的可行性范圍。2.貪心算法經(jīng)典應(yīng)用舉例2.1刪數(shù)問(wèn)題問(wèn)題的提出問(wèn)題提出：給定n位正整數(shù)a，去掉其中任意k=n個(gè)數(shù)字后，剩下的數(shù)字按原次序排列組成一個(gè)新的正整數(shù)。對(duì)于給定的n位正整數(shù)a和正整數(shù)k，設(shè)計(jì)一個(gè)算法找出剩下數(shù)字組成的新數(shù)最小的刪數(shù)方案。貪心算法策略分析：n位數(shù)a可表示為x1x2xixjxkxn，要?jiǎng)h去k位數(shù)，使得剩下的數(shù)字組成的整數(shù)最小。設(shè)本問(wèn)題為T，其最優(yōu)解A=(y1，y2yk)表示依次刪去的k個(gè)數(shù)，在刪去k個(gè)數(shù)后剩下的數(shù)字按原次序排成的新數(shù)。即最優(yōu)值記為TA。 本問(wèn)題采用貪心算法求解，采用最近下降點(diǎn)優(yōu)先的貪心策略：即x1x2xixj；如果xkxj，則刪去xj，即得到一個(gè)新的數(shù)且這個(gè)數(shù)為n一1位中為最小的數(shù)Nl，可表示為x1x2xixkxmxn。對(duì)N1而言，即刪去了1位數(shù)后，原問(wèn)題T變成了需對(duì)n-1位數(shù)刪去k-1個(gè)數(shù)新問(wèn)題T。新問(wèn)題和原問(wèn)題相同，只是問(wèn)題規(guī)模由n減小為n-1，刪去的數(shù)字個(gè)數(shù)由k減少為k-1?；诖朔N刪除策略，對(duì)新問(wèn)題T，選擇最近下降點(diǎn)的數(shù)進(jìn)行刪除，如此進(jìn)行下去，直至刪去k個(gè)數(shù)為止。問(wèn)題的貪心選擇性質(zhì) 先來(lái)證明該問(wèn)題具有貪心選擇性質(zhì)，即對(duì)問(wèn)題T刪除最近下降點(diǎn)的數(shù)xj后得到的N1是n一1位數(shù)是中最小的數(shù)。 根據(jù)數(shù)的進(jìn)制特點(diǎn)，對(duì)a按權(quán)展開(kāi)得： a=x1*10n-1+x2*10n-2+xi*10n-i+xj*10n-j+xk*10n-k+xn 則有：Nl=x1*10n-2+x2*10n-3+xi*10n-i-1+xk*10n-k+xn假設(shè)刪去的不是xj而是其它位，則有N2=x1*10n-2+x2*10n-3+xi*10n-i-1+xj*10n-k+xn因?yàn)橛衳1x2xixk，則有NlN2。 因此刪數(shù)問(wèn)題滿足貪心選擇性質(zhì)。 刪數(shù)問(wèn)題的C+代碼：#include #include using namespace std; int main() string n; int s,i,x,l,m; printf(請(qǐng)輸入一個(gè)正整數(shù)和將要?jiǎng)h去的個(gè)數(shù)!n); while(cinns) i=-1,m=0,x=0; l=n.length(); while(xni+1)/出現(xiàn)遞減,刪除遞減的首數(shù)字 n=n.erase(i,1); x+;/ x統(tǒng)計(jì)刪除數(shù)字的個(gè)數(shù) i=-1;/從頭開(kāi)始查遞減區(qū)間 if(i=l-x-2&xs) m=1;/已經(jīng)無(wú)遞減區(qū)間,m=1脫離循環(huán) printf(最后結(jié)果為:n); coutn.substr(0,l-s+x);/只打印剩下的左邊l-(s-x)個(gè)數(shù)字 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)在進(jìn)行了貪心選擇后，原問(wèn)題T就變成了對(duì)N1如何刪去k-1個(gè)數(shù)的問(wèn)題T，是原問(wèn)題的子問(wèn)題。若A=(xj，A)是原問(wèn)題T的最優(yōu)解，則A是子問(wèn)題T的最優(yōu)解，其最優(yōu)值為TA。 證明：假設(shè)A不是子問(wèn)題T的最優(yōu)解，其子問(wèn)題的最優(yōu)解為B，其最優(yōu)值記為TB，則有TBTA。而根據(jù)TA的定義可知：TA= TA+xj*1On-j，而TBTA，因此有TB+xj*1On-jN，則不可能到達(dá)終點(diǎn)；C 加油站間的距離相等，即i=aj=LN，則加油次數(shù)k=n/N(n%N=0)或k=n/N+1(n%N！=0)；D 加油站間的距離不相等，即i！=aj，則加油次數(shù)k通過(guò)貪心算法求解。貪心算法策略該題目求加油最少次數(shù)，即求最優(yōu)解的問(wèn)題，可分成幾個(gè)步驟，一般來(lái)說(shuō)，每個(gè)步驟的最優(yōu)解不一定是整個(gè)問(wèn)題的最優(yōu)解，然而對(duì)于有些問(wèn)題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問(wèn)題的求解過(guò)程看作是一系列選擇，從問(wèn)題的某一個(gè)初始解出發(fā)，向給定目標(biāo)推進(jìn)。推進(jìn)的每一階段不是依據(jù)某一個(gè)固定的遞推式，而是在每一個(gè)階段都看上去是一個(gè)最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。不斷地將問(wèn)題實(shí)例歸納為更小的相似的子問(wèn)題，并期望做出的局部最優(yōu)的選擇產(chǎn)生一個(gè)全局得最優(yōu)解。由于汽車是由始向終點(diǎn)方向開(kāi)的，我們最大的麻煩就是不知道在哪個(gè)加油站加油可以使我們既可以到達(dá)終點(diǎn)又可以使我們加油次數(shù)最少。提出問(wèn)題是解決的開(kāi)始。為了著手解決遇到的困難，取得最優(yōu)方案。我們可以假設(shè)不到萬(wàn)不得已我們不加油，即除非我們油箱里的油不足以開(kāi)到下一個(gè)加油站，我們才加一次油。在局部找到一個(gè)最優(yōu)的解。每加一次油我們可以看作是一個(gè)新的起點(diǎn)，用相同的遞歸方法進(jìn)行下去。最終將各個(gè)階段的最優(yōu)解合并為原問(wèn)題的解得到我們?cè)瓎?wèn)題的求解。貪心算法正確性證明(1)貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。對(duì)于一個(gè)具體的問(wèn)題，要確定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的一個(gè)整體最優(yōu)解。該題設(shè)在加滿油后可行駛的N千米這段路程上任取兩個(gè)加油站、，且距離始點(diǎn)比距離始點(diǎn)近，則若在加油不能到達(dá)終點(diǎn)那么在加油一定不能到達(dá)終點(diǎn)，因?yàn)閙+Nn+N，即在B點(diǎn)加油可行駛的路程比在A點(diǎn)加油可行駛的路程要長(zhǎng)n-m千米，所以只要終點(diǎn)不在B、C之間且在C的右邊的話，根據(jù)貪心選擇，為使加油次數(shù)最少就會(huì)選擇距離加滿油得點(diǎn)遠(yuǎn)一些的加油站去加油，因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。(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ì)。由于（b1，b2，bn）是這段路程加油次數(shù)最少的一個(gè)滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個(gè)加油站加油時(shí)，b1=1，則（b2，b3，bn）是從a2到an這段路程上加油次數(shù)最少且這段路程上的加油站個(gè)數(shù)為（a2，a3，an）的最優(yōu)解，即每次汽車中剩下的油不能在行駛到下一個(gè)加油站時(shí)我們才在這個(gè)加油站加一次油，每個(gè)過(guò)程從加油開(kāi)始行駛到再次加油滿足貪心且每一次加油后相當(dāng)于與起點(diǎn)具有相同的條件，每個(gè)過(guò)程都是相同且獨(dú)立，也就是說(shuō)加油次數(shù)最少具有最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心算法時(shí)間復(fù)雜度分析由于若想知道該在哪個(gè)加油站加油就必須遍歷所有的加油站，且不需要重復(fù)遍歷，所以時(shí)間復(fù)雜度為O(n)。2.3會(huì)場(chǎng)安排問(wèn)題問(wèn)題的提出假設(shè)要在足夠多的會(huì)場(chǎng)里安排一批活動(dòng)，并希望使用盡可能少的會(huì)場(chǎng)。設(shè)計(jì)一個(gè)有效的貪心算法進(jìn)行安排。(這個(gè)問(wèn)題實(shí)際上是著名的圖著色問(wèn)題。若將每一個(gè)活動(dòng)作為圖的一個(gè)頂點(diǎn)，不相容活動(dòng)間用邊相連。使相鄰頂點(diǎn)著有不同顏色的最小著色數(shù)，相應(yīng)于要找的最小會(huì)場(chǎng)數(shù)。) 數(shù)據(jù)輸入：由文件input.txt給出輸入數(shù)據(jù)。第一行有1個(gè)正整數(shù)k，表示有k個(gè)待安排的活動(dòng)。接下來(lái)的k行中，每行有2個(gè)正整數(shù)，分別表示k個(gè)待安排的活動(dòng)開(kāi)始時(shí)間和結(jié)束時(shí)間。時(shí)間以0點(diǎn)開(kāi)始的分鐘計(jì)。結(jié)果輸出：將編程計(jì)算出的最少會(huì)場(chǎng)數(shù)輸出到文件output.txt。會(huì)場(chǎng)安排問(wèn)題的C+代碼：#include using namespace std;int Partition(int a, int low, int high )/劃分int i,j;int x = alow;i = low;j = high;while(ij) while(ij&x aj) j = j - 1; if(ij) ai = aj; i=i+1; while(i= ai) i = i + 1; if(ij) aj = ai; j=j-1; ai = x; return i;void QuickSort(int a, int low, int high) int Position; if(low -1) n=1;for(;i=bs) /有一個(gè)活動(dòng)結(jié)束，新活動(dòng)可在已空閑的會(huì)場(chǎng)進(jìn)行。 s+;else n+; /要增開(kāi)一會(huì)場(chǎng) return n;int main( ) int n; cinn; int *st= new intn; int *et=new intn; for(int i=0;istieti; QuickSort(st,0,n-1); QuickSort(et,0,n-1); cout schedule(st,et,0,n-1) endl; delete st; delete et; return 0;輸入文件示例輸出文件示例input.txt output.txt 5 3 1 23 12 28 25 35 27 80 36 50 編碼分析根據(jù)會(huì)場(chǎng)安排問(wèn)題的定義，首先將問(wèn)題簡(jiǎn)化為：找出兩個(gè)活動(dòng)，若ei和ej滿足sifj或sjfi，則稱這兩個(gè)活動(dòng)相容，即問(wèn)題轉(zhuǎn)化為：要求找出最多相容會(huì)場(chǎng)集合A。問(wèn)題簡(jiǎn)化為對(duì)相容會(huì)場(chǎng)A的尋找，下面用貪心方法分析過(guò)程，根據(jù)題意，選取一種量度標(biāo)準(zhǔn)，然后按量度標(biāo)準(zhǔn)對(duì)n個(gè)輸入排序，按順序一次輸入一個(gè)量。如果這個(gè)輸入和當(dāng)前已構(gòu)成在這種量度意義下的部分最優(yōu)解加在一起不能產(chǎn)生一個(gè)可行解，則不把此輸入加到這部分解中，這種能夠得到某種量度意義下的最優(yōu)解的分級(jí)處理方法就是貪心方法。那么問(wèn)題轉(zhuǎn)化為對(duì)度量標(biāo)準(zhǔn)的尋找，判斷各個(gè)數(shù)據(jù)是否可以包含在解向量中去，然后根據(jù)目標(biāo)函數(shù)來(lái)選擇最優(yōu)解。貪心算法（1）將所有活動(dòng)按結(jié)束時(shí)間排序，得到活動(dòng)集合E=e1，e2，en；（2）先將e1選入結(jié)果集合A中，即A=e1；（3）依次掃描每一個(gè)活動(dòng)ei：如果ei的開(kāi)始時(shí)間晚于最后一個(gè)選入A的活動(dòng)ej的結(jié)束時(shí)間，則將ei選入A中，否則放棄ei。最優(yōu)解證明若E=e1，e2en是按結(jié)束時(shí)間排序的活動(dòng)集合，則e1具有最早的結(jié)束時(shí)間，設(shè)存在一個(gè)最優(yōu)安排A不包含e1，并以ei開(kāi)始，則易見(jiàn)：A-eie1也是最優(yōu)的活動(dòng)安排；依此類推，即可推出上述活動(dòng)都為A中的不相容最優(yōu)活動(dòng)。俗話所的好的：紙上得來(lái)終覺(jué)淺，絕知此事要躬行！那么讓我們舉個(gè)例子來(lái)進(jìn)一步清晰化問(wèn)題：下面表格有12個(gè)活動(dòng)，并給出各個(gè)活動(dòng)的開(kāi)始時(shí)間與結(jié)束時(shí)間，那么請(qǐng)用上述貪心解法分析并求解最優(yōu)會(huì)場(chǎng)數(shù)