1、貪心法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想 貪心法的求解過(guò)程貪心法的求解過(guò)程貪心法的基本要素貪心法的基本要素 貪心法在解決問(wèn)題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解Optimal Solution），但通常能獲得近似最優(yōu)解Near-Optimal Solution）。1 貪心法的設(shè)計(jì)思想貪心法的設(shè)計(jì)思想 例：用貪心法求解付款問(wèn)題。例：用貪心法求解付款問(wèn)題。假設(shè)有面值為假設(shè)有面值為5元、元、2元、元、1元、元、5角、角

2、、2角、角、1角的貨幣，需角的貨幣，需要找給顧客要找給顧客4元元6角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首先選出先選出1張面值不超過(guò)張面值不超過(guò)4元元6角的最大面值的貨幣，即角的最大面值的貨幣，即2元，元，再選出再選出1張面值不超過(guò)張面值不超過(guò)2元元6角的最大面值的貨幣，即角的最大面值的貨幣，即2元，元，再選出再選出1張面值不超過(guò)張面值不超過(guò)6角的最大面值的貨幣，即角的最大面值的貨幣，即5角，再選角，再選出出1張面值不超過(guò)張面值不超過(guò)1角的最大面值的貨幣，即角的最大面值的貨幣，即1角，總共付出角，總共付出4張貨幣。張貨幣。 在付款問(wèn)題每一步的貪心選擇中，在不超過(guò)

3、應(yīng)付在付款問(wèn)題每一步的貪心選擇中，在不超過(guò)應(yīng)付款金額的條件下，只選擇面值最大的貨幣，而不去考慮款金額的條件下，只選擇面值最大的貨幣，而不去考慮在后面看來(lái)這種選擇是否合理，而且它還不會(huì)改變決定：在后面看來(lái)這種選擇是否合理，而且它還不會(huì)改變決定：一旦選出了一張貨幣，就永遠(yuǎn)選定。付款問(wèn)題的貪心選一旦選出了一張貨幣，就永遠(yuǎn)選定。付款問(wèn)題的貪心選擇策略是盡可能使付出的貨幣最快地滿足支付要求，其擇策略是盡可能使付出的貨幣最快地滿足支付要求，其目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心目的是使付出的貨幣張數(shù)最慢地增加，這正體現(xiàn)了貪心法的設(shè)計(jì)思想。法的設(shè)計(jì)思想。貪心法求解的問(wèn)題的特征：貪心法求解的問(wèn)題的

4、特征：（1最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問(wèn)題滿足最稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，也稱此問(wèn)題滿足最優(yōu)性原理。優(yōu)性原理。（2貪心選擇性質(zhì)貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指問(wèn)題的整體最優(yōu)解可以所謂貪心選擇性質(zhì)是指問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)得到。通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)得到。v 動(dòng)態(tài)規(guī)劃法通常以自底向上的方式求解各個(gè)子問(wèn)題，而貪心法則通常以自頂向下的方式做出一系列的貪心選擇。2 貪心法的求解過(guò)程貪心法的求解過(guò)程 用貪心法求解問(wèn)題應(yīng)該考慮如下幾

5、個(gè)方面：（1候選集合C：為了構(gòu)造問(wèn)題的解決方案，有一個(gè)候選集合C作為問(wèn)題的可能解，即問(wèn)題的最終解均取自于候選集合C。例如，在付款問(wèn)題中，各種面值的貨幣構(gòu)成候選集合。（2解集合S：隨著貪心選擇的進(jìn)行，解集合S不斷擴(kuò)展，直到構(gòu)成一個(gè)滿足問(wèn)題的完整解。例如，在付款問(wèn)題中，已付出的貨幣構(gòu)成解集合。 （3解決函數(shù)solution：檢查解集合S是否構(gòu)成問(wèn)題的完整解。例如，在付款問(wèn)題中，解決函數(shù)是已付出的貨幣金額恰好等于應(yīng)付款。 （4選擇函數(shù)select：即貪心策略，這是貪心法的關(guān)鍵，它指出哪個(gè)候選對(duì)象最有希望構(gòu)成問(wèn)題的解，選擇函數(shù)通常和目標(biāo)函數(shù)有關(guān)。例如，在付款問(wèn)題中，貪心策略就是在候選集合中選擇面值最大

6、的貨幣。 （5可行函數(shù)feasible：檢查解集合中加入一個(gè)候選對(duì)象是否可行，即解集合擴(kuò)展后是否滿足約束條件。例如，在付款問(wèn)題中，可行函數(shù)是每一步選擇的貨幣和已付出的貨幣相加不超過(guò)應(yīng)付款。 貪心法的一般過(guò)程Greedy(C) /C是問(wèn)題的輸入集合即候選集合 S= ; /初始解集合為空集 while (not solution(S) /集合S沒(méi)有構(gòu)成問(wèn)題的一個(gè)解 x=select(C); /在候選集合C中做貪心選擇 if feasible(S, x) /判斷集合S中加入x后的解是否可行 S=S+x; C=C-x; return S;例1、 活動(dòng)安排問(wèn)題 活動(dòng)安排問(wèn)題就是要在所給的活動(dòng)集合中選出最

7、大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。該問(wèn)題要求高效地安排一系列爭(zhēng)用某一公共資源的活動(dòng)。貪心算法提供了一個(gè)簡(jiǎn)單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。例1、活動(dòng)安排問(wèn)題 設(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í)間fi,且si fi 。如果選擇了活動(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相容。例1

8、、 活動(dòng)安排問(wèn)題在下面所給出的解活動(dòng)安排問(wèn)題的貪心算法greedySelector :int greedySelector(int s, int f, bool a) int n=strlen(s)-1; a1=true; int j=1; int count=1; for (int i=2;i=fj) ai=true; j=i; count+; else ai=false; return count; 各活動(dòng)的起始時(shí)間和結(jié)各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組束時(shí)間存儲(chǔ)于數(shù)組s s和和f f中且按結(jié)束時(shí)間的非減中且按結(jié)束時(shí)間的非減序排列序排列 例1、 活動(dòng)安排問(wèn)題 由于輸入的活動(dòng)以其完成時(shí)間的

9、非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說(shuō)，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。 算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。 例1、活動(dòng)安排問(wèn)題 例：設(shè)待安排的11個(gè)活動(dòng)的開(kāi)始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i12345678910 11Si

10、130535688212fi4567891011121314例1、 活動(dòng)安排問(wèn)題 算法greedySelector 的計(jì)算過(guò)程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。例1、 活動(dòng)安排問(wèn)題 若被檢查的活動(dòng)i的開(kāi)始時(shí)間Si小于最近選擇的活動(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é)歸納法證明。3、貪心算法的基本要

11、素 對(duì)于一個(gè)具體的問(wèn)題，怎么知道是否可用貪心算法解此問(wèn)題，以及能否得到問(wèn)題的最優(yōu)解呢?這個(gè)問(wèn)題很難給予肯定的回答。 但是，從許多可以用貪心算法求解的問(wèn)題中看到這類問(wèn)題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。 3 貪心算法的基本要素1.1.貪心選擇性質(zhì)貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是指所求問(wèn)題的所謂貪心選擇性質(zhì)是指所求問(wèn)題的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的整體最優(yōu)解可以通過(guò)一系列局部最優(yōu)的選擇，即貪心選擇來(lái)達(dá)到。這是貪心算選擇，即貪心選擇來(lái)達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。

12、動(dòng)態(tài)規(guī)劃算法通常以自底向上的方動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問(wèn)題，而貪心算法則通常以自式解各子問(wèn)題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 對(duì)于一個(gè)具體問(wèn)題，要確定它是否對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。解。3 貪心算法的基本要素2.2.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 當(dāng)

13、一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)的最優(yōu)解時(shí)，稱此問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題性質(zhì)。問(wèn)題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。鍵特征。 貪心與動(dòng)態(tài)規(guī)劃 【例】在一個(gè)NM的方格陣中，每一格子賦予一個(gè)數(shù)即為權(quán)）。規(guī)定每次移動(dòng)時(shí)只能向上或向右。現(xiàn)試找出一條路徑，使其從左下角至右上角所經(jīng)過(guò)的權(quán)之和最大。 貪婪：1 3 4 6 動(dòng)規(guī)：1 2 10 6 局部最優(yōu)解VS全局最優(yōu)解3461210例例2、 背包問(wèn)題背包問(wèn)題 給定給定n種物品和一個(gè)容量為種物品和一個(gè)容量為

14、C的背包，物的背包，物品品i的重量是的重量是wi，其價(jià)值為，其價(jià)值為vi，背包問(wèn)題是如，背包問(wèn)題是如何選擇裝入背包的物品，使得裝入背包中物品何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大的總價(jià)值最大? 0-10-1背包問(wèn)題：背包問(wèn)題： 給定給定n n種物品和一個(gè)背包。物品種物品和一個(gè)背包。物品i i的重量是的重量是WiWi，其價(jià)值為，其價(jià)值為ViVi，背包的容量，背包的容量為為C C。應(yīng)如何選擇裝入背包的物品，使得。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大裝入背包中物品的總價(jià)值最大? ? 在選擇裝入背包的物品時(shí)，對(duì)每種物品在選擇裝入背包的物品時(shí)，對(duì)每種物品i i只有只有2

15、 2種種選擇，即裝入背包或不裝入背包。不能將物品選擇，即裝入背包或不裝入背包。不能將物品i i裝入裝入背包多次，也不能只裝入部分的物品背包多次，也不能只裝入部分的物品i i。 背包問(wèn)題：背包問(wèn)題： 與與0-1背包問(wèn)題類似，所不同的背包問(wèn)題類似，所不同的是在選擇物品是在選擇物品i裝入背包時(shí)，可以選擇物裝入背包時(shí)，可以選擇物品品i的一部分，而不一定要全部裝入背包，的一部分，而不一定要全部裝入背包，1in。 這2類問(wèn)題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而0-1背包問(wèn)題卻不能用貪心算法求解。 于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件式于是，背包問(wèn)題歸結(jié)為尋找一個(gè)滿足約束條件

16、式7.1，并使目標(biāo)函數(shù)式并使目標(biāo)函數(shù)式7.2達(dá)到最大的解向量達(dá)到最大的解向量X=(x1, x2, , xn)。設(shè)設(shè)xi表示物品表示物品i裝入背包的情況，根據(jù)問(wèn)題的要求，裝入背包的情況，根據(jù)問(wèn)題的要求，有如下約束條件和目標(biāo)函數(shù)：有如下約束條件和目標(biāo)函數(shù)： )1 (101nixCxwiniii（式（式7.1）niiixv1max（式（式7.2）至少有三種看似合理的貪心策略：至少有三種看似合理的貪心策略： （1選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快選擇價(jià)值最大的物品，因?yàn)檫@可以盡可能快地增加背包的總價(jià)值。但是，雖然每一步選擇獲得地增加背包的總價(jià)值。但是，雖然每一步選擇獲得了背包價(jià)值的極大增長(zhǎng)，但背包

17、容量卻可能消耗得了背包價(jià)值的極大增長(zhǎng)，但背包容量卻可能消耗得太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保太快，使得裝入背包的物品個(gè)數(shù)減少，從而不能保證目標(biāo)函數(shù)達(dá)到最大。證目標(biāo)函數(shù)達(dá)到最大。 （2選擇重量最輕的物品，因?yàn)檫@可以裝入盡可選擇重量最輕的物品，因?yàn)檫@可以裝入盡可能多的物品，從而增加背包的總價(jià)值。但是，雖然能多的物品，從而增加背包的總價(jià)值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價(jià)每一步選擇使背包的容量消耗得慢了，但背包的價(jià)值卻沒(méi)能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)值卻沒(méi)能保證迅速增長(zhǎng)，從而不能保證目標(biāo)函數(shù)達(dá)到最大。到最大。 （3選擇單位重量?jī)r(jià)值最大的物品，在背包價(jià)值選擇單

18、位重量?jī)r(jià)值最大的物品，在背包價(jià)值增長(zhǎng)和背包容量消耗兩者之間尋找平衡。增長(zhǎng)和背包容量消耗兩者之間尋找平衡。 應(yīng)用第三種貪心策略，每次從物品集合中選擇單位重量?jī)r(jià)值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個(gè)最優(yōu)子問(wèn)題它同樣是背包問(wèn)題，只不過(guò)背包容量減少了，物品集合減少了。因此背包問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 120 50 背包 180 190 200(a) 三個(gè)物品及背包 (b) 貪心策略1 (c) 貪心策略2 (d) 貪心策略3 50 30 10 20 20 3020/30 20 1010/20 30 10例如，有例如，有3個(gè)物品，其重量分別

19、是個(gè)物品，其重量分別是20, 30, 10，價(jià)值分，價(jià)值分別為別為60, 120, 50，背包的容量為，背包的容量為50，應(yīng)用三種貪心策，應(yīng)用三種貪心策略裝入背包的物品和獲得的價(jià)值如圖所示。略裝入背包的物品和獲得的價(jià)值如圖所示。 設(shè)背包容量為C，共有n個(gè)物品，物品重量存放在數(shù)組wn中，價(jià)值存放在數(shù)組vn中，問(wèn)題的解存放在數(shù)組xn中。 1改變數(shù)組改變數(shù)組w和和v的排列順序，使其按單位重量?jī)r(jià)值的排列順序，使其按單位重量?jī)r(jià)值vi/wi降序排列；降序排列；2將數(shù)組將數(shù)組xn初始化為初始化為0； /初始化解向量初始化解向量3i=1; 循環(huán)直到循環(huán)直到(wiC) 1 xi=1; /將第將第i個(gè)物品放入背包

20、個(gè)物品放入背包 2 C=C-wi; 3 i+;5. xi=C/wi;算法的時(shí)間主要消耗在將各種物品依其單位重量的價(jià)值從算法的時(shí)間主要消耗在將各種物品依其單位重量的價(jià)值從大到小排序。因而，其時(shí)間復(fù)雜性為大到小排序。因而，其時(shí)間復(fù)雜性為O(nlog2n)。#include #include #include #include #include #include #include #include #include #include using namespace std;using namespace std;struct thingstruct thing double wi,vi,vwi; d

21、ouble wi,vi,vwi;an10000;an10000;int cmp(thing i,thing j)int cmp(thing i,thing j) return i.vwi j.vwi; return i.vwi j.vwi; int main()int main() int n,c; int n,c; while(cinnc)while(cinnc) for(int i=0;in;i+) for(int i=0;iani.wiani.vi; cinani.wiani.vi; ani.vwi=ani.vi/ani.wi; ani.vwi=ani.vi/ani.wi; sort(a

22、n,an+n,cmp); sort(an,an+n,cmp); int step=0; int step=0; double cost=0; double cost=0; for(int i=0;in;i+) for(int i=0;i=c) if(step=c) break; break; if(c-step)=ani.wi) if(c-step)=ani.wi) step += ani.wi; step += ani.wi; cost += ani.vi; cost += ani.vi; else else cost += ani.vwi cost += ani.vwi* *(c-(c-s

23、tep);step); step=c; step=c; coutcostendl; coutcostendl; return 0; return 0; 對(duì)于0-1背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。 #include #include #include #in

24、clude #include #include #include #include #include #include using namespace std;using namespace std;struct thingstruct thing int wi,vi; int wi,vi;an10000;an10000; int dp10000;int dp10000;int main()int main() int n,c; int n,c; while(cinnc) while(cinnc) for(int i=0;in;i+) for(int i=0;iani.wiani.vi; ci

25、nani.wiani.vi; memset(dp,0,sizeof(dp); memset(dp,0,sizeof(dp); for(int i=0;in;i+) for(int i=0;i=ani.wi;j-) for(int j=c;j=ani.wi;j-) dpj=max(dpj,dpj-ani.wi+ani.vi); dpj=max(dpj,dpj-ani.wi+ani.vi); coutdpcendl; coutdpcendl; return 0; return 0; 例3 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問(wèn)題要求確定在裝載體積不受

26、限制的情況下，將盡可能多的集裝箱裝上輪船。1.算法描述最優(yōu)裝載問(wèn)題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解。具體算法描述如下頁(yè)。 最優(yōu)裝載2.2.貪心選擇性質(zhì)貪心選擇性質(zhì) 可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。可以證明最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。 3.3.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。最優(yōu)裝載問(wèn)題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子由最優(yōu)裝載問(wèn)題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法結(jié)構(gòu)性質(zhì)，容易證明算法loadingloading的正確性。的正確性。算法算法loadingloading的主要計(jì)算量

27、在于將集裝箱依的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間其重量從小到大排序，故算法所需的計(jì)算時(shí)間為為 O(nlogn) O(nlogn)。 例4、 單源最短路徑給定帶權(quán)有向圖G =(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源。現(xiàn)在要計(jì)算從源到所有其他各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問(wèn)題通常稱為單源最短路徑問(wèn)題。1.算法基本思想(迪科斯徹算法)Dijkstra算法是解單源最短路徑問(wèn)題的貪心算法。 例4、 單源最短路徑其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來(lái)擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短

28、路徑長(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)度。 例4、 單源最短路徑例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其他頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。 例4、 單源最短路徑迭代迭代S Su udist2dist2 dist3dist3 dist4dist4

29、 dist5dist5初始初始1-10maxint301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代過(guò)程： 4 單源最短路徑2.2.算法的正確性和計(jì)算復(fù)雜性算法的正確性和計(jì)算復(fù)雜性(1)(1)貪心選擇性質(zhì)貪心選擇性質(zhì)(2)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)(3)計(jì)算復(fù)雜性計(jì)算復(fù)雜性對(duì)于具有對(duì)于具有n n個(gè)頂點(diǎn)和個(gè)頂點(diǎn)和e e條邊的帶權(quán)有向圖，條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么DijkstraDijkstra

30、算法的主循環(huán)體需要算法的主循環(huán)體需要 時(shí)間。這個(gè)時(shí)間。這個(gè)循環(huán)需要執(zhí)行循環(huán)需要執(zhí)行n-1n-1次，所以完成循環(huán)需要次，所以完成循環(huán)需要 時(shí)間。算法的其余部分所需要時(shí)間不超時(shí)間。算法的其余部分所需要時(shí)間不超過(guò)過(guò) 。)(nO)(2nO)(2nO 5 最小生成樹(shù) 設(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ù)。網(wǎng)絡(luò)的最小生成樹(shù)在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)cv

31、w表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹(shù)就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。 6 最小生成樹(shù)1.1.最小生成樹(shù)性質(zhì)最小生成樹(shù)性質(zhì)用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成生成樹(shù)的有效算法。本節(jié)介紹的構(gòu)造最小生成樹(shù)的樹(shù)的PrimPrim算法和算法和KruskalKruskal算法都可以看作是應(yīng)算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這用貪心算法設(shè)計(jì)策略的例子。盡管這2 2個(gè)算法個(gè)算法做貪心選擇的方式不同，它們都利用了下面的做貪心選擇的方式不同，它們都利用了下面的最小生成樹(shù)性質(zhì)：最小生成樹(shù)性質(zhì)：設(shè)設(shè)

32、G=(V,E)G=(V,E)是連通帶權(quán)圖，是連通帶權(quán)圖，U U是是V V的真子集。的真子集。假如假如(u,v)(u,v)E E，且，且u uU U，v vV-UV-U，且在所有這，且在所有這樣的邊中，樣的邊中，(u,v)(u,v)的權(quán)的權(quán)cuvcuv最小，那么一定最小，那么一定存在存在G G的一棵最小生成樹(shù)，它以的一棵最小生成樹(shù)，它以(u,v)(u,v)為其中一為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為條邊。這個(gè)性質(zhì)有時(shí)也稱為MSTMST性質(zhì)。性質(zhì)。 5 最小生成樹(shù)2.Prim2.Prim算法算法 設(shè)設(shè)G=(V,E)G=(V,E)是連通帶權(quán)圖，是連通帶權(quán)圖，V=1,2,nV=1,2,n。構(gòu)造構(gòu)造G G的

33、最小生成樹(shù)的的最小生成樹(shù)的PrimPrim算法的基本思算法的基本思想是：首先置想是：首先置S=1S=1，然后，只要，然后，只要S S是是V V的真子的真子集，就作如下的貪心選擇：選取滿足條件集，就作如下的貪心選擇：選取滿足條件i iS S，j jV-SV-S，且，且cijcij最小的邊，將頂點(diǎn)最小的邊，將頂點(diǎn)j j添加到添加到S S中。這個(gè)過(guò)程一直進(jìn)行到中。這個(gè)過(guò)程一直進(jìn)行到S=VS=V時(shí)為止。時(shí)為止。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G G的一棵最小生成樹(shù)。的一棵最小生成樹(shù)。 5 最小生成樹(shù)利用最小生成樹(shù)性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含

34、G的某棵最小生成樹(shù)中的邊。因而，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹(shù)。 例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下頁(yè)圖所示。 5 最小生成樹(shù) 5 最小生成樹(shù)在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)cij最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。在Prim算法執(zhí)行過(guò)程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closestj)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為 )

35、(2nO 5 最小生成樹(shù)3.Kruskal3.Kruskal算法算法KruskalKruskal算法構(gòu)造算法構(gòu)造G G的最小生成樹(shù)的基的最小生成樹(shù)的基本思想是，首先將本思想是，首先將G G的的n n個(gè)頂點(diǎn)看成個(gè)頂點(diǎn)看成n n個(gè)孤個(gè)孤立的連通分支。將所有的邊按權(quán)從小到立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開(kāi)始，依邊權(quán)大排序。然后從第一條邊開(kāi)始，依邊權(quán)遞增的順序查看每一條邊，并按下述方遞增的順序查看每一條邊，并按下述方法連接法連接2 2個(gè)不同的連通分支：當(dāng)查看到第個(gè)不同的連通分支：當(dāng)查看到第k k條邊條邊(v,w)(v,w)時(shí)，如果端點(diǎn)時(shí)，如果端點(diǎn)v v和和w w分別是當(dāng)分別是當(dāng)

36、前前2 2個(gè)不同的連通分支個(gè)不同的連通分支T1T1和和T2T2中的頂點(diǎn)時(shí)，中的頂點(diǎn)時(shí)，就用邊就用邊(v,w)(v,w)將將T1T1和和T2T2連接成一個(gè)連通分連接成一個(gè)連通分支，然后繼續(xù)查看第支，然后繼續(xù)查看第k+1k+1條邊；如果端點(diǎn)條邊；如果端點(diǎn)v v和和w w在當(dāng)前的同一個(gè)連通分支中，就直在當(dāng)前的同一個(gè)連通分支中，就直接再查看第接再查看第k+1k+1條邊。這個(gè)過(guò)程一直進(jìn)行條邊。這個(gè)過(guò)程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。到只剩下一個(gè)連通分支時(shí)為止。 5 最小生成樹(shù)例如，對(duì)前面的連通帶權(quán)圖，按例如，對(duì)前面的連通帶權(quán)圖，按KruskalKruskal算法順序得到的算法順序得到的最小生成樹(shù)上的

37、邊如下圖所示。最小生成樹(shù)上的邊如下圖所示。 5 最小生成樹(shù)關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。 按權(quán)的遞增順序查看等價(jià)于對(duì)優(yōu)先隊(duì)列執(zhí)行removeMin運(yùn)算。可以用堆實(shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。 對(duì)一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運(yùn)算。當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是 。當(dāng) 時(shí)，Kruskal算法比Prim算法差，但當(dāng) 時(shí)，Kruskal算法卻比Prim算法好得多。)log(eeO)(2ne)(2noe 鍵盤輸入一個(gè)高精度的正整數(shù)鍵盤輸入一個(gè)高精度的正整數(shù)N，去掉其中任意，去掉其中任意S個(gè)數(shù)字后個(gè)數(shù)字后剩下

38、的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給剩下的數(shù)字按原左右次序?qū)⒔M成一個(gè)新的正整數(shù)。編程對(duì)給定的定的N和和S，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。，尋找一種方案使得剩下的數(shù)字組成的新數(shù)最小。 輸入數(shù)據(jù)均不需判錯(cuò)。輸出應(yīng)包括所去掉的數(shù)字的位置和輸入數(shù)據(jù)均不需判錯(cuò)。輸出應(yīng)包括所去掉的數(shù)字的位置和組成的新的正整數(shù)組成的新的正整數(shù) 例6、刪數(shù)游戲 問(wèn)題分析問(wèn)題分析 在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)在位數(shù)固定的前提下，讓高位的數(shù)字盡量小其值就較小，依據(jù)此貪婪策略就可以解決這個(gè)問(wèn)題。此貪婪策略就可以解決這個(gè)問(wèn)題。 怎么樣根據(jù)貪婪策略刪除數(shù)字呢？總目標(biāo)是刪除高位較大的數(shù)怎么樣根據(jù)貪婪策略刪除數(shù)字呢？總目標(biāo)是刪除高位較大的數(shù)字，具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過(guò)字，具體地相鄰兩位比較若高位比低位大則刪除高位。我們通過(guò)“枚舉歸納設(shè)計(jì)算法的細(xì)節(jié)，看一個(gè)實(shí)例枚舉歸納設(shè)計(jì)算法的細(xì)節(jié)，看一個(gè)實(shí)例s=3） ： n1=“