數(shù)據(jù)結(jié)構(gòu)與算法實(shí)踐指導(dǎo) 課件 9-貪心算法

第9章

貪心算法9.1知識簡介

可以用貪心策略解決的問題一般具有兩個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。9.1.1貪心算法的基本要素

（1）貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。貪心算法通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題。對于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。

（2）最優(yōu)子結(jié)構(gòu)性質(zhì)是指一個(gè)問題的最優(yōu)解包含子問題的最優(yōu)解。這個(gè)性質(zhì)是判斷問題能用貪心算法或動態(tài)規(guī)劃算法求解的關(guān)鍵特征。9.1知識簡介貪心算法的一般步驟為：①

觀察問題特征，構(gòu)造貪心選擇；②

證明策略正確性。算法正確性一般用歸納法證明，歸納證明步驟為：

①

敘述一個(gè)有關(guān)自然數(shù)n的命題，該命題斷定該貪心策略的執(zhí)行最終將導(dǎo)致最優(yōu)解。其中自然數(shù)n可以代表算法步數(shù)或者問題規(guī)模。

②

證明命題對所有的自然數(shù)為真。

貪心算法適用于組合優(yōu)化問題，用貪心算法解決問題時(shí)算法簡單，時(shí)間和空間復(fù)雜度低。9.1.2貪心算法的步驟9.2實(shí)驗(yàn)?zāi)康?/p>

通過解決活動選擇問題、最優(yōu)裝載問題、最小延時(shí)調(diào)度問題等經(jīng)典貪心問題，加深對貪心算法的理解和應(yīng)用能力。通過編程實(shí)現(xiàn)貪心算法，培養(yǎng)算法設(shè)計(jì)和調(diào)試技能，積累解決實(shí)際問題的經(jīng)驗(yàn)。通過實(shí)踐操作使學(xué)生深入掌握貪心策略及其在解決實(shí)際問題中的應(yīng)用，培養(yǎng)嚴(yán)謹(jǐn)?shù)倪壿嬎季S能力和高效的問題解決技巧。9.3實(shí)驗(yàn)范例

9.3.1活動選擇問題1、問題描述9.3實(shí)驗(yàn)范例

9.3.1活動選擇問題i12345678910si1325456883fi45589911111213該案例的最優(yōu)解A={1，4，8}。1、問題描述9.3實(shí)驗(yàn)范例

該問題的形式化描述如下：9.3.1活動選擇問題

1、問題描述9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇

采用貪心算法的計(jì)算過程是多步的判斷過程，每一步判斷依據(jù)某種“短視”的策略（只看眼前）進(jìn)行活動選擇，選擇時(shí)注意滿足相容性條件。此問題可能的貪心選擇有開始時(shí)間早的活動優(yōu)先選擇、占用時(shí)間少的活動優(yōu)先選擇、結(jié)束時(shí)間早的活動優(yōu)先選擇。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略1：開始時(shí)間早的活動優(yōu)先i123si028fi20515

排序使得s1≤s2≤?≤sn，從前向后挑選。這種策略并不能得到最優(yōu)解，舉反例來證明，例如有3個(gè)活動，各活動的開始時(shí)間和結(jié)束時(shí)間如下表所示。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略1：開始時(shí)間早的活動優(yōu)先

用圖表示如下，如果按照此策略，先應(yīng)該選擇活動1，選擇活動1后，活動2、活動3都與活動1不相容，所以得到的結(jié)果是A={1}。從圖上看出此結(jié)果不是最優(yōu)的，最優(yōu)的結(jié)果應(yīng)該是A={2，3}。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略2：占用時(shí)間少的活動優(yōu)先

i123si078fi89159.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略2：占用時(shí)間少的活動優(yōu)先

用圖表示如下，如果按照活動時(shí)間最短優(yōu)先選擇，則先選擇活動2，活動1、活動3都與活動2不相容，所以得到的結(jié)果是A={2}。從圖可以看出此結(jié)果不是最優(yōu)的，最優(yōu)的結(jié)果應(yīng)該是A={1，3}。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略3：結(jié)束時(shí)間早的優(yōu)先

9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略3：結(jié)束時(shí)間早的優(yōu)先i12345678910si1325456883fi45589911111213

如上表所示10個(gè)活動的開始時(shí)間和結(jié)束時(shí)間。該問題中最先結(jié)束的活動是活動1，選擇活動1，由于活動2、活動3、活動10都與活動1不相容，排除這些活動。接著剩下的活動中選擇最先結(jié)束的活動，即活動4，由于活動5、活動6、活動7與活動4不相同，排除這些活動。接著剩下的活動中選擇最先結(jié)束的活動，即活動8，由于活動9與活動8不相同，活動9排除。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略3：結(jié)束時(shí)間早的優(yōu)先如下圖所示：

得到的結(jié)果A={活動1，活動4，活動8}，選擇的活動數(shù)為3，該解是該問題的一個(gè)最優(yōu)解。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題2、構(gòu)造貪心選擇策略3：結(jié)束時(shí)間早的優(yōu)先

9.3實(shí)驗(yàn)范例9.3.1活動選擇問題3、證明問題貪心策略的正確性

用歸納法來證明活動選擇問題中選擇活動最早時(shí)間策略的正確性。1)活動選擇算法的命題

假設(shè)算法選擇執(zhí)行到第k步，選擇了k項(xiàng)活動i1=1，i2，…，ik，則存在最優(yōu)解A包含活動i1=1，i2，…，ik，k最多到n。

對于任何k，算法前k步的選擇都將導(dǎo)致最優(yōu)解，至多到第n步將得到問題的最優(yōu)解。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題3、證明問題貪心策略的正確性

2)歸納證明

9.3實(shí)驗(yàn)范例9.3.1活動選擇問題3、證明問題貪心策略的正確性

2)歸納證明

歸納步驟：假設(shè)命題對k為真，證明對k+1也為真。

9.3實(shí)驗(yàn)范例9.3.1活動選擇問題3、證明問題貪心策略的正確性

2)歸納證明

歸納步驟：假設(shè)命題對k為真，證明對k+1也為真。

從而證明了該問題中選擇活動最早時(shí)間策略的正確性。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題4、算法描述voidActivitySelection(intn,TimeTypes[],TimeTypef[],boolA[]){

A[0]=true;//選擇第1個(gè)活動

intj=0;//記錄最后選擇的活動

for(inti=1;i<n;i++){//從第2個(gè)活動開始

if(s[i]>=f[j]){//如果第i個(gè)活動與之前選擇的活動相容

A[i]=true;//選擇該活動

j=i;

}else//不相容

A[i]=false;//不選擇該活動 }}n個(gè)活動，每個(gè)活動的開始時(shí)間s[n]，每個(gè)活動的結(jié)束時(shí)間f[n]，A[n]表示選擇了哪些活動?；顒右寻凑战Y(jié)束時(shí)間從小到大排好。9.3實(shí)驗(yàn)范例9.3.1活動選擇問題5、算法分析

算法的時(shí)間復(fù)雜度包括兩個(gè)部分，一部分是對n個(gè)活動按結(jié)束時(shí)間從小到大排序，排序的時(shí)間復(fù)雜度為O(nlogn)，另一部分是對n個(gè)活動進(jìn)行逐個(gè)判斷選擇，時(shí)間復(fù)雜度為O(n)。所以算法的時(shí)間復(fù)雜度為O(nlogn)+O(n)，即O(nlogn)。9.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)1：用貪心策略求解最優(yōu)裝載問題。

其中，xi=0表示不裝入集裝箱i，xi=1表示裝入集裝箱i。9.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)2：用貪心策略解決最小延遲調(diào)度問題。

給定等待服務(wù)的客戶集合A={1,2,…,n}，各客戶的服務(wù)時(shí)間T=(t1,t2,…,tn)，其中客戶i的服務(wù)時(shí)間為ti（ti>0），各客戶的期望完成時(shí)刻D=(d1,d2,…,dn)，其中客戶i期望的服務(wù)完成時(shí)刻為di（di>0）。一個(gè)調(diào)度f：A->N，f(i)為客戶i的開始時(shí)刻。如果對客戶i的服務(wù)在di之前結(jié)束，那么客戶i的服務(wù)沒有延遲，如果在di之后結(jié)束，那么這個(gè)服務(wù)就被延遲了，延遲的時(shí)間等于該服務(wù)的實(shí)際完成時(shí)刻f(i)+ti減去預(yù)期結(jié)束時(shí)刻di。一個(gè)調(diào)度f的最大延遲是所有客戶延遲時(shí)長的最大值max{f(i)+ti-di}。要求找出一個(gè)調(diào)度使得最大延遲達(dá)到最小。9.4實(shí)驗(yàn)任務(wù)完成下列任務(wù)，并分析各算法的時(shí)間復(fù)雜度。任務(wù)2：用貪心策略解決最小延遲調(diào)度問題。

如下圖所示，客戶i的開始時(shí)間為f(i)，結(jié)束時(shí)間為f(i)+ti，則該客戶的延遲時(shí)間為f(i)+ti-di。該問題的形式化描述為：給定有n個(gè)任務(wù)的任務(wù)集A，以及任務(wù)的服務(wù)時(shí)間{t1,t2,…,tn}和期望完成時(shí)刻{d1,d2,…,dn}，求最大延遲達(dá)到最小的調(diào)度，即求f使得9.5任務(wù)提示1、構(gòu)造貪心選擇任務(wù)1提示

此問題采用重量最小優(yōu)先裝載的貪心策略，先對集裝箱按照重量從小到大排序，然后從小的集裝箱開始逐個(gè)裝載到輪船，直到總裝載重量超過輪船裝載限制的前一個(gè)集裝箱為止。

例如：C=30，n=8，w[8]={4,10,7,11,3,5,14,2}。1）先對集裝箱按照重量從小到大排序，將w[8]從小到大排序，w[8]={2,3,4,5,7,10,11,14}。2）從小的集裝箱開始逐個(gè)裝載到輪船

先選擇第1個(gè)集裝箱，如果裝入輪船，則裝入重量tmp=2，tmp<C，沒有超重，選擇該集裝箱；9.5任務(wù)提示1、構(gòu)造貪心選擇任務(wù)1提示

接著選擇第2個(gè)集裝箱，如果裝入輪船，則裝入重量tmp=2+3=5，tmp<C，沒有超重，選擇該集裝箱；

接著選擇第3個(gè)集裝箱，如果裝入輪船，則裝入重量tmp=2+3+4=9，tmp<C，沒有超重，選擇該集裝箱；

接著選擇第4個(gè)集裝箱，如果裝入輪船，則裝入重量tmp=2+3+4+5=14，tmp<C，沒有超重，選擇該集裝箱；

接著選擇第5個(gè)集裝箱，如果裝入輪船，則裝入重量tmp=2+3+4+5+7=21，tmp<C，沒有超重，選擇該集裝箱；

接著選擇第6個(gè)集裝箱，如果裝入輪船，則裝入重量tmp=2+3+4+5+7+10=31，tmp>C，超重，第6個(gè)集裝箱不選，選擇結(jié)束。9.5任務(wù)提示1、構(gòu)造貪心選擇任務(wù)1提示

集裝箱最多選擇5個(gè)。

該問題是0-1背包問題的子問題，集裝箱相當(dāng)于物品，物品重量是wi，價(jià)值vi都為1，輪船載重限制C相當(dāng)于背包重量限制。9.5任務(wù)提示2、正確性證明任務(wù)1提示1）最優(yōu)裝載問題算法的命題

對裝載問題任何規(guī)模為n的輸入實(shí)例，算法能得到最優(yōu)解。設(shè)集裝箱重量按從小到大記為1、2、…、n。2）歸納證明

第一步：證明對于任何只含一個(gè)箱子的輸入實(shí)例，貪心法能得到最優(yōu)解，這個(gè)顯然是正確的。

第二步：假設(shè)對于n個(gè)集裝箱的輸入，貪心法都可以得到最優(yōu)解，那么對于n+1個(gè)集裝箱{1,2,…,n+1}，重量為{w1，w2，…，wn+1}（其中w1≤w2≤…≤wn+1），裝載量為C，通過貪心選擇也能得到最優(yōu)解。9.5任務(wù)提示2、正確性證明任務(wù)1提示1）最優(yōu)裝載問題算法的命題

對裝載問題任何規(guī)模為n的輸入實(shí)例，算法能得到最優(yōu)解。設(shè)集裝箱重量按從小到大記為1、2、…、n。2）歸納證明

由歸納假設(shè)，對于N′={2,3,…,n+1}，C′=C-w1，貪心法得到最優(yōu)解I′，令I(lǐng)=I′∪{1}。我們來證明I是N的最優(yōu)解。用反正法。

假設(shè)I不是N的最優(yōu)解，設(shè)存在包含1號集裝箱的關(guān)于N的最優(yōu)解I*(如果I*中沒有1，用1替換I*中的第一個(gè)元素得到的也是最優(yōu)解)，且|I*|>|I|，那么I*-{1}是N′和C′的解且|I*-{1}|>|I-{1}|=|I′|。這與I′是關(guān)于N′和C′的最優(yōu)解矛盾。即I就是關(guān)于N和C的最優(yōu)解。9.5任務(wù)提示任務(wù)1提示3、算法描述

n個(gè)集裝箱，每個(gè)集裝箱重量w[n],輪船能裝的最大重量C，返回能裝入的集裝箱個(gè)數(shù)。intLoading(intn,WeightTypeC,WeightTypew[]){//先對集裝箱重量從小達(dá)到進(jìn)行排序Sort(n,w);WeightTypetmp=0;//已裝載到船上的集裝箱重量intcnt=0;//裝載到船上的集裝箱個(gè)數(shù)for(i=1;i<=n;i++){if(tmp+w[i]<=C){//裝入第i個(gè)集裝箱后的裝載重量小于Ctmp+=w[i];//選擇該集裝箱cnt++;//集裝箱個(gè)數(shù)加1

}else{break;//選擇結(jié)束}}returncnt;}9.5任務(wù)提示任務(wù)1提示4、算法分析

算法的時(shí)間復(fù)雜度包括兩個(gè)部分，一部分是對n個(gè)集裝箱的重量從小到大排序，排序的時(shí)間復(fù)雜度為O(nlogn)，另一部分是對n個(gè)集裝箱進(jìn)行逐個(gè)選擇，時(shí)間復(fù)雜度為O(n)。所以算法的時(shí)間復(fù)雜度為O(nlogn)+O(n)，即O(nlogn)。9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇

此問題可能的貪心選擇有：按照服務(wù)時(shí)間從小到大調(diào)度、按照客戶期望的開始時(shí)刻從小到大調(diào)度、按照客戶期望的完成時(shí)刻從小到大調(diào)度。9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇策略1：按照服務(wù)時(shí)間ti從小到大調(diào)度

按照服務(wù)的時(shí)間從小到大進(jìn)行調(diào)度，誰的服務(wù)時(shí)間少，誰先調(diào)度。此策略中需先根據(jù)每個(gè)客戶的服務(wù)時(shí)間從小到大進(jìn)行排序。此策略不是對所有實(shí)例都能得到最優(yōu)解。如果某個(gè)客戶服務(wù)時(shí)間ti很長，而且其還很著急想早些結(jié)束，即di很小；而其他客戶服務(wù)時(shí)間ti很短，但是不著急結(jié)束，即di很大。如果使用此策略，會使那些不著急的客戶先調(diào)度，而著急的客戶后調(diào)度，必然造成長延遲。9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇

如客戶集A={1,2}，T={1,10}，D={100,10}。第1個(gè)客戶的服務(wù)時(shí)間為1，其期望完成時(shí)間為100，而第2個(gè)客戶的服務(wù)時(shí)間為10，其期望完成時(shí)間為10。按此策略先為第1個(gè)客戶服務(wù)，第1個(gè)客戶的服務(wù)時(shí)間為1，第1個(gè)客戶實(shí)際結(jié)束時(shí)間為1。接著為第2個(gè)客戶服務(wù)，開始時(shí)間為2，實(shí)際結(jié)束時(shí)間為11。各客戶的延遲時(shí)間分別是0、1。這不是最優(yōu)解，如果先為第2個(gè)客戶服務(wù)，然后再為第1個(gè)客戶服務(wù)，各客戶的延遲時(shí)間都為0。比之前的調(diào)度順序更優(yōu)。

策略1：按照服務(wù)時(shí)間ti從小到大調(diào)度9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇策略2：按照客戶期望的開始時(shí)間從小到大調(diào)度

客戶期望的開始時(shí)間為客戶期望的完成時(shí)間減去客戶的服務(wù)時(shí)間，即di-ti。此策略需先根據(jù)客戶期望的開始時(shí)間從小到大進(jìn)行排序。此策略不是對所有實(shí)例都能得到最優(yōu)解。如果某個(gè)客戶不是很著急，即di很大，其服務(wù)的時(shí)間很長，即ti很大，但兩者相減很小，該客戶會先獲得服務(wù)，該客戶會占有大量的時(shí)間，其他的客戶得不到服務(wù)。9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇策略2：按照客戶期望的開始時(shí)間從小到大調(diào)度

如客戶集A={1,2}，T={1,10}，D={2,10}。客戶2服務(wù)時(shí)間為10，其期望完成時(shí)間為10。兩個(gè)客戶期望的開始時(shí)間為1和0，先為第2個(gè)客戶服務(wù)，第2個(gè)客戶的服務(wù)時(shí)間為10，第2個(gè)客戶實(shí)際結(jié)束時(shí)間為10。接著為第1個(gè)客戶服務(wù)，開始時(shí)間為11，實(shí)際結(jié)束時(shí)間為11。各客戶的延遲時(shí)間分別是0、9。這不是最優(yōu)解，如果先為第1個(gè)客戶服務(wù)，然后再為第2個(gè)客戶服務(wù)，各客戶的延遲時(shí)間分別為0、1，比此策略調(diào)度順序更優(yōu)。9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇策略3：按照客戶期望的完成時(shí)刻從小到大調(diào)度按照客戶期望的完成時(shí)刻從小到大進(jìn)行調(diào)度，這樣沒有空閑，可以得到最優(yōu)解。如有5個(gè)客戶集合A={1,2,3,4,5}，各客戶的服務(wù)時(shí)間T和各客戶期望的完成時(shí)刻D如下表所示。i12345T584103D1012151120i14235T510843D1011121520先按D從小到大進(jìn)行排序。9.5任務(wù)提示任務(wù)2提示1、構(gòu)造貪心選擇按照排好序的順序?yàn)榭蛻舴?wù)，服務(wù)順序?yàn)?、4、2、3、5，各客戶開始時(shí)刻和實(shí)際完成時(shí)刻如下表所示。策略3：按照客戶期望的完成時(shí)刻從小到大調(diào)度各任務(wù)延遲為：0，4，11，12，10，其最大延遲為12。如果按照前兩種策略，最大延遲時(shí)間分別是15和13，顯然策略3更優(yōu)。9.5任務(wù)提示任務(wù)2提示2、正確性證明

此算法的正確性證明用交換論證方法，該方法的證明思路：1）先分析一般最優(yōu)解與算法解的區(qū)別（成分不同或者排列順序不同，本問題是排列順序不同）；2）設(shè)計(jì)一種轉(zhuǎn)換操作（替換成分或交換次序，本問題是交換次序），可以在有限步將任意一個(gè)普通最優(yōu)解逐步轉(zhuǎn)換成算法的解。每步轉(zhuǎn)換都不降低解的最優(yōu)性質(zhì)。9.5任務(wù)提示任務(wù)2提示2、正確性證明

本問題的解具有沒有空閑時(shí)間，沒有逆序的性質(zhì)。

逆序(i,j)是指：f(i)<f(j)且di>dj。即第i個(gè)客戶安排的服務(wù)時(shí)間比第j個(gè)客戶安排的服務(wù)時(shí)間早，但是第i個(gè)客戶期望的截止時(shí)刻比第j個(gè)客戶期望的截止時(shí)刻大。

本問題交換論證的過程就是不斷的消除逆序，當(dāng)逆序消除完，則和算法的解等價(jià)。此算法的證明依據(jù)引理：所有沒有逆序、沒有空閑時(shí)間的調(diào)度具有相同的最大延遲。證明過程：從一個(gè)沒有空閑的最優(yōu)解出發(fā)，逐步轉(zhuǎn)變成沒有逆序的解，根據(jù)引理，這個(gè)解和算法解具有相同的最大延遲。

此算法的正確性證明用交換論證方法，該方法的證明思路：9.5任務(wù)提示任務(wù)2提示3、算法描述structCustom//客