0021算法筆記——【貪心算法】貪心算法與活動(dòng)安排問(wèn)題

1、0021算法筆記一一【貪心算法】貪心算法與活動(dòng)安排問(wèn)題1、貪心算法原理：在對(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)解的近似解。(2)特性:貪心算法采用自頂向下,以迭代的方法做出相繼的貪心選擇，每做一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為一個(gè)規(guī)模更小的子問(wèn)題，通過(guò)每一步貪心選擇，可得到問(wèn)題的一個(gè)最優(yōu)解，雖然每一步上都要保證能獲得局部最優(yōu)解，但由此產(chǎn)生的全局解有時(shí)不一定是最優(yōu)的，所以貪婪法不要回溯。能夠用貪心算法求解的問(wèn)題一般具有兩

2、個(gè)重要特性：貪心選擇性質(zhì)禾口最優(yōu)子結(jié)構(gòu)性質(zhì)。貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素。貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。證明的大致過(guò)程為：首先考察問(wèn)題的一個(gè)整體最優(yōu)解，并證明可修改這個(gè)最優(yōu)解，使其以貪心選擇開(kāi)始。做了貪心選擇后，原問(wèn)題簡(jiǎn)化為規(guī)模更小的類(lèi)似子問(wèn)題。然后用數(shù)學(xué)歸納法證明通過(guò)每一步做貪心選擇，最終可得到問(wèn)題的

3、整體最優(yōu)解。其中，證明貪心選擇后的問(wèn)題簡(jiǎn)化為規(guī)模更小的類(lèi)似子問(wèn)題的關(guān)鍵在于利用該問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)刃最優(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ì)。貪心算法與動(dòng)態(tài)規(guī)劃算法的差異動(dòng)態(tài)規(guī)劃和貪心算法都是一種遞推算法，均有最優(yōu)子結(jié)構(gòu)性質(zhì)，通過(guò)局部最優(yōu)解來(lái)推導(dǎo)全局最優(yōu)解。兩者之間的區(qū)別在于：貪心算法中作出的每步貪心決策都無(wú)法改變，因?yàn)樨澬牟呗允怯缮弦徊降淖顑?yōu)解推導(dǎo)下一步的最優(yōu)解，而上一部之前的最優(yōu)解則不作保留，貪心算法每一步的最優(yōu)解一定包含上一步的最優(yōu)解。動(dòng)態(tài)規(guī)劃算法中全局最優(yōu)解中一定包含某個(gè)局部最優(yōu)解，但不一定包含前一個(gè)局部最優(yōu)解，因此需要記錄之前的所有最優(yōu)解。

4、他基本思路：1）建立數(shù)學(xué)模型來(lái)描述問(wèn)題。2）把求解的問(wèn)題分成若干個(gè)子問(wèn)題。3）對(duì)每一子問(wèn)題求解，得到子問(wèn)題的局部最優(yōu)解。4）把子問(wèn)題的解局部最優(yōu)解合成原來(lái)解問(wèn)題的一個(gè)解。2、活動(dòng)安排問(wèn)題活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。問(wèn)題描述T設(shè)有n個(gè)活動(dòng)的集合E=1,2,n，其中每個(gè)活動(dòng)都要求使用同一資源，如演講會(huì)場(chǎng)等，而在同一時(shí)間內(nèi)只有一個(gè)活動(dòng)能使用這一資源。每個(gè)活動(dòng)i都有一個(gè)要求使用該資源的起始時(shí)間si和一個(gè)結(jié)束時(shí)間

5、fi,且sivfi。如果選擇了活動(dòng)i,貝怕在半開(kāi)時(shí)間區(qū)間si,fi）內(nèi)占用資源。若區(qū)間si,fi）與區(qū)間sj,fj）不相交，則稱活動(dòng)i與活動(dòng)j是相容的。也就是說(shuō)，當(dāng)sifj或sjfi時(shí)，活動(dòng)i與活動(dòng)j相容?；顒?dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合。求解思路：將活動(dòng)按照結(jié)束時(shí)間進(jìn)行從小到大排序。然后用i代表第i個(gè)活動(dòng)，si代表第i個(gè)活動(dòng)開(kāi)始時(shí)間，fi代表第i個(gè)活動(dòng)的結(jié)束時(shí)間。按照從小到大排序，挑選出結(jié)束時(shí)間盡量早的活動(dòng)，并且滿足后一個(gè)活動(dòng)的起始時(shí)間晚于前一個(gè)活動(dòng)的結(jié)束時(shí)間，全部找出這些活動(dòng)就是最大的相容活動(dòng)子集合。事實(shí)上系統(tǒng)一次檢查活動(dòng)i是否與當(dāng)前已選擇的所有活動(dòng)相容。若相容

6、活動(dòng)i加入已選擇活動(dòng)的集合中，否則，不選擇活動(dòng)i,而繼續(xù)下一活動(dòng)與集合A中活動(dòng)的相容性。若活動(dòng)i與之相容，則i成為最近加入集合A的活動(dòng)，并取代活動(dòng)j的位置。下面給出求解活動(dòng)安排問(wèn)題的貪心算法，各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中，且按結(jié)束時(shí)間的非減序排列。如果所給的活動(dòng)未按此序排列，可以用O(nlogn)的時(shí)間重排。具體代碼如下：cppviewplaincopy/4d1活動(dòng)安排問(wèn)題貪心算法#includestdafx.h#includeusingnamespacestd;5.templateclassTypevoidGreedySelector(intn,Types,Typef,boo

7、lA);8.constintN=11;10.intmain()/下標(biāo)從1開(kāi)始，存儲(chǔ)活動(dòng)開(kāi)始時(shí)間ints=0,1,3,0,5,3,5,6,8,8,2,12;15./下標(biāo)從1開(kāi)始，存儲(chǔ)活動(dòng)結(jié)束時(shí)間intf=0,4,5,6,7,8,9,10,11,12,13,14;18.boolAN+1;20.cout各活動(dòng)的開(kāi)始時(shí)間，結(jié)束時(shí)間分別為：endl;for(inti=1;i=N;i+)TOC o 1-5 h zcouti:(si,fi)endl;GreedySelector(N,s,f,A);cout最大相容活動(dòng)子集為：endl;for(inti=1;i=N;i+)if(Ai)cout”i”:”(”si

8、”，”fi”)”endl;TOC o 1-5 h z34.return0;37.templateclassTypevoidGreedySelector(intn,Types,Typef,boolA)3.54.55.A1=true；intj=1;/記錄最近一次加入A中的活動(dòng)for(inti=2;i=fj)Ai=true;j=i;elseAi=false;由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間I勺相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)

9、留下盡可能多的時(shí)。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)，算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需0(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下:算法greedySelector的計(jì)算過(guò)程如下圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si

10、小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi,則不選擇活動(dòng)i,否則選擇活動(dòng)i加入集合A中。貪心算法并不總能求得問(wèn)題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問(wèn)題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。證明如下：設(shè)E=0,1,2,，n-1為所給的活動(dòng)集合。由于E中活動(dòng)安排安結(jié)束時(shí)間的非減序排列，所以活動(dòng)0具有最早完成時(shí)間。首先證明活動(dòng)安排問(wèn)題有一個(gè)最優(yōu)解以貪心選擇開(kāi)始，即該最優(yōu)解中包含活動(dòng)0設(shè)a是所給的活動(dòng)安排問(wèn)題的一個(gè)最優(yōu)解，且a中活動(dòng)也按結(jié)束時(shí)間非減序排列，a中的第一個(gè)活動(dòng)是活動(dòng)k。如k=0，則a就是一個(gè)以貪心選擇開(kāi)始的最優(yōu)解。若k0,則我們?cè)O(shè)b=a-kU0。由于end0sendk,且a中活動(dòng)是互為相容的，故b中的活動(dòng)也是互為相容的。又由于b中的活動(dòng)個(gè)數(shù)與a中活動(dòng)個(gè)數(shù)相同，且a是最優(yōu)的，故b也是最優(yōu)的。也就是說(shuō)b是一個(gè)以貪心選擇活