貪心算法介紹

貪心算法思想：顧名思義，貪心算法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對(duì)所有問(wèn)題都得到整體最優(yōu)解，但對(duì)許多問(wèn)題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問(wèn)題，最小生成樹(shù)問(wèn)題等。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。貪心算法的基本要素：貪心選擇性質(zhì)。所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(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)解。當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。貪心算法的基本思路：從問(wèn)題的某一個(gè)初始解出發(fā)逐步逼近給定的目標(biāo)，以盡可能快的地求得更好的解。當(dāng)達(dá)到算法中的某一步不能再繼續(xù)前進(jìn)時(shí)，算法停止。該算法存在問(wèn)題：不能保證求得的最后解是最佳的；不能用來(lái)求最大或最小解問(wèn)題；只能求滿足某些約束條件的可行解的范圍。實(shí)現(xiàn)該算法的過(guò)程：從問(wèn)題的某一初始解出發(fā)；while能朝給定總目標(biāo)前進(jìn)一步do求出可行解的一個(gè)解元素；由所有解元素組合成問(wèn)題的一個(gè)可行解；用背包問(wèn)題來(lái)介紹貪心算法：背包問(wèn)題：有一個(gè)背包，背包容量是M=150。有7個(gè)物品，物品可以分割成任意大小。要求盡可能讓裝入背包中的物品總價(jià)值最大，但不能超過(guò)總?cè)萘俊Ｎ锲稟BCDEFG重量35306050401025價(jià)值10403050354030分析如下目標(biāo)函數(shù)：Epi最大約束條件是裝入的物品總重量不超過(guò)背包容量：Ewi<=M(M=150)。根據(jù)貪心的策略，每次挑選價(jià)值最大的物品裝入背包，得到的結(jié)果是否最優(yōu)？每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？每次選取單位重量?jī)r(jià)值最大的物品，成為解本題的策略。值得注意的是，貪心算法并不是完全不可以使用，貪心策略一旦經(jīng)過(guò)證明成立后，它就是一種高效的算法。貪心算法還是很常見(jiàn)的算法之一，這是由于它簡(jiǎn)單易行，構(gòu)造貪心策略不是很困難?？上У氖?，它需要證明后才能真正運(yùn)用到題目的算法中。一般來(lái)說(shuō)，貪心算法的證明圍繞著：整個(gè)問(wèn)題的最優(yōu)解一定由在貪心策略中存在的子問(wèn)題的最優(yōu)解得來(lái)的。對(duì)于背包問(wèn)題中的3種貪心策略，都是無(wú)法成立(無(wú)法被證明)的，解釋如下：貪心策略：選取價(jià)值最大者。反例：W=30物品：ABC重量：281212價(jià)值：302020根據(jù)策略，首先選取物品A，接下來(lái)就無(wú)法再選取了，可是，選取B、C則更好。貪心策略：選取重量最小。它的反例與第一種策略的反例差不多。貪心策略：選取單位重量?jī)r(jià)值最大的物品。反例：W=30物品：ABC重量：282010價(jià)值：282010根據(jù)策略，三種物品單位重量?jī)r(jià)值一樣，程序無(wú)法依據(jù)現(xiàn)有策略作出判斷，如果選擇A，則答案錯(cuò)誤。所以需要說(shuō)明的是，貪心算法可以與隨機(jī)化算法一起使用，具體的例子就不再多舉了。(因?yàn)檫@一類(lèi)算法普及性不高，而且技術(shù)含量是非常高的，需要通過(guò)一些反例確定隨機(jī)的對(duì)象是什么，隨機(jī)程度如何，但也是不能保證完全正確，只能是極大的幾率正確)。幾種常見(jiàn)的貪心算法有人說(shuō)貪心算法是最簡(jiǎn)單的算法，原因很簡(jiǎn)單：你我其實(shí)都很貪，根本不用學(xué)。有人說(shuō)貪心算法是最復(fù)雜的算法，原因也很簡(jiǎn)單：這世上貪的人太多了，那輪到你我的份？不論難度如何，貪心算法都是一個(gè)很重要的算法，我在網(wǎng)上以及書(shū)上題目中，總結(jié)了三類(lèi)較為常見(jiàn)，也十分經(jīng)典的貪心算法，這里略表介紹。(注：由于沒(méi)有現(xiàn)成的名字可用，這三種類(lèi)型貪心算法的名字都是我自己取的，只是用一個(gè)詞語(yǔ)去表達(dá)一類(lèi)的貪心問(wèn)題)。線段覆蓋(linescover)題目大意：在一維空間中告訴你N條線段的起始坐標(biāo)與終止坐標(biāo)，要求求出這些線段一共覆蓋了多大的長(zhǎng)度。解題思路：將線段按其坐標(biāo)進(jìn)行排序(排序的具體方法:按起始坐標(biāo)排，起始坐標(biāo)相同的按終止坐標(biāo)排，都是小在前大在后)，使之依次遞增，并按順序分別編號(hào)為X(i),X(i).a代表其起始坐標(biāo)，X(i).b代表其終止坐標(biāo)。然后按排好的順序依次處理：定義一個(gè)變量last記錄考慮到當(dāng)前線段之時(shí)被線段覆蓋的最大的坐標(biāo)值，再定義一個(gè)變量length記錄當(dāng)前線段覆蓋的長(zhǎng)度。對(duì)于后面的線段，我們把它看成由兩個(gè)部分組成，即把它分成last之前的線段和last之后的線段。(如果線段全部處在last之后，其last之前的部分不存在。)由于我們排過(guò)序，我們可以肯定當(dāng)前考慮的線段X(i)其處在last之前的部分不會(huì)對(duì)length造成影響(因?yàn)閄(i-1).b=last，X(i).a>=X(i-1).a，即X(i)在last之前的部分所處位置肯定被線段X(i-1)覆蓋過(guò))，所以會(huì)對(duì)length產(chǎn)生影響的即是X(i)處在last之后的部分。所以我們可以依次對(duì)每條線段做如下處理：(初始化length為零，last為負(fù)無(wú)窮)length+=X(i).b-last(X(i).a<=last且X(i).b>=last)length+=X(i).b-X(i).a(X(i).a>last)last=X(i).b;最后length就為我們所需要的答案。最優(yōu)數(shù)對(duì)(bestpair)題目大意：按遞增的順序告訴你N個(gè)正整數(shù)和一個(gè)實(shí)數(shù)P，要求求出求出該數(shù)列中的比例最接近P的兩個(gè)數(shù)(保證絕對(duì)沒(méi)有兩個(gè)數(shù)使得其比值為P)。解題思路：定義兩個(gè)指針i和j，先初始化i=j=1，然后進(jìn)行如下操作：當(dāng)code[j]/code[i]>p時(shí)，inc(j)；當(dāng)code[j]/code[i]<p時(shí)，inc(i)。記錄其中產(chǎn)生的最優(yōu)值即為答案。3.連續(xù)數(shù)之和最大值(maxsum)題目大意：給出一個(gè)長(zhǎng)度為N的數(shù)列(數(shù)列中至少有一個(gè)正數(shù))，要求求出其中的連續(xù)數(shù)之和的最大值。(也可以加入a和b來(lái)限制連續(xù)數(shù)的長(zhǎng)度不小于a且不大于b)。解題思路：先說(shuō)不加限制的那種，定義一個(gè)統(tǒng)計(jì)變量tot，然后用循環(huán)進(jìn)行如下操作：inc(tot，item)其中如果出現(xiàn)tot<0的情況，則將tot賦值為0。在循環(huán)過(guò)程之中tot出現(xiàn)的最大值即為答案。如果加入了限制條件的話，問(wèn)題就變得難一些了(這句真的不是廢話)。為此我們先定義數(shù)組sum[i]來(lái)表示code[1]到code[i]之和（這樣的話code[a]~code[b]的和我們就可以用sum[b]-sum[a-1]來(lái)表示了）。再維護(hù)一個(gè)數(shù)組hash[i]來(lái)表示滿足條件的sum[a-1]的下標(biāo)，并使之按遞增順序排列，這樣當(dāng)前以第i的數(shù)為終止的數(shù)列的最大值肯定就是sum[i]-sum[hash[1]]?，F(xiàn)在我們來(lái)討論hash數(shù)組之中的數(shù)據(jù)需要滿足的條件和如何維護(hù)的具體問(wèn)題：當(dāng)考慮到以第i個(gè)數(shù)為結(jié)尾時(shí)，hash[i]所表示的下標(biāo)需要滿足的第一個(gè)條件就是題目規(guī)定的長(zhǎng)度限制，我們需要實(shí)時(shí)的加入滿足長(zhǎng)度規(guī)定的下標(biāo)，刪除不符合要求的下標(biāo)。其次，與不加限制條件時(shí)相同，若sum[i]-sum[hash[1]]的值小于零，則清空數(shù)組hash。維護(hù)時(shí)可以這樣，當(dāng)考慮到第i個(gè)數(shù)時(shí)，我們就將下標(biāo)i-a+1加入到hash中，因?yàn)閔ash中原來(lái)已經(jīng)排好序，因此我們我們可以用插入排序來(lái)維護(hù)hash的遞增性，然后我們考察hash[1]，若hash[1]<i-b+1，則證明其已超出長(zhǎng)度限制，我們就將其刪除，接著再考慮更新后的hash[1]，如此重復(fù)直至找到一個(gè)滿足條件的hash[1]為止。我們可以用鏈表來(lái)表示hash，這樣就可以減少數(shù)據(jù)加入和刪除時(shí)頻繁數(shù)據(jù)移動(dòng)的時(shí)間消耗。記錄下sum[i]-sum[hash[1]]的最大值即為答案。動(dòng)態(tài)規(guī)劃和貪心算法相同與不同：相同點(diǎn)：動(dòng)態(tài)規(guī)劃和貪心算法都是一種遞推算法；均有局部最優(yōu)解來(lái)推導(dǎo)全局最優(yōu)解；不同點(diǎn)：貪心算法：貪心算法中，作出的每步貪心決策都無(wú)法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留。由（1）中的介紹，可以知道貪心法正確的條件是：每一步的最優(yōu)解一定包含上一步的最優(yōu)解。動(dòng)態(tài)規(guī)劃算法：全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解。動(dòng)態(tài)規(guī)劃的關(guān)鍵是狀態(tài)轉(zhuǎn)移方程，即如何由以求出的局部最優(yōu)解來(lái)推導(dǎo)全局最優(yōu)。邊界條件：即最簡(jiǎn)單的，可以直接得出的局部最優(yōu)解。貪心算法的理論基礎(chǔ)：借助于擬陣工具，可建立關(guān)于貪心算法的較一般的理論。這個(gè)理論對(duì)確定何時(shí)使用貪心算法可以得到問(wèn)題的整體最優(yōu)解十分有用。1.擬陣擬陣M定義為滿足下面3個(gè)條件的有序?qū)?S,I)：S是非空有限集。1是S的一類(lèi)具有遺傳性質(zhì)的獨(dú)立子集族，即若Bel，則B是S的獨(dú)立子集，且B的任意子集也都是S的獨(dú)立子集。空集0必為I的成員。1滿足交換性質(zhì)，即若AeI,BeI且IAI<IBI，則存在某一元素xeB-A，使得AU{x}eI。例如，設(shè)S是一給定矩陣中行向量的集合，I是S的線性獨(dú)立子集族，則由線性空間理論容易證明(S,I)是一擬陣。擬陣的另一個(gè)例子是無(wú)向圖G=(V,E)的圖擬陣。給定擬陣M=(S,I)，對(duì)于I中的獨(dú)立子集AeI，若S有一元素xeA，使得將x加入A后仍保持獨(dú)立性，即AU{x}eI,則稱x為A的可擴(kuò)展元素。當(dāng)擬陣M中的獨(dú)立子集A沒(méi)有可擴(kuò)展元素時(shí)，稱A為極大獨(dú)立子集。下面的關(guān)于極大獨(dú)立子集的性質(zhì)是很有用的。定理1：擬陣M中所有極大獨(dú)立子集大小相同。這個(gè)定理可以用反證法證明。若對(duì)擬陣M=(S,I)中的S指定權(quán)函數(shù)W，使得對(duì)于任意xeS，有W(x)>0，則稱擬陣M為帶權(quán)擬陣。依此權(quán)函數(shù)，S的任一子集A的權(quán)定義為。2.關(guān)于帶權(quán)擬陣的貪心算法許多可以用貪心算法求解的問(wèn)題可以表示為求帶權(quán)擬陣的最大權(quán)獨(dú)立子集問(wèn)題。給定帶權(quán)擬陣M=(S,I)，確定S的獨(dú)立子集AeI使得W(A)達(dá)到最大。這種使W(A)最大的獨(dú)立子集A稱為擬陣M的最優(yōu)子集。由于S中任一元素x的權(quán)W(x)是正的，因此，最優(yōu)子集也一定是極大獨(dú)立子集。例如，在最小生成樹(shù)問(wèn)題可以表示為確定帶權(quán)擬陣的最優(yōu)子集問(wèn)題。求帶權(quán)擬陣的最優(yōu)子集A的算法可用于解最小生成樹(shù)問(wèn)題。下面給出求帶權(quán)擬陣最優(yōu)子集的貪心算法。該算法以具有正權(quán)函數(shù)W的帶權(quán)擬陣M=(S,I)作為輸入，經(jīng)計(jì)算后輸出M的最優(yōu)子集A。Setgreedy(M,W){A=0;將S中元素依權(quán)值W(大者優(yōu)先)組成優(yōu)先隊(duì)列；while(S!=0){S.removeMax(x