算法設(shè)計與分析 課件 第五章 貪心法

計算機(jī)算法設(shè)計與分析第5章貪心法5.1.1部分背包問題給定編號1~n的n個物品，編號i的物品重量wi，價值vi，現(xiàn)用1個負(fù)重W的背包來裝這些物品，在不超過背包負(fù)重的前提下，使得背包裝入的總價值最大。與0-1背包問題的區(qū)別是這些物品可以分割后部分裝入背包，分割后的物品重量價值比不變。5.1.1部分背包問題一個背包負(fù)重W=150的7個物品的部分背包問題：物品編號1234567重量wi35306050401025價值vi10403050354030貪心策略1：價值最大策略選擇價值最大的物品，可以盡可能快地增加背包的總價值。但背包容量卻可能消耗得太快，使得裝入背包的物品個數(shù)減少，從而不能保證裝入背包的物品總價值達(dá)到最大。按照物品價值從大到小排序，價值相同的重量小的優(yōu)先，可選擇4號物品、6號物品，2號物品、5號物品、7號物品（部分裝入）。得到背包的總重量為50+10+30+40+20=150，總價值為50+40+40+35+20/25*30=189。物品編號1234567重量wi35306050401025價值vi10403050354030貪心策略2：重量最輕策略選擇重量最輕的物品，可以裝入盡可能多的物品，從而增加背包的總價值。但背包的價值卻不能保證迅速增長，也不一定能保證裝入背包的物品總價值達(dá)到最大。按照物品重量從小到大排序，可選擇6號物品、7號物品、2號物品、1號物品、5號物品和4號物品（部分裝入），得到背包的總重量為10+25+30+35+40+10=150，總價值為40+30+40+10+35+10/50*50=165。物品編號1234567重量wi35306050401025價值vi10403050354030貪心策略3：單位重量價值最大策略選擇單位重量價值最大的物品，在背包價值增長和背包容量消耗兩者之間尋找平衡。將物品按照單位重量價格從大到小排序，可選擇6號物品、2號物品、7號物品、4號物品和5號物品（部分裝入），得到背包總重量為10+30+25+50+35=150，總價值為40+40+30+50+35/40*35=190.625。物品編號1234567重量wi35306050401025價值vi10403050354030結(jié)論顯然，以上三種貪心策略中，每次選取單位重量價值最大策略使得裝入背包的物品總價值最大。背包問題數(shù)學(xué)模型設(shè)xi表示編號為i的物品裝入背包情況，0≤xi≤1。根據(jù)問題的要求，有如下目標(biāo)函數(shù)和約束條件：證明貪心策略3正確性首先按照每個物品的單位重量價值vi/wi給物品重新排序，排序后的物品也重新編號為1~n，即i<j時有

。貪心策略：從單位重量價值最大的物品開始選擇，若將這個物品全部裝入背包后，背包沒有超過其負(fù)重W，則繼續(xù)選擇下一個物品進(jìn)行裝入，當(dāng)選擇某物品裝入背包后超過背包負(fù)重，則該物品采用部分裝入方式將背包裝滿。證明貪心策略3正確性（1）存在包含單位價值最大物品的最優(yōu)解。使用反證法來證明第一步選擇，因為物品已經(jīng)按單位重量價值遞減排序且w1<W，則部分背包問題存在最優(yōu)解v1x1+v2x2+...+vnxn。若x1=1，顯然最優(yōu)解包含單位重量價值最大的物品的結(jié)論成立。若x1<1，則將背包中重量等于(1-x1)w1的部分物品與物品1交換，這樣背包的負(fù)重不變，但因，重樣重量的物品1具有更大的價值，即等量交換后背包的總價值增加了，這與假設(shè)是最優(yōu)解矛盾。如果w1≥W，則直接裝入W重的第1個物品部分即為最優(yōu)解，總價值為最優(yōu)解包含單位重量價值最大的物品的結(jié)論成立!也即，貪心選擇的第一步選擇總是會包含在某個最優(yōu)解中。（2）在完成第一步選擇之后，子問題P'()與原問題P()還是同一類問題，意味著我們的選擇沒有改變問題的結(jié)構(gòu)。令π'為子問題P'的最優(yōu)解，π為原問題P的最優(yōu)解，則π=π'+v1。證明貪心策略3正確性證明貪心策略3正確性還是使用反證法來證明這個結(jié)論，假設(shè)π不是原問題的最優(yōu)解，原問題P的最優(yōu)解為π*。根據(jù)第一步結(jié)論，我們知道最優(yōu)解π*中一定含有v1，那么π*-v1就應(yīng)該是子問題P'的解，π*-v1>π-v1=π'，這與π'為子問題P'的最優(yōu)解定義矛盾。所以π=π'+v1不可能不是最優(yōu)解，因此原問題的最優(yōu)解等于子問題最優(yōu)解加上第一個選擇的物品價值。證明貪心策略3正確性（3）由以上兩步證明知道，我們按照單位重量價值由大到小做出的每一步選擇，都將原問題簡化為一個與原問題相同形式的更小的子問題，使用數(shù)學(xué)歸納法可以證明這種貪心策略可以得到原問題的一個最優(yōu)解。計算機(jī)算法設(shè)計與分析第5章貪心法5.2.1活動安排問題學(xué)校有n個分工會需要進(jìn)行節(jié)目彩排活動安排，學(xué)校彩排舞臺只有一個。每個分工會都有自己的一個空閑時間段，即每個分工會都給出自己可以進(jìn)行彩排活動的一個起始時間和結(jié)束時間。而學(xué)校的舞臺同一時間只能安排一個分工會入場進(jìn)行活動。如何安排這次彩排活動，使得被安排的分工會盡可能多，沒有能安排的分工會只能放到下次安排?；顒影才艈栴}設(shè)學(xué)校分工會節(jié)目彩排活動編號的集合為E={1,2,...,n}，第i個分工會節(jié)目彩排活動的起始時間為si，結(jié)束時間為fi，且si<fi。如果安排了第i個分工會進(jìn)行彩排，則它在半開時間區(qū)間[si，fi)內(nèi)占用舞臺資源。當(dāng)兩個活動區(qū)間[si，fi)與[sj，fj)不相交，則稱活動i和活動j是相容的，即si≥fj或sj≥fi，i≠j，活動i和活動j相容?；顒影才艈栴}是求解兩兩相容的最大活動子集S?；顒影才艈栴}分工會i1234567891011起始時間si130535688212結(jié)束時間fi4567891011121314貪心策略1：更早的活動起始時間優(yōu)先策略，這樣可以增大舞臺資源利用率。按照活動的起始時間先后順序選擇活動。如表所示的11個活動，先安排活動3，則活動1、2、4、5、6、10與活動3均不相容；之后安排與活動3相容的具有更早起始時間的活動7，則活動8、9與活動7均不相容；之后安排與活動7相容的具有更早起始時間的活動11，安排結(jié)束。貪心策略1安排的相容活動集合S={3,7,11}。分工會i1234567891011起始時間si130535688212結(jié)束時間fi4567891011121314活動安排問題貪心策略2：更早的活動結(jié)束時間優(yōu)先策略，這樣可以下一個活動盡早得到安排。按照活動結(jié)束時間從小到大順序選擇活動，表中的活動已經(jīng)按活動結(jié)束時間順序從小到大排序。選擇活動1，之后選擇與活動1相容活動4，之后選擇與活動4相容的活動8，最后選擇與活動8相容的活動11，安排結(jié)束。貪心策略2安排的相容活動集合S={1,4,8,11}。分工會i1234567891011起始時間si130535688212結(jié)束時間fi4567891011121314活動安排問題活動安排問題貪心策略2的正確性證明：將n個活動按照其結(jié)束時間fi從小到大排序，排序后的活動序列還是按E={1,2,...,n}編號。第一次先選1號活動，然后接下來的每一步，從E中按順序選出下一個相容的活動，直到E中所有活動都被檢查過一遍。證明貪心策略2能得到活動安排問題的最優(yōu)解，即考察如下問題：該算法執(zhí)行到第k步時，選擇了k個活動：i1,i2,...,ik，則存在最優(yōu)解S包含這k個活動，即該算法執(zhí)行的每一步的結(jié)果都是最優(yōu)解的一部分?；顒影才艈栴}（1）設(shè)S是E的一個最優(yōu)解且S={i1,...,im}。若最優(yōu)解S的第一個活動i1≠1，由于活動1的結(jié)束時間是活動集合E中最前面的，因此

。這樣，就將S中的i1換成1，得到S'：

由于

，因此S'中的活動也是相容的，而且活動數(shù)量與S中一致，故S'也是一個最優(yōu)解。也即E中的第1步選擇活動1肯定可以在一個最優(yōu)解中。活動安排問題（2）采用數(shù)學(xué)歸納法證明，若第k步選擇的活動ik在最優(yōu)解中，則第k+1步選擇的活動ik+1也在最優(yōu)解中。歸納假設(shè)第

k步選擇的活動ik在最優(yōu)解中，可以表述為：前

k

步已經(jīng)選擇的活為i1,i2,...,ik，存在一個最優(yōu)解S：第k+1步時，選擇只能在待選活動集合E'中選取，所謂待選活動集合，即原集合E中去除已判為沖突的活動和已選擇的活動后剩下的集合?；顒影才艈栴}①那么，B是E'（子問題）的一個最優(yōu)解。若不是，假設(shè)E'的有解是B*，且B*>B，那么用B*替換B以后得到

，則S'>S，與S是最優(yōu)解矛盾。故

②根據(jù)（1）的證明，貪心策略2的第一步選擇結(jié)束時間最早的活動總是導(dǎo)致問題的一個最優(yōu)解，故對于子問題E'存在一個最優(yōu)解B'，包含子問題E'的第一個活動ik+1。因B'和B都是E'的最優(yōu)解,B'=B，所以：S'和S是包含的活動數(shù)量一樣的原問題的最優(yōu)解，因此得證第k+1步選擇的活動ik+1在最優(yōu)解中。即按貪心策略2進(jìn)行選擇的活動必將導(dǎo)致問題的一個最優(yōu)解是成立的?；顒影才艈栴}效率分析:問題的輸入規(guī)模為n，按活動結(jié)束時間從小到大高效排序的時間復(fù)雜度為O(nlogn)，貪心算法選擇活動n步即可完成，故T(n)=O(nlogn)。活動安排問題計算機(jī)算法設(shè)計與分析第5章貪心法5.2.2村村通最小成本問題村村通工程（通電、通水、通氣、通網(wǎng)、通路等）是中國政府推行的一個旨在改善農(nóng)村地區(qū)基礎(chǔ)設(shè)施和信息化水平的工程項目?，F(xiàn)某鄉(xiāng)鎮(zhèn)政府決定實現(xiàn)村村通公路，通過勘察已將各個村落之間的可修建道路成本數(shù)據(jù)統(tǒng)計在下表中，根據(jù)表中給出的數(shù)據(jù)，求使得每個村都有公路連通所需要的最低成本和具體修建線路。村落1111122345村落2345636456成本29845694635.2.2村村通最小成本問題用無向連通帶權(quán)圖G=（V，E）表示村落之間的道路數(shù)據(jù)及其公路修建成本，如圖所示，各個村落為圖G的頂點(diǎn)，村落之間有路連通用無向邊相連，邊的權(quán)值為修建村落公路的成本。村村通公路最小成本問題轉(zhuǎn)化為求圖G的最小生成樹問題。5.2.2村村通最小成本問題對一個無向連通帶權(quán)圖G，如果G的子圖G'是一棵包含G的所有頂點(diǎn)的樹，則稱G'為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。貪心策略1，Prim算法設(shè)圖G=（V,E）是無向連通帶權(quán)圖，V={1,2,...,n}，E為邊集，cost[i][j]記錄頂點(diǎn)i到頂點(diǎn)j這條邊的權(quán)值。Prim算法構(gòu)造最小生成樹的基本步驟如下：（1）置頂點(diǎn)集合S={1}；（2）只要S中頂點(diǎn)數(shù)目小于n，就作如下的貪心選擇：選取滿足條件i∈S，j∈V-S，且（i,j）邊權(quán)值cost[i][j]最小，將頂點(diǎn)j添加到S中。這個過程一直進(jìn)行到|S|=|V|時為止，選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。貪心策略1，Prim算法1SSSSSSPrim算法正確性證明對于k<n，存在一棵最小生成樹包含Prim算法前k步選擇的邊。（1）首先證明k=1，存在一棵最小生成樹T包含邊e=（1，i），其中cost[1][i]是所有關(guān)聯(lián)頂點(diǎn)1的邊中權(quán)值最小的。Prim算法正確性證明設(shè)T是一棵最小生成樹，且T不包含邊（1，i），則T+（1，i）含有一條回路，刪除回路中關(guān)聯(lián)頂點(diǎn)1的另一條邊（1，j）得到一棵生成樹T'，如圖所示。因cost[1][i]≤cost[1][j]，所以生成樹T'的權(quán)值≤最小生成樹T的權(quán)值，與T是一棵最小生成樹矛盾。因此，與頂點(diǎn)1關(guān)聯(lián)的最小權(quán)值邊一定包含在一棵生成樹中。1ij

T1ij

1ij

T'Prim算法正確性證明（2）假設(shè)Prim算法第k步選擇的邊構(gòu)成一棵最小生成樹的邊，證明算法第k+1步選擇的邊也構(gòu)成一棵最小生成樹的邊。假設(shè)算法進(jìn)行了k步，生成樹的邊為e1,e2,...,ek，這些邊的端點(diǎn)構(gòu)成集合S，由歸納假設(shè)存在G的一棵最小生成樹T包含這些邊。算法第k+1步選擇頂點(diǎn)ik+1，則ik+1到S中頂點(diǎn)邊權(quán)值最小，設(shè)此邊ek+1=（ik，ik+1）。若ek+1∈T，則算法k+1顯然正確。Prim算法正確性證明若T不包含ek+1，將ek+1加T中形成一條回路，這條回路有另外一條連接S與頂點(diǎn)ik+1的邊e，令,則T*是一棵生成樹，包含e1,e2,...,ek，ek+1，且T*的各邊權(quán)值之和小于等于T的各邊權(quán)值之和，說明T*也是一顆最小生成樹，算法到k+1步仍然得到最小生成樹。證明過程如圖所示。權(quán)值最小ek+1i1ikS1

V-Sik+1e時間效率分析當(dāng)使用鄰接矩陣存儲圖時，Prim算法的時間復(fù)雜度為O(n2)，其中n是頂點(diǎn)的數(shù)量。這是因為Prim算法需要遍歷每個頂點(diǎn)，并在每次迭代中找到與當(dāng)前生成樹最近的頂點(diǎn)。當(dāng)使用鄰接表存儲圖時，Prim算法的時間復(fù)雜度為O((n+e)logn)，其中e是邊的數(shù)量。這是因為Prim算法使用最小堆來選擇最小權(quán)值的邊，每次從堆中取出邊的時間復(fù)雜度為O(logn)，而最多有n個頂點(diǎn)和e條邊。計算機(jī)算法設(shè)計與分析第5章貪心法5.2.3單源最短路徑問題給定一個帶權(quán)有向圖

G=(V,E)，其中每條邊的權(quán)是一個非負(fù)實數(shù)。給定圖G中的一個頂點(diǎn)v0∈V，稱為源點(diǎn)。求源點(diǎn)v0到G中其余各頂點(diǎn)的最短路徑長度。這里的長度是指路徑上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。5.2.3單源最短路徑問題源點(diǎn)終點(diǎn)最短路徑路徑長度11無

2(1,3,2)7

3(1,3)3

4(1,3,2,4)9

5(1,3,5)55.2.3單源最短路徑問題dist[i]表示計算過程中源點(diǎn)到各目標(biāo)頂點(diǎn)i的當(dāng)前最短路徑長度，dist[i]隨著計算過程會不斷變化，其初始值為源點(diǎn)到其余頂點(diǎn)有向邊的權(quán)值，若不存在有向邊則用無窮大。path[i]表示在最短路徑上頂點(diǎn)i的前一個頂點(diǎn)編號。集合S表示已求出最短路徑的頂點(diǎn)的集合。集合T（T=V-S）表示尚未確定最短路徑的頂點(diǎn)集合，V是圖G中頂點(diǎn)的集合。二維數(shù)組edge表示圖G的鄰接矩陣。貪心策略，Dijkstra算法迪杰斯特拉（Dijkstra）提出了一個按路徑長度遞增次序產(chǎn)生最短路徑的貪心算法，對于有向帶權(quán)圖