第三章貪心算法

2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析1第三章

貪心算法2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析2貪心算法的特點(diǎn)貪心算法總是作出在當(dāng)前來看是最好的選擇。就是說，貪心算法并不從整體最優(yōu)上來考慮，所作出的選擇只是某種意義上的局部最優(yōu)選擇。當(dāng)然希望貪心算法得到的最終結(jié)果是最優(yōu)的?？墒秦澬乃惴ú⒉荒鼙ＷC最終結(jié)果是最優(yōu)的。不過，在許多的情況下，應(yīng)用貪心算法能夠得到整體最優(yōu)解；并且在一些情況下，即使得到的不是最優(yōu)解，也是一個(gè)很好的近似解。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析3貪心算法的一般框架GreedyAlgorithm(parameters){初始化；重復(fù)執(zhí)行以下的操作：選擇當(dāng)前可以選擇的(相容)最優(yōu)解；將所選擇的當(dāng)前解加入到問題的解中；直至滿足問題求解的結(jié)束條件。}2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析4最小生成樹設(shè)G=(V,E)是一個(gè)無向連通帶權(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的最小(優(yōu))生成樹。

2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析5樹的基本性質(zhì)連通無回路的圖G稱為樹。樹是點(diǎn)比邊多一的連通圖，G連通且q=p–1

。樹是點(diǎn)比邊多一的無回路圖：G無回路且q=p–1。樹若添?xiàng)l邊就有回路：G無回路，但對任意的u,v∈V(G)，若uvE(G)，則G+uv中恰有一條回路。樹若減條邊就不連通：G連通，但對e∈E(G),G–e不連通。n個(gè)頂點(diǎn)的連通圖的生成樹含有n–1條邊。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析6最小生成樹的貪心選擇性質(zhì)令G中權(quán)最小的邊為e1。首先必定有圖G的一棵最小生成樹包含了e1。若G的任何最小生成樹都不包含e1。設(shè)T為G的最小生成樹，e1T。于是T+e1是一個(gè)有回路的圖且該回路中包含e1。該回路中必有條不是e的邊ei。令T’={T+e1}–ei。T’也是G的生成樹。又c(T’)=c(T)+c(e1)–c(e1)，c(e1)≤c(ei)，從而c(T’)≤c(T)，T’是G的最小生成樹且含有邊e1。矛盾。故必定有圖G的最小生成樹包含了e1。選定第一條邊e1以后，該如何選擇第二條邊呢？依據(jù)各條邊的權(quán)重，依次選出權(quán)重較輕的n–1條邊。這n–1條邊必定包括了G的n個(gè)頂點(diǎn)。這樣就得到了G的一棵最小生成樹。這樣做是否可以呢？不行！因?yàn)椴荒鼙ＷC這n–1條邊構(gòu)成樹？要保證這n–1條邊構(gòu)成樹，必須使這n–1條邊是連通的或者是無回路的。Prim算法的做法：在保證連通的前提下依次選出權(quán)重較小的n–1條邊（在實(shí)現(xiàn)中體現(xiàn)為n個(gè)頂點(diǎn)的選擇）。Kruskal算法的做法：在保證無回路的前提下依次選擇權(quán)重較小的n–1條邊。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析7Prim算法基本思想：在保證連通的前提下依次選出權(quán)重較小的n–1條邊。G=(V,E)為無向連通帶權(quán)圖，令V={1,2,…,n}。設(shè)置一個(gè)集合S，初始化S={1}，T=Φ。貪心策略：如果V–S中的頂點(diǎn)j與S中的某個(gè)點(diǎn)i連接且(i,j)是E中的權(quán)重最小的邊，于是就選擇j(將j加入S)，并將(i,j)加入T中。重復(fù)執(zhí)行貪心策略，直至V–S為空。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析8Prim算法中的數(shù)據(jù)結(jié)構(gòu)圖用連接矩陣C[i][j]給出，即C[i][j]為結(jié)點(diǎn)i到結(jié)點(diǎn)j的權(quán)重。為了有效地找出V–S中滿足與S中的某個(gè)點(diǎn)i連接且(i,j)權(quán)重最小的頂點(diǎn)j，對其中的每個(gè)頂點(diǎn)j設(shè)立兩個(gè)數(shù)組closest[j]和lowcost[j]：closest[j]是s中與j最近的頂點(diǎn)，(closest[j],j)即為選中的邊，而lowcost[j]是相應(yīng)邊的權(quán)重。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析9Prim算法的實(shí)現(xiàn)Prim(intn,Type**c){

初始化：結(jié)點(diǎn)1放入S；并初始化lowcost[]和

closest[]；

執(zhí)行以下操作n–1次：依據(jù)lowcost[]找出與S最近的點(diǎn)j并放入S；

調(diào)整lowcost[]和closest[]；}intj=1;s[j]=true;for(inti=2;i<=n;i++){closest[i]=1;lowcost[i]=c[1][i];s[i]=false;}for(inti=1;i<n;i++){min=inf;for(intk=2;k<=n;k++){if(lowcost[k]<min&&!s[k]){min=lowcost[k];j=k}s[j]=true;s中僅加入了一個(gè)新成員j，因此只需要依據(jù)結(jié)點(diǎn)j調(diào)整lowcost[]和closest[]；for(intk=2;k<=n;k++){if(c[j][k]<lowcost[k]&&!s[k]){lowcost[k]=c[j][k];closest[k]=j}}}2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析10Prim算法的示例給定一個(gè)連通帶權(quán)圖如下：1234561655536624初始時(shí)S={1}，T=Φ；1第一次選擇：∵(1,3)權(quán)最小∴S={1,3}T={(1,3)}

；3第二次選擇：∵(3,6)權(quán)最小∴S={1,3,6}，

T={(1,3),(3,6)}

；6第三次選擇：∵(6,4)權(quán)最小∴S={1,3,6,4}，

T={(1,3),(3,6),(6,4)}

；4第四次選擇：∵(2,3)權(quán)最小∴S={1,3,6,4,2}，

T={(1,3),(3,6),(6,4),(2,3)}

；2第五次選擇：∵(5,2)權(quán)最小∴S={1,3,6,4,2,5}，

T={(1,3),(3,6),(6,4),(3,2)(2,5)}

；52023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析11Kruskal算法基本思想：在保證無回路的前提下依次選出權(quán)重較小的n–1條邊。貪心策略：如果(i,j)是E中尚未被選中的邊中權(quán)重最小的，并且(i,j)不會(huì)與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。問題：如何知道(i,j)不會(huì)造成回路？若邊(i,j)的兩個(gè)端點(diǎn)i和j屬于同一個(gè)連通分支，則選擇(i,j)會(huì)造成回路，反之則不會(huì)造成回路。因此初始時(shí)將圖的n個(gè)頂點(diǎn)看成n個(gè)孤立分支。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析12Kruskal算法的數(shù)據(jù)結(jié)構(gòu)數(shù)組e[][]表示圖的邊，e[i][u]、e[i][v]和e[k][w]分別表示邊i的兩個(gè)端點(diǎn)及其權(quán)重。函數(shù)Sort(e,w)將數(shù)組e按權(quán)重w從小到大排序。一個(gè)連通分支中的頂點(diǎn)表示為一個(gè)集合。函數(shù)Initialize(n)將每個(gè)頂點(diǎn)初始化為一個(gè)集合。函數(shù)Find(u)給出頂點(diǎn)u所在的集合。函數(shù)Union(a,b)給出集合a和集合b的并集。重載算符!=判斷集合的不相等。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析13Kruskal算法的實(shí)現(xiàn)Kruskal(intn,**e){Sort(e,w);//將邊按權(quán)重從小到大排序

initialize(n);//初始時(shí)每個(gè)頂點(diǎn)為一個(gè)集合

k=1;//k累計(jì)已選邊的數(shù)目，

j=1;//j為所選的邊在e中的序號

while(k<n)//選擇n–1條邊

{a=Find(e[j][u]);b=Find(e[j][v]);//找出第j條邊兩個(gè)端點(diǎn)所在的集合

if(a!=b){t[k++]=j;Union(a,b)}//若不同，第j條邊放入樹中并合并這兩個(gè)集合

j++}}//繼續(xù)考察下一條邊2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析14Kruskal算法的例子1234561655536624131462253364145235345126356566初始時(shí)為6個(gè)孤立點(diǎn)123456選擇了邊1，于是1、3點(diǎn)合并為同一個(gè)集合。√選擇了邊2，于是4、6點(diǎn)合并為同一個(gè)集合。√選擇了邊3，于是2、5點(diǎn)合并為同一個(gè)集合?！踢x擇了邊4，于是1、3、4、6點(diǎn)合并為同一個(gè)集合?！炭疾爝?，因?yàn)?、4點(diǎn)屬于同一個(gè)集合，被放棄?！吝x擇邊6，于是1、3、4、6、2、5點(diǎn)屬于同一個(gè)集合。√已經(jīng)選擇邊了n–1條邊，算法結(jié)束。結(jié)果如圖所示。uvw2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析15Prim與Kruskal兩算法的復(fù)雜性Prim算法為兩重循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)為O(n)，因此其復(fù)雜性為O(n2)。Kruskal算法中，設(shè)邊數(shù)為e，則邊排序的時(shí)間為O(e)，確定邊的時(shí)間為O(loge)，所以整個(gè)時(shí)間復(fù)雜性為O(eloge)。當(dāng)e=Ω(n2)時(shí)，Kruskal算法要比Prim算法差；當(dāng)e=ο(n2)時(shí)，Kruskal算法比Prim算法好得多。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析16貪心算法也能獲得最優(yōu)解用Kruskal算法得到的生成樹T*必是最優(yōu)樹。證明：設(shè)T*不是最優(yōu)，令T是與T*有k條共同邊的最優(yōu)樹且k是最優(yōu)樹與T*共有邊數(shù)的最大值?！?/p>

T≠T*∴

ek+1:ek+1E(T)且ek+1∈E(T*)。則T+ek+1含唯一回路C，C必有條邊ek’E(T*)。令T’=(T+ek)–ek’,w(T’)=w(T)+w(ek+1)–w(ek’)。由算法知，w(ek+1)w(ek’)，∴

T’是最優(yōu)樹。但T’與T*有k+1條共同邊，矛盾。故T*是最優(yōu)。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析170-1背包問題給定n個(gè)物品和一個(gè)背包。物品i的重量為wi，價(jià)值為vi，背包容量為c。問如何選擇裝入背包中的物品，使得裝入背包的物品的價(jià)值最大？在裝入背包時(shí)，每種物品i只有兩種選擇，裝入或者不裝入，既不能裝入多次，也不能只裝入一部分。因此，此問題稱為0-1背包問題。如果在裝入背包時(shí)，物品可以切割，即可以只裝入一部分，這種情況下的問題稱為背包問題。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析180-1背包問題不適用貪心算法背包容量為50kg，物品1,2和3的容量和價(jià)值分別為(10kg,$60),(20kg,$100)和(30kg,$120)。單位重量價(jià)值最高的為物品1，6$/kg。但是依照貪心算法首選物品1卻不能獲得最優(yōu)解：物品1物品2物品1物品3物品2物品3總價(jià)值為$160,空余20kg總價(jià)值為$180,空余10kg總價(jià)值為$220,沒有空余。但是背包問題卻是適用貪心算法的。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析19貪心算法的基本要素貪心算法的基本要素是：貪心選擇性質(zhì)。所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)解的選擇，即貪心選擇來達(dá)到。貪心選擇每次選取當(dāng)前最優(yōu)解，因此它依賴以往的選擇，而不依賴于將來的選擇。貪心算法通常以自頂向下的方式進(jìn)行，每次貪心選擇就將原問題轉(zhuǎn)化為規(guī)模更小的子問題。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析20如何確定貪心選擇性質(zhì)證明貪心選擇將導(dǎo)致整體的最優(yōu)解：首先證明存在問題的一個(gè)整體最優(yōu)解必定包含了第一個(gè)貪心選擇。然后證明在做了貪心選擇后，原問題簡化為規(guī)模較小的類似子問題，即可繼續(xù)使用貪心選擇。于是用數(shù)學(xué)歸納法可證明，經(jīng)過一系列貪心選擇可以得到整體最優(yōu)解。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析21單源最短路徑給定一個(gè)圖G=(V,E)，其中每條邊的權(quán)是一個(gè)非負(fù)實(shí)數(shù)。另外給定V中的一個(gè)頂點(diǎn)v，稱為源。求從源v到所有其它各個(gè)頂點(diǎn)的最短路徑。單源最短路徑問題的貪心選擇策略：選擇從源v出發(fā)目前用最短的路徑所到達(dá)的頂點(diǎn)，這就是目前的局部最優(yōu)解。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析22單源最短路徑的貪心算法基本思想：首先設(shè)置一個(gè)集合S；用數(shù)組dis[]來記錄v到S中各點(diǎn)的目前最短路徑長度。然后不斷地用貪心選擇來擴(kuò)充這個(gè)集合，并同時(shí)記錄或修訂數(shù)組dis[]；直至S包含所有V中頂點(diǎn)。貪心選擇：一個(gè)頂點(diǎn)u屬于S當(dāng)且僅當(dāng)從v到u的最短路徑長度已知。初始化：S中僅含有源v。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析23Dijkstra算法Dijkstra算法的做法是：由近到遠(yuǎn)逐步計(jì)算，每次最近的頂點(diǎn)的距離就是它的最短路徑長度。然后再從這個(gè)最近者出發(fā)。即依據(jù)最近者修訂到各頂點(diǎn)的距離，然后再選出新的最近者。如此走下去，直到所有頂點(diǎn)都走到。2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析24Dijkstra算法ProcedureDijkstra{(1)S:={1};//初始化S(2)fori:=2tondo//初始化D(3)dis[i]=C[1,i];//初始時(shí)為源到頂點(diǎn)i一步的距離(4)fori:=1ton-1do{(5)從V-S中選取一個(gè)頂點(diǎn)u使得dis[u]最?。?6)將u加入到S中；//將新的最近者加入S(7)forw∈V-Sdo//依據(jù)最近者u修訂dis[v](8)dis[w]:=min(dis[w],dis[u]+C[u,w)}}2023/2/1計(jì)算機(jī)算法設(shè)計(jì)與分析25Dijkstra算法舉例迭代Sudis[2]dis[3]dis[4]dis[5]初始{1}--10

∞301001{1,2}21060

30

1002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060

1254310205010030060賦權(quán)圖G由數(shù)組