算法分析與設(shè)計(jì)論文

1、算法分析與設(shè)計(jì)論文 貪心算法引言：算法復(fù)雜性的高低體現(xiàn)在運(yùn)行該算法所需要的計(jì)算機(jī)資源多少上，所需要的資源越多，該算法的復(fù)雜性越高；反之，所需要的資源越少，該算法的復(fù)雜性越低。計(jì)算機(jī)資源最重要的是時(shí)間和空間資源，因此，算法的復(fù)雜性有時(shí)間復(fù)雜性和空間復(fù)雜性之分，不言而喻，設(shè)計(jì)復(fù)雜性盡可能低的算法是在設(shè)計(jì)算法時(shí)追求的重要目標(biāo)。為了滿足人們對(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è)好的求解算法更像是一門(mén)藝術(shù)而不像是技術(shù) ,但仍然存在一些行之有效的、能夠

2、用于解決許多問(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ù)

3、問(wèn)題，以及哈夫曼編碼問(wèn)題等具有最優(yōu)子結(jié)構(gòu)和貪心選擇性質(zhì)的問(wèn)題卻可以獲得整體最優(yōu)解。而且所給出的算法一般比動(dòng)態(tài)規(guī)劃算法更加簡(jiǎn)單、直觀和高效。摘 要在求最優(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ì)。

4、如果一個(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)題Greedy algorithm design and its practical applicationJiang YuanliDepartment of Information Management, Southwest University, Rongchang,

5、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

6、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 result

7、s 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 t

8、o 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、貪心算法定義：貪心算法可以簡(jiǎn)單描述為：對(duì)一組數(shù)據(jù)進(jìn)行排序，找出最小值，進(jìn)行處理，再找出最小值，再處理。也就是說(shuō)貪心算法是一種在每一步選擇中都采取在當(dāng)前狀態(tài)下最好或最優(yōu)的選擇，從而希望得到結(jié)果是最好或最優(yōu)的算法。貪心算法是

9、一種能夠得到某種度量意義下的最優(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、貪心算法的基本思路及實(shí)現(xiàn)過(guò)程貪心的基本思想:用局部解構(gòu)造全局解，即從問(wèn)題的某一個(gè)初始解逐步逼近給定的目標(biāo)，以盡可能快地求得更好的解。當(dāng)某個(gè)算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。貪心算法思想的本質(zhì)就是分治，或者說(shuō)：分治是貪心的基礎(chǔ)。每次都

10、形成局部最優(yōu)解，換一種方法說(shuō)，就是每次都處理出一個(gè)最好的方案。利用貪心策略解題，需要解決兩個(gè)問(wèn)題：（1）該題是否適合于用貪心策略求解；（2）如何選擇貪心標(biāo)準(zhǔn)，以得到問(wèn)題的最優(yōu)/較優(yōu)解。貪心算法的實(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è)可行解。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í)，從“

11、貪心策略”一詞我們便可以看出，貪心策略總是做出在當(dāng)前看來(lái)是最優(yōu)的選擇，也就是說(shuō)貪心策略并不是從整體上加以考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)解，而許多問(wèn)題自身的特性決定了該題運(yùn)用貪心策略可以得到最優(yōu)解或較優(yōu)解。4、貪心算法的特點(diǎn)貪心算法的最大特點(diǎn)就是快，通常是線性二次式，不需要多少額外的內(nèi)存。一般二次方級(jí)的存儲(chǔ)要浪費(fèi)額外的空間，而且那些空間經(jīng)常得不出正解。但是，使用貪心算法時(shí)，這些空間可以幫助算法更容易實(shí)現(xiàn)且更快執(zhí)行。如果有正確貪心性質(zhì)存在，那么一定要采用。因?yàn)樗菀拙帉?xiě)，容易調(diào)試，速度極快，并且節(jié)約空間。幾乎可以說(shuō)，此時(shí)它是所有算法中最好的。但是應(yīng)該注意，貪心算法有兩大難點(diǎn)：（1）

12、如何貪心怎樣用一個(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)題采用貪心算法。其中“找零錢(qiá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ù)

13、據(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)。5、貪心算法的理論基礎(chǔ)貪心策略是最接近人類認(rèn)知思維的一種解題策略。但是，越是顯而易見(jiàn)的方

14、法往往越難以證明。下面我們就來(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ú)立子集。空集必為I的成員；（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中元素

15、依權(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)擬陣，算法Gree

16、dy返回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)題是十分有效的。6、 舉例多處最優(yōu)服務(wù)次序問(wèn)題6.1.1 問(wèn)題的提出設(shè)有n個(gè)顧客同時(shí)等待一項(xiàng)服務(wù)。顧客i需要的服務(wù)時(shí)間為ti，1=i=n。共有s處可以提供此項(xiàng)服務(wù)。應(yīng)如何安排n個(gè)顧客的服務(wù)次序才能

17、使平均等待時(shí)間達(dá)到最小？平均等待時(shí)間是n個(gè)顧客等待服務(wù)時(shí)間的總和除以n。6.1.2 貪心選擇策略假設(shè)原問(wèn)題為T(mén)，而我們已經(jīng)知道了某個(gè)最優(yōu)服務(wù)系列，即最優(yōu)解為A=t(1)，t(2)，t(n)(其中t(i)為第i個(gè)用戶需要的服務(wù)時(shí)間)，則每個(gè)用戶等待時(shí)間為：T(1)=t(1)；T(2)=t(1)+t(2)；.T(n)：t(1)+t(2)+t(3)+t(n)；那么總等待時(shí)問(wèn)，即最優(yōu)值為：TA=n*t(1)+(n-1)*t(2)+(n+1-j)*t(i)+2*t(n-1)+t(n)；由于平均等待時(shí)間是n個(gè)顧客等待時(shí)間的總和除以n，故本題實(shí)際上就是求使顧客等待時(shí)間的總和最小的服務(wù)次序。本問(wèn)題采用貪心算法

18、求解，貪心策略如下：對(duì)服務(wù)時(shí)間最短的顧客先服務(wù)的貪心選擇策略。首先對(duì)需要服務(wù)時(shí)間最短的顧客進(jìn)行服務(wù)，即做完第一次選擇后，原問(wèn)題T變成了需對(duì)n-1個(gè)顧客服務(wù)的新問(wèn)題T。新問(wèn)題和原問(wèn)題相同，只是問(wèn)題規(guī)模由n減小為n-1?；诖朔N選擇策略，對(duì)新問(wèn)題T，選擇n-1顧客中選擇服務(wù)時(shí)間最短的先進(jìn)行服務(wù)，如此進(jìn)行下去，直至所有服務(wù)都完成為止。6.1.3 問(wèn)題的貪心選擇性質(zhì)先來(lái)證明該問(wèn)題具有貪心選擇性質(zhì)，即最優(yōu)服務(wù)A中t(1)滿足條件：t(1)=t(i)(2it(i)(i1)。 設(shè)另一服務(wù)序列B=（t(i)，t(2)，t(1)，t(n)）那么TA-TB=n*t(1)-t(i)+(n+1-i)t(i)-t(1)

19、=(1-i)*t(i)-t(1)0即TATB，這與A是最優(yōu)服務(wù)相矛盾。 故最優(yōu)服務(wù)次序問(wèn)題滿足貪心選擇性質(zhì)。6.1.4 問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)在進(jìn)行了貪心選擇后，原問(wèn)題T就變成了如何安排剩余的n-1個(gè)顧客的服務(wù)次序的問(wèn)題T，是原問(wèn)題的子問(wèn)題。若A是原問(wèn)題T的最優(yōu)解，則A=t(2)，t(i)t(n)是服務(wù)次序問(wèn)題子問(wèn)題T的最優(yōu)解。證明：假設(shè)A不是子問(wèn)題T的最優(yōu)解，其子問(wèn)題的最優(yōu)解為B，則有TBTA，而根據(jù)TA的定義知，TA十t(1)=TA。因此TB+t(1)TA+t(1)=TA，即存在一個(gè)比最優(yōu)值TA更短的總等待時(shí)間，而這與TA為問(wèn)題T的最優(yōu)值相矛盾。因此，A是子問(wèn)題T的最優(yōu)值。從以上貪心選擇及最

20、優(yōu)子結(jié)構(gòu)性質(zhì)的證明，可知對(duì)最優(yōu)服務(wù)次序問(wèn)題用貪心算法可求得最優(yōu)解。根據(jù)以上證明，最優(yōu)服務(wù)次序問(wèn)題可以用最短服務(wù)時(shí)間優(yōu)先的貪心選擇可以達(dá)到最優(yōu)解。故只需對(duì)所有服務(wù)先按服務(wù)時(shí)間從小到大進(jìn)行排序，然后按照排序結(jié)果依次進(jìn)行服務(wù)即可。平均等待時(shí)間即為T(mén)A/n。6.1.5 算法結(jié)果分析程序主要是花費(fèi)在對(duì)各顧客所需服務(wù)時(shí)間的排序和貪心算法，即計(jì)算平均服務(wù)時(shí)間上面。其中，貪心算法部分只有一重循環(huán)影響時(shí)間復(fù)雜度，其時(shí)間復(fù)雜度為O(n)：而排序在這里采用希爾(Shel1)排序，其時(shí)間復(fù)雜度為O(nlogn)。因此，綜合來(lái)看算法的時(shí)間復(fù)雜度為O(nlogn)。最優(yōu)合并問(wèn)題6.2.1 問(wèn)題的提出給定k個(gè)排好序的序列S

21、1，S2，Sk，用2路合并算法將這k個(gè)序列合并成一個(gè)序列。假設(shè)所采用的2路合并算法合并2個(gè)長(zhǎng)度分別為m和n的序列需要m+n-1次比較。試設(shè)計(jì)一個(gè)算法確定合并這個(gè)序列的最優(yōu)合并順序，使所需的總比較次數(shù)最少。為了進(jìn)行比較，還需要確定合并這個(gè)序列的最差合并順序，使所需的總比較次數(shù)最多。 6.2.2 原理分析 這個(gè)程序比較適合用堆，最優(yōu)用最小堆，最差用最大堆；以最優(yōu)合并為例：（1）使用各序列的長(zhǎng)度建堆； （2）兩個(gè)最小的元素出堆，計(jì)算這兩序列合并需要的比較次數(shù)，該次數(shù)入堆； （3）重復(fù)（2），直到堆只剩下一個(gè)元素； 最后剩下的元素即為題目的解。6.2.3 算法時(shí)間復(fù)雜度分析復(fù)雜度為O(nlogn)，排

22、序后，最小的兩個(gè)序列是前兩個(gè)，計(jì)算最小的兩個(gè)序列的合并次數(shù)后，該次數(shù)不一定是新的最小的兩個(gè)序列之一，所以在下一次合并前，必需使數(shù)組仍舊有序，讓最小的兩個(gè)序列在數(shù)組的最前面，為使數(shù)組重新有序，可以使用類似插入排序的插入過(guò)程，將新得到的數(shù)字直接插入到數(shù)組，這樣不需要額外的儲(chǔ)存空間，但總復(fù)雜度是O(n2)，考慮到需要計(jì)算最優(yōu)與最差，實(shí)際上也必須需要額外的O(n)的空間來(lái)保存排序后的結(jié)果，如果將排序后的數(shù)組按照順序作成一個(gè)鏈表，那么鏈表的最前的兩節(jié)點(diǎn)就是最小的兩序列，計(jì)算合并次數(shù)，刪除該兩節(jié)點(diǎn)，將新得到的次數(shù)插入到鏈表，注意到，后面需要插入的數(shù)字肯定比前面插入的數(shù)字大，所以從上一次插入的位置之后查找新的插入位置，這樣插入數(shù)字的總的時(shí)間復(fù)雜度是O(n)的，