第三章貪心算法課件

算法設(shè)計(jì)與分析——貪婪算法2023/7/201我們來(lái)看一個(gè)找硬幣的例子。假設(shè)有四種硬幣，它們的面值分別為二角五分、一角、五分和一分。現(xiàn)在要找給某顧客六角三分錢。這時(shí)，我們會(huì)不假思索地拿出2個(gè)二角五分的硬幣，1個(gè)一角的硬幣和3個(gè)一分的硬幣交給顧客。這種找硬幣方法與其他的找法相比，所拿出的硬幣個(gè)數(shù)是最少的。這里，我們下意識(shí)地使用了這樣的找硬幣算法：首先選出一個(gè)面值不超過(guò)六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個(gè)面值不超過(guò)三角八分的最大硬幣，即又一個(gè)二角五分，如此一直做下去。這個(gè)找硬幣的方法實(shí)際上就是貪婪算法。貪婪算法（greedyalgorithms,也叫登山法）2023/7/202顧名思義，貪婪算法總是作出在當(dāng)前看來(lái)是最好的選擇。也就是說(shuō)貪婪算法并不從整體最優(yōu)上加以考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。當(dāng)然，我們希望貪婪算法得到的最終結(jié)果也是整體最優(yōu)的。上面所說(shuō)的找硬幣算法得到的結(jié)果就是一個(gè)整體最優(yōu)解。雖然貪婪算法不是對(duì)所有問題都能得到整體最優(yōu)解，但對(duì)范圍相當(dāng)廣的許多問題它能產(chǎn)生整體最優(yōu)解。如圖的單源最短路徑問題，最小生成樹問題等。在一些情況下，即使貪婪算法不能得到整體最優(yōu)解，但其最終結(jié)果卻是最優(yōu)解的很好的近似解。2023/7/203設(shè)天平有一些25克的砝碼，一些10克的砝碼，一些5克的砝碼和一些1克的砝碼?，F(xiàn)要稱63克的物體，問至少需要用幾個(gè)砝碼。用貪婪算法，為了砝碼數(shù)最少，在不超過(guò)63克的前提下，每次都盡量選擇大的砝碼，即頭兩次選25克的，然后選一個(gè)10克的，最后選三個(gè)1克的。總共用六個(gè)砝碼，事實(shí)說(shuō)明這是最好的結(jié)果。例1．選取砝碼2023/7/204如果問題改成：砝碼的種類分別為11克、5克和1克，待稱的物體是15克。用貪婪算法應(yīng)先選一個(gè)11克的，然后選四個(gè)1克的，共用五個(gè)砝碼。這不是最優(yōu)結(jié)果，只要用三個(gè)5克的砝碼就夠了。貪婪算法雖不能保證得到最優(yōu)結(jié)果，但對(duì)于一些除了“窮舉”方法外沒有有效算法的問題，用貪婪算法往往能很快地得出較好的結(jié)果，如果此較好結(jié)果與最優(yōu)結(jié)果相差不是很多的話，此方法還是很實(shí)用的。2023/7/205設(shè)有n=8個(gè)體積分別為54，45，43，29，23，21，14，1的物體和一個(gè)容積為C=110的背包，問選擇哪幾個(gè)物體裝入背包可以使其裝的最滿。如直接用貪婪算法，將物體由大到小順次裝入背包，到裝不下時(shí)再逐個(gè)試裝更小的一些，直至試到最小的一個(gè)或裝滿為止。按此處所給數(shù)據(jù)，先裝入54和45兩個(gè)，容積尚余11，最后只能再裝入體積為1的一個(gè)，總體積達(dá)到100，并不算太滿。此方法的好處是節(jié)省時(shí)間，主要的運(yùn)算時(shí)間是用來(lái)對(duì)n個(gè)元素進(jìn)行排序，故其復(fù)雜性是O（nlogn）。例2.背包問題2023/7/206如果對(duì)上述算法作一些改進(jìn)，可得到更好的結(jié)果。先從n個(gè)物體中試著取j個(gè)總體積不超過(guò)C的裝入背包，剩下的(n-j)個(gè)物體則利用貪婪算法盡量往里裝。此j值從零開始逐漸增加，反復(fù)進(jìn)行試探，直至j達(dá)到某預(yù)先給定的常數(shù)k(0<k<n)，最后從這些結(jié)果中取其最好的一個(gè)。如果在試探中能得到一個(gè)完全裝滿的方案，則此過(guò)程就可提前結(jié)束。因?yàn)閺膎個(gè)物體中取出j個(gè)共有

種方案，此值隨著j的增加而增加較快，但可以證明此改進(jìn)算法的復(fù)雜性為O（knk+1）,因k是常數(shù)，故仍為多項(xiàng)式界的算法。2023/7/207按本例所給數(shù)值，取j=0時(shí)，因就是前述普通貪婪算法，已經(jīng)得到100的結(jié)果；取j=1時(shí)，共有8種方案，當(dāng)用29或23先裝入時(shí)，可得到54+29+23+1=107的更好結(jié)果；取j=2時(shí)，共有28種方案，其中有能將背包完全裝滿的結(jié)果（43+23+29+14+1=110）。故知此問題當(dāng)取k≥2時(shí)就可得到最優(yōu)解。2023/7/208當(dāng)n不太大時(shí)，適當(dāng)?shù)娜值，此改進(jìn)方法常?？梢缘玫阶顑?yōu)解，但不能因此就說(shuō)一般背包問題有多項(xiàng)式算法。當(dāng)n增大時(shí)，k不能隨著n不斷的加大，如k隨n增大而同時(shí)加大，其復(fù)雜性就是指數(shù)型而不是多項(xiàng)式型的了，而如k取值較小，又不能保證得出最優(yōu)解。2023/7/209設(shè)有5座城市，城市間的距離矩陣為：例3．巡回推銷員問題2023/7/2010將城市間的距離從小到大排列有：d24(1),d13(2),d15(2),d25(3),d45(6),d35(9),d34(9),d12(14),d14(16),d23(25)。

由于是5個(gè)城市，環(huán)繞一圈為5條邊，貪婪方法求解此問題的過(guò)程是從最小邊開始，依此從小到大取邊加入到回路邊集中，但在將1條邊加入時(shí)不能使1頂點(diǎn)的度數(shù)超過(guò)3，也不能形成小回路。此問題解的過(guò)程如下：

2023/7/2011d24(1)；d24(1)+d13(2)；d24(1)+d13(2)+d15(2)；d24(1)+d13(2)+d15(2)+d25(3)；d24(1)+d13(2)+d15(2)+d25(3)+[d45(6)]；（下標(biāo)中5出現(xiàn)了3次,頂點(diǎn)5有三條邊相連,d45(6)放棄）d24(1)+d13(2)+d15(2)+d25(3)+[d35(9)]；（下標(biāo)中5出現(xiàn)了3次,頂點(diǎn)5有三條邊相連,d35(9)放棄）d24(1)+d13(2)+d15(2)+d25(3)+d34(9)。得到一條回路：v1→v3→v4→v2→v5→v1同由分枝限解方法得到的路徑相同，因此是最佳的回路。2023/7/2012例4設(shè)有六個(gè)城市，其坐標(biāo)分別為a(0,0),b:(4,3),c:(1,7),d:(15,7),e(15,4),f:(18,0)。如下圖所示：2023/7/20136座城市間的距離矩陣為：2023/7/2014

用貪婪算法，先將任兩城市間的連線距離按從小到大的次序排列，然后從中逐個(gè)選擇。但有兩種情況的連線應(yīng)舍棄：

(1)使任一城市的度數(shù)（連線數(shù)）超過(guò)2的連線必須舍棄；

(2)在得到經(jīng)過(guò)所有點(diǎn)的回路前就形成小回路的連線必須舍棄。

距離按從小到大的次序排列:Dde(3),Dab(5),Dbc(5),Def(5),Dac(7.07),Ddf(7.62),Dbe(11.01),Dbd(11.7),Dcd(14),Dbf(14.32),Dce(14.32),Dae(15.52),Dad(16.55),Daf(18),Def(18.38)2023/7/2015

按貪婪算法原則，其選擇過(guò)程如下：Dde；Dde+Dab；Dde+Dab+Dbc；Dde+Dab+Dbc+Def；Dde+Dab+Dbc+Def+[Dac]；(形成小回路，舍棄)Dde+Dab+Dbc+Def+[Ddf]；(形成小回路，舍棄)Dde+Dab+Dbc+Def+[Dbe]；(b頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+[Dbd]；(b頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+Dcd；Dde+Dab+Dbc+Def+Dcd+[Dbf]；(b頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dce]；(c、e頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dae]；(e頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+Dcd+[Dad]；(d頂點(diǎn)度數(shù)超過(guò)2，舍棄)Dde+Dab+Dbc+Def+Dcd+Daf；得到1條回路2023/7/2016最后得到的回路如圖（a）的結(jié)果，總長(zhǎng)度為50。2023/7/2017不過(guò)，這不是此問題的最優(yōu)解，此問題的最優(yōu)解為下圖所示的路徑(可以用分枝限界等方法求得)，總長(zhǎng)度為48.39。用貪婪方法得到的結(jié)果同最優(yōu)解相比只多了3.3%。2023/7/2018設(shè)有n個(gè)獨(dú)立的作業(yè){1,2,…,n}，由m臺(tái)相同的機(jī)器進(jìn)行加工處理。作業(yè)i所需的處理時(shí)間為ti?，F(xiàn)約定，任何作業(yè)可以在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。任何作業(yè)不能拆分成更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。

例5:多機(jī)調(diào)度問題2023/7/2019這個(gè)問題是一個(gè)NP完全問題，到目前為止還沒有一個(gè)有效的解法。對(duì)于這一類問題，用貪婪選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪婪選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問題的較好的近似算法。按此策略，當(dāng)n≤m時(shí)，我們只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可。當(dāng)n＞m時(shí)，我們首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。2023/7/2020例如，設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺(tái)機(jī)器M1,M2,和M3來(lái)加工處理。各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。按貪婪算法產(chǎn)生的作業(yè)調(diào)度如圖4-13所示，所需的加工時(shí)間為17。當(dāng)n＞m時(shí)，因此算法所需的計(jì)算時(shí)間復(fù)雜度為O(nlogn)。2023/7/2021

一般情況下，用貪婪算法得到的是近似解，而不能保證得到最優(yōu)解。但用貪婪方法計(jì)算最小生成樹，卻可以設(shè)計(jì)出保證得到最優(yōu)解的算法。設(shè)G=(V,E)是一個(gè)無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的一個(gè)子圖G’是一棵包含G的所有頂點(diǎn)的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的費(fèi)用。在G的所有生成樹中，費(fèi)用最小的生成樹稱為G的最小生成樹。網(wǎng)絡(luò)的最小生成樹在實(shí)際中有廣泛應(yīng)用。例如，在設(shè)計(jì)通信網(wǎng)絡(luò)時(shí)，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通信線路所需的費(fèi)用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。例6:最小生成樹2023/7/2022

Kruskal

在1956年提出了1個(gè)最小生成樹算法，它的思路很容易理解。設(shè)G=(V,E)是一個(gè)連通帶權(quán)圖，V={1,2,…,n}。將圖中的邊按其權(quán)值由小到大排序，然后作如下的貪婪選擇，由小到大順序選取各條邊，若選某邊后不形成回路，則將其保留作為樹的一條邊；若選某邊后形成回路，則將其舍棄，以后也不再考慮。如此依次進(jìn)行，到選夠（n-1）條邊即得到最小生成樹。Kruskal最小生成樹算法2023/7/2023例如，對(duì)于下圖中的帶權(quán)圖各邊按權(quán)值排序?yàn)椋篸13=1d46=2d25=3d36=4d14=

5d34=5d23=5d12=6d35=6d56=62023/7/2024按Kruskal算法選取邊的過(guò)程如下圖所示。d13=1d46=2d25=3d36=4d14=5d34=5d23=5d12=6d35=6d56=62023/7/2025

Prim在1957年提出另一種算法，這種算法特別適用于邊數(shù)相對(duì)較多，即比較接近于完全圖的圖。此算法是按逐個(gè)將頂點(diǎn)連通的步驟進(jìn)行的，它只需采用一個(gè)頂點(diǎn)集合。這個(gè)集合開始時(shí)是空集，以后將已連通的頂點(diǎn)陸續(xù)加入到集合中去，到全部頂點(diǎn)都加入到集合中了，就得到所需的生成樹。設(shè)G=(V,E)是一個(gè)連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的一棵最小生成樹的Prim算法的過(guò)程是：首先從圖的任一頂點(diǎn)起進(jìn)行，將它加入集合S中置，S={1}，然后作如下的貪婪選擇，從與之相關(guān)聯(lián)的邊中選出權(quán)值c[i][j]最小的一條作為生成樹的一條邊，此時(shí)滿足條件iS，jV-S，并將該j加入集合中，表示連兩個(gè)頂點(diǎn)已被所選出的邊連通了。Prim最小生成樹算法2023/7/2026以后每次從一個(gè)端點(diǎn)在集合中而另一個(gè)端點(diǎn)在集合外的各條邊中選取權(quán)值最小的一條作為生成樹的一條邊，并把其在集合外的那個(gè)頂點(diǎn)加入到集合S中，表示該點(diǎn)也已被連通。如此進(jìn)行下去，直到全部頂點(diǎn)都加入到集合S中。在這個(gè)過(guò)程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。由于Prim算法中每次選取的邊兩端總是一個(gè)已連通頂點(diǎn)和一個(gè)未連通頂點(diǎn)，故這個(gè)邊選取后一定能將該未連通點(diǎn)連通而又保證不會(huì)形成回路。2023/7/2027例如，對(duì)于下圖(a)中的帶權(quán)圖，按Prim算法選取邊的過(guò)程如下圖(b)所示。2023/7/2028設(shè)一個(gè)帶權(quán)的圖表示一交通運(yùn)輸網(wǎng)絡(luò)，以圖的各個(gè)頂點(diǎn)代表一些城市，圖的各條邊表示城市之間的交通運(yùn)輸路線，每條邊的權(quán)值則表示此路線的長(zhǎng)度或表示沿此路線運(yùn)輸所需花費(fèi)的時(shí)間或運(yùn)費(fèi)等。運(yùn)輸路線往往是有方向性的，例如汽車運(yùn)輸有時(shí)會(huì)遇到單行路,而且不同的方向所花費(fèi)的時(shí)間或尺價(jià)可能不同，例如汽車的上山和下山、水路的順?biāo)湍嫠ㄙM(fèi)的時(shí)間或代價(jià)就不相同，所以交通運(yùn)輸網(wǎng)絡(luò)一般是有向圖，所謂最短路徑(Shortestpath)問題指的是：如果從圖中某頂點(diǎn)出發(fā)(此點(diǎn)稱為源點(diǎn)),經(jīng)圖的邊到達(dá)另一頂點(diǎn)（稱之為目的點(diǎn)）的路徑不止一條，如何找到一條路徑使沿此路徑上各邊的權(quán)值之和為最小。例7:最短路徑2023/7/2029給定一個(gè)帶權(quán)有向圖G=(V,E),其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外,還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在我們要計(jì)算從源到所有其他各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。

Dijkstra于1959年提出了解決此問題的一般算法，此算法可按邊的權(quán)值由小到大的次序，通過(guò)貪婪選擇，逐步得到由給定源點(diǎn)到圖的其余各點(diǎn)間的最短路徑。其基本作法是，設(shè)置一個(gè)頂點(diǎn)集合S，一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S中僅含有源點(diǎn)。設(shè)vi是G的某一個(gè)頂點(diǎn)，我們把從源點(diǎn)到vi且中間只經(jīng)過(guò)S中頂點(diǎn)的路稱為從源點(diǎn)到vi的路徑，并用數(shù)組dist來(lái)記錄當(dāng)前S中每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短路徑長(zhǎng)度。1．單源最短路徑2023/7/2030

Dijkstra算法每次從V-S中取出具有最短路徑長(zhǎng)度的頂點(diǎn)vi，將vi添加到S中，同時(shí)檢查vi添加到S中后，源點(diǎn)到V-S中各頂點(diǎn)的距離是否可以通過(guò)源點(diǎn)到vi的路徑而縮短，如果縮短則對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其他頂點(diǎn)之間的最短路徑長(zhǎng)度。例如下圖所示距離矩陣2023/7/2031現(xiàn)以頂點(diǎn)6為源點(diǎn)，求到其他各頂點(diǎn)的最短路徑長(zhǎng)度。2023/7/20322023/7/2033

例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其他頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。2023/7/2034迭代