第4章貪心算法

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

貪心算法2學(xué)習(xí)要點(diǎn)理解貪心算法的概念。掌握貪心算法的基本要素：

（1）最優(yōu)子結(jié)構(gòu)性質(zhì)（2）貪心選擇性質(zhì)理解貪心算法的一般理論通過(guò)應(yīng)用范例學(xué)習(xí)貪心設(shè)計(jì)策略。（1）最小生成樹(shù)；（2）單源最短路徑；（3）旅行商問(wèn)題；（4）活動(dòng)安排問(wèn)題；（5）最優(yōu)裝載問(wèn)題；2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析3找硬幣假設(shè)有四種硬幣，面值分別為二角五分一角五分一分現(xiàn)在要找給某顧客六角三分錢，哪種找錢方法拿出的硬幣個(gè)數(shù)最少呢？二角五分二角五分一角一分一分一分

首先選出一個(gè)面值不超過(guò)六角三分的最大硬幣，即二角五分；然后從六角三分中減去二角五分，剩下三角八分；再選出一個(gè)面值不超過(guò)三角八分的最大硬幣，即又一個(gè)二角五分，如此一直做下去。這種方法實(shí)際上就是貪心算法。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析4再找硬幣若硬幣的面值改為一分、五分和一角一分3種，而要找給顧客的是一角五分錢。還用貪心算法，將找個(gè)顧客1個(gè)一角一分的硬幣和4個(gè)一分的硬幣。然而，3個(gè)五分的硬幣顯然才是最好的找法。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析5貪心算法的適用情形設(shè)待求解問(wèn)題有N個(gè)輸入，根據(jù)必須滿足的條件和目標(biāo)函數(shù)，希望從問(wèn)題的所有允許解中求出最優(yōu)值。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析6貪心算法的特點(diǎn)貪心算法總是作出在當(dāng)前來(lái)看是最好的選擇。就是說(shuō)，貪心算法并不從整體最優(yōu)上來(lái)考慮，所作出的選擇只是某種意義上的局部最優(yōu)選擇。貪心法在解決問(wèn)題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來(lái)有什么結(jié)果，這個(gè)選擇都不會(huì)改變。這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解，但通常能獲得近似最優(yōu)解。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析7貪心算法的一般框架GreedyAlgorithm(parameters){初始化；重復(fù)執(zhí)行以下的操作：選擇當(dāng)前可以選擇的(相容)最優(yōu)解；將所選擇的當(dāng)前解加入到問(wèn)題的解中；直至滿足問(wèn)題求解的結(jié)束條件。}2023年2月3日8煤氣管道的鋪設(shè)

某新建小區(qū)著手鋪設(shè)煤氣管道，已知每一幢樓的接入位置和距離，請(qǐng)求出最短的鋪設(shè)方案。2023年2月3日9學(xué)校有n臺(tái)計(jì)算機(jī)，為了方便數(shù)據(jù)傳輸，現(xiàn)要將它們用數(shù)據(jù)線連接起來(lái)。兩臺(tái)計(jì)算機(jī)被連接是指它們之間有數(shù)據(jù)線連接。由于計(jì)算機(jī)所處的位置不同，因此不同的兩臺(tái)計(jì)算機(jī)的連接費(fèi)用往往是不同的。最優(yōu)布線問(wèn)題最優(yōu)通信網(wǎng)若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條線路即可。如何以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)，是一個(gè)網(wǎng)的最小生成樹(shù)問(wèn)題。2023年2月3日102023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析11最小生成樹(shù)設(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)的樹(shù)，則稱G’為G的生成樹(shù)。生成樹(shù)的各邊的權(quán)的總和稱為該生成樹(shù)的耗費(fèi)。在G的所有生成樹(shù)中，耗費(fèi)最小的生成樹(shù)稱為G的最小(優(yōu))生成樹(shù)。

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

。樹(shù)是點(diǎn)比邊多一的無(wú)回路圖：G無(wú)回路且q=p–1樹(shù)若添?xiàng)l邊就有回路：G無(wú)回路，但對(duì)任意的u,v∈V(G)，若uvE(G)，則G+uv中恰有一條回路樹(shù)若減條邊就不連通：G連通，但對(duì)e∈E(G),G–e不連通。n個(gè)頂點(diǎn)的連通圖的生成樹(shù)含有n–1條邊。2023年2月3日13實(shí)例BCAED706080509075300200BCAED705090300BCAED708050300BCAED70608050若G的任何最小生成樹(shù)都不包含e1。設(shè)T為G的最小生成樹(shù)，e1T。于是T+e1是一個(gè)有回路的圖且該回路中包含e1。該回路中必有條不是e1的邊ei。令T’={T+e1}–ei。T’也是G的生成樹(shù)。又c(T’)=c(T)+c(e1)–c(ei)，c(e1)≤c(ei)，從而c(T’)≤c(T)，T’是G的最小生成樹(shù)且含有邊e1。矛盾。故必定有圖G的最小生成樹(shù)包含了e1。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析14最小生成樹(shù)的貪心選擇性質(zhì)令G中權(quán)最小的邊為e1。首先必定有圖G的一棵最小生成樹(shù)包含了e1。選定第一條邊e1以后，該如何選擇第二條邊呢？依據(jù)各條邊的權(quán)重，依次選出權(quán)重較輕的n–1條邊。這n–1條邊必定包括了G的n個(gè)頂點(diǎn)。這樣就得到了G的一棵最小生成樹(shù)。這樣做是否可以呢？不行！因?yàn)椴荒鼙ＷC這n–1條邊構(gòu)成樹(shù)？要保證這n–1條邊構(gòu)成樹(shù)，必須使這n–1條邊是連通的或者是無(wú)回路的。Prim算法的做法：在保證連通的前提下依次選出權(quán)重較小的n–1條邊（在實(shí)現(xiàn)中體現(xiàn)為n個(gè)頂點(diǎn)的選擇）。Kruskal算法的做法：在保證無(wú)回路的前提下依次選擇權(quán)重較小的n–1條邊。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析15Prim算法基本思想：在保證連通的前提下依次選出權(quán)重較小的n–1條邊。G=(V,E)為無(wú)向連通帶權(quán)圖，令V={1,2,…,n}。設(shè)置一個(gè)集合S，初始化S={1}，T=Φ。貪心策略：如果V–S中的頂點(diǎn)j與S中的某個(gè)點(diǎn)i連接且(i,j)的權(quán)重最小，于是就選擇j(將j加入S)，并將(i,j)加入T中。重復(fù)執(zhí)行貪心策略，直至V–S為空。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析16Prim算法的示例給定一個(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/3計(jì)算機(jī)算法設(shè)計(jì)與分析17Prim算法中的數(shù)據(jù)結(jié)構(gòu)圖用連接矩陣C[i][j]給出，即C[i][j]為結(jié)點(diǎn)i到結(jié)點(diǎn)j的權(quán)重。標(biāo)志數(shù)組S[i]指示頂點(diǎn)i是否已經(jīng)加入到S中。為了有效地找出V–S中滿足與S中的某個(gè)點(diǎn)i連接且(i,j)權(quán)重最小的頂點(diǎn)j，對(duì)其中的每個(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)重。關(guān)鍵點(diǎn)：如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)？2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析18Prim算法的實(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(i=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(k=2;k<=n;k++){if(c[j][k]<lowcost[k]&&!s[k]){lowcost[k]=c[j][k];closest[k]=j}}}2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析19Kruskal算法基本思想：在保證無(wú)回路的前提下依次選出權(quán)重較小的n–1條邊。貪心策略：如果(i,j)是E中尚未被選中的邊中權(quán)重最小的，并且(i,j)不會(huì)與已經(jīng)選擇的邊構(gòu)成回路，于是就選擇(i,j)。問(wèn)題：如何知道(i,j)不會(huì)造成回路？若邊(i,j)的兩個(gè)端點(diǎn)i和j屬于同一個(gè)連通分支，則選擇(i,j)會(huì)造成回路，反之則不會(huì)造成回路因此初始時(shí)將圖的n個(gè)頂點(diǎn)看成n個(gè)孤立分支。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析20Kruskal算法的例子1234561655536624131462253364145235345126356566初始時(shí)為6個(gè)孤立點(diǎn)123456選擇了邊1，于是1、3點(diǎn)合并為同一個(gè)集合?！踢x擇了邊2，于是4、6點(diǎn)合并為同一個(gè)集合?！踢x擇了邊3，于是2、5點(diǎn)合并為同一個(gè)集合?！踢x擇了邊4，于是1、3、4、6點(diǎn)合并為同一個(gè)集合√考察邊5，因?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/3計(jì)算機(jī)算法設(shè)計(jì)與分析21Kruskal算法的數(shù)據(jù)結(jié)構(gòu)結(jié)構(gòu)數(shù)組e[]表示圖的邊，e[i].u、e[i].v和e[i].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/3計(jì)算機(jī)算法設(shè)計(jì)與分析22Kruskal算法的實(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中的序號(hào)

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);k=k+1;}//若不同，第j條邊放入樹(shù)中并合并這兩個(gè)集合

j++}}//繼續(xù)考察下一條邊2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析23Prim與Kruskal兩算法的復(fù)雜性Prim算法為兩重循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)為O(n)，因此其復(fù)雜性為O(n2)。Kruskal算法中，設(shè)邊數(shù)為e，則邊排序的時(shí)間為O(eloge)，最多對(duì)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/3計(jì)算機(jī)算法設(shè)計(jì)與分析24貪心算法也能獲得最優(yōu)解用Kruskal算法得到的生成樹(shù)T*必是最優(yōu)樹(shù)。證明：設(shè)T*不是最優(yōu)，令T是與T*有k條共同邊的最優(yōu)樹(shù)且k是最優(yōu)樹(shù)與T*共有邊數(shù)的最大值∵

T≠T*∴

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

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

12543102050100301060賦權(quán)圖G由數(shù)組dis[i]可知：從頂點(diǎn)1到頂點(diǎn)2、3、4、5的最短通路的長(zhǎng)度分別為10、50、30和60。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析34Dijkstra算法的貪心選擇性質(zhì)Dijkstra算法中所做的貪心選擇是：若u是V–S中具有最短路徑的特殊頂點(diǎn)，就將u選入S，并確定了從源到u的最短路徑長(zhǎng)度dis[u]。為什么從源到u沒(méi)有更短的路徑呢？若有，則將如下圖所示：Svdis[u](最近距離)uxdis[x]若該路徑經(jīng)S外一點(diǎn)x到達(dá)u，則：dis[x]+d(x,u)＜dis[u]從而dis[x]＜dis[u]，這與u的選取矛盾2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析35Dijkstra算法的計(jì)算復(fù)雜性Dijkstra算法有兩層循環(huán)，外層循環(huán)為n次，內(nèi)層有兩個(gè)循環(huán)：一個(gè)是選出最小的u(第5行)，另一個(gè)是修訂dis[w](第7、8行)，內(nèi)層循環(huán)的時(shí)間為O(n)。因此Dijkstra算法的時(shí)間復(fù)雜度為O(n2)。Dijkstra算法能求出從源到其它各頂點(diǎn)的最短通路的長(zhǎng)度，但是卻并沒(méi)有給出其最短通路。對(duì)Dijkstra算法做適當(dāng)?shù)男薷谋憧汕蟪鲎疃掏贰?023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析36旅行商問(wèn)題推銷員從某城市出發(fā)，遍歷n個(gè)城市最后返回出發(fā)城市。設(shè)從城市i到城市j的費(fèi)用為cij，如何選擇旅行路線使得該推銷員此趟旅行的總費(fèi)用最小?圖論語(yǔ)言表述：給定n個(gè)節(jié)點(diǎn)簡(jiǎn)單無(wú)向完全圖G=<V,E,c>，c(i,j)是節(jié)點(diǎn)i到j(luò)的代價(jià)(邊權(quán))。在G中求遍歷所有節(jié)點(diǎn)簡(jiǎn)單回路C，使C上所有邊權(quán)的和最小。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析37旅行商問(wèn)題分析123451∞12752∞4433∞124∞35∞

對(duì)于n個(gè)節(jié)點(diǎn)的旅行商問(wèn)題，n個(gè)節(jié)點(diǎn)的任意一個(gè)圓排列都是問(wèn)題的一個(gè)可能解。n個(gè)節(jié)點(diǎn)的圓排列有(n-1)!個(gè)，因此問(wèn)題歸結(jié)為在(n-1)!個(gè)回路中選取最小回路。是否能夠不用O((n-1)!)時(shí)間來(lái)求解旅行商問(wèn)題？2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析38旅行商問(wèn)題的貪心算法基本思想：首先設(shè)置一個(gè)集合Path和當(dāng)前節(jié)點(diǎn)v，然后不斷地用貪心選擇來(lái)擴(kuò)充這個(gè)集合，直至Path包含所有V中頂點(diǎn)。貪心選擇：如果V–Path中的頂點(diǎn)j是與當(dāng)前節(jié)點(diǎn)v相鄰接的頂點(diǎn)中邊權(quán)最小的，于是就選擇j(將j加入Path)，并將j作為新的當(dāng)前節(jié)點(diǎn)。初始化：Path中僅含有源v。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析39最臨近算法中的數(shù)據(jù)結(jié)構(gòu)圖用連接矩陣W[i][j]給出，即W[i][j]為結(jié)點(diǎn)i到結(jié)點(diǎn)j的權(quán)重。Path[]記錄依次連接的城市，p記錄當(dāng)前到達(dá)的最后一個(gè)頂點(diǎn)，cost為當(dāng)前路徑長(zhǎng)度。如果節(jié)點(diǎn)k已經(jīng)到達(dá)，則arrived[k]=true。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析40旅行商問(wèn)題的最臨近算法CostTypeTray_Greedy(intn,CostType**w,int*path){for(i=1;i<=n;i++)arrived[i]=false;cost=0;//初始化

path[1]=1;p=1;arrived[1]=true;//從節(jié)點(diǎn)1出發(fā)

for(i=2;i<=n;i++){min=inf;for(j=1;j<=n;j++)if(!arrived[j]&&w[p][j]<min){k=j;min=w[p][j]}//搜索最臨近p且尚未到達(dá)過(guò)的節(jié)點(diǎn)kcost=cost+w[p][k];path[i]=k;arrived[k]=true;p=k;//將節(jié)點(diǎn)k加入到路徑中

}cost=cost+w[p][1];returncost;//加上回路最后一條邊的權(quán)

}2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析41旅行商算法舉例從節(jié)點(diǎn)1出發(fā)：Path=<1,2,5,3,4,1>;cost=14;

因此最臨近法不保證求得旅行商問(wèn)題的精確解，只能得到問(wèn)題地近似解。一般地，貪心選擇只依賴于前面選擇步驟地最優(yōu)性，因此是局部最優(yōu)的，所以貪心法不能夠確保求出問(wèn)題的最優(yōu)解。不難看出，從節(jié)點(diǎn)2出發(fā)：Path=<2,1,3,4,5,2>;cost=10;且此為最優(yōu)解！2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析42改進(jìn)的旅行商算法如果分別從節(jié)點(diǎn)i出發(fā)（i=1,2,..n）執(zhí)行算法Tray_Greedy，通過(guò)結(jié)果比較，取最小代價(jià)回路，可以求得更接近于最佳解的近似解。作業(yè)：對(duì)算法Tray_Greedy進(jìn)行修改補(bǔ)充，得到改進(jìn)后的旅行商貪心算法Tray_Greedy1。

2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析43Tray_Greedy算法的計(jì)算復(fù)雜性Tray_Greedy算法有兩層循環(huán)，外層循環(huán)為n次，內(nèi)層循環(huán)也是n次，因此Tray_Greedy算法的時(shí)間復(fù)雜度為O(n2)Tray_Greedy1

算法分別從n個(gè)節(jié)點(diǎn)出發(fā)計(jì)算最小代價(jià)回路，其時(shí)間復(fù)雜度為O(n3)2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析44活動(dòng)安排問(wèn)題設(shè)有n個(gè)活動(dòng)的集合E={1,2,…,n}，其中每個(gè)活動(dòng)都要求使用同一資源，且在同一時(shí)間里只能有一個(gè)活動(dòng)可以使用該資源。現(xiàn)要求給出一個(gè)活動(dòng)安排，使得利用該資源活動(dòng)為最多。每個(gè)活動(dòng)i都有使用該資源的一個(gè)啟始時(shí)間si和一個(gè)結(jié)束時(shí)間fi，si＜fi，其占用資源的時(shí)間為半開(kāi)區(qū)間[si,fi)。若區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，則稱活動(dòng)i與活動(dòng)j是相容的。

活動(dòng)安排問(wèn)題就是求E的最大相容活動(dòng)子集。

2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析45活動(dòng)安排的例子i1234567891011s[i]650283183512f[i]1096131254118714

貪心法求解活動(dòng)安排問(wèn)題的關(guān)鍵是如何選擇貪心策略，使得按照一定的順序選擇相容活動(dòng)，并能安排盡量多的活動(dòng)。至少有兩種看似合理的貪心策略：（1）最早開(kāi)始時(shí)間：可以增大資源的利用率。（2）最早結(jié)束時(shí)間：可以使下一個(gè)活動(dòng)盡早開(kāi)始。

由于活動(dòng)占用資源的時(shí)間沒(méi)有限制，因此，后一種貪心選擇更為合理。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析46活動(dòng)安排問(wèn)題的貪心算法基本思想：某項(xiàng)活動(dòng)結(jié)束時(shí)間愈早，安排其它活動(dòng)的剩余區(qū)間愈大。所以貪心策略為盡量選擇結(jié)束時(shí)間早的活動(dòng)來(lái)安排。為此，將活動(dòng)按結(jié)束時(shí)間的非減順序排序，即f1≤f2≤…≤fn。顯然排序需要的時(shí)間為O(nlogn)。貪心選擇：當(dāng)安排下第i個(gè)活動(dòng)后，可能有：fi>si+1，所以第i+1個(gè)活動(dòng)無(wú)法安排，這就必須舍棄第i+1個(gè)活動(dòng)，檢測(cè)第i+2個(gè)活動(dòng)……直到第i+k個(gè)活動(dòng)的si+k>fi，就把此活動(dòng)安排進(jìn)來(lái)。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析47先將所有活動(dòng)按照結(jié)束時(shí)間f[i]遞增排序活動(dòng)安排的例子首先選定活動(dòng)1，其結(jié)束時(shí)間f[1]=4。然后因s[4]=5≥4，選定活動(dòng)4，這時(shí)f[4]=7。又因s[8]=8≥7，選定活動(dòng)8，這時(shí)f[8]=11。最后因s[11]=12≥11，選定活動(dòng)11。最終的活動(dòng)安排為：1、4、8和11。i1234567891011s[i]130535688212f[i]45678910111213142023年2月3日48活動(dòng)安排的貪心算法將所有活動(dòng)按結(jié)束時(shí)間排序，得到活動(dòng)集合E={e1,e2…en}；先將e1選入結(jié)果集合A中，即A={e1}；依次掃描每一個(gè)活動(dòng)ei：

如果ei的開(kāi)始時(shí)間晚于最后一個(gè)選入A的活動(dòng)ej的結(jié)束時(shí)間，則將ei選入A中，否則放棄ei；2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析49活動(dòng)安排貪心算法的實(shí)現(xiàn)typedefstruct{

int

number;//活動(dòng)的編號(hào)

floatstart;

//活動(dòng)開(kāi)始的時(shí)間

floatend;

//活動(dòng)結(jié)束的時(shí)間

Boolselected;//標(biāo)記活動(dòng)是否被選擇

}Active;intgreedySelector(Activeactivity[],intn){QuickSort(activity,n);//將活動(dòng)按結(jié)束時(shí)間排序

activity[1].selected=true;

j=1;count=1;

for(i=2;i<=n;i++)

if(activity[i].start>=activity[j].end){activity[i].selected=true;

j=i;count++;}

else

activity[i].selected=false;

returncount;

}2023年2月3日50算法正確性證明需要證明：活動(dòng)安排問(wèn)題有一個(gè)最優(yōu)解以貪心選擇開(kāi)始；活動(dòng)安排問(wèn)題具有最優(yōu)子結(jié)構(gòu)；算法每一步按照貪心選擇計(jì)算，最終可得到原問(wèn)題的一個(gè)最優(yōu)解。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析51貪心算法能夠得到活動(dòng)安排問(wèn)題的最優(yōu)解設(shè)活動(dòng)集合E={1,2,…,n}已按結(jié)束時(shí)間的非減順序排列，活動(dòng)1具有最早結(jié)束時(shí)間。首先必定有最優(yōu)解包含活動(dòng)1。否則設(shè)A是E的最優(yōu)解，且A中最早結(jié)束的活動(dòng)是k。若k＞1，則活動(dòng)1必與A中除k以外的活動(dòng)相容。令B=A–{k}∪{1}，則B也是最優(yōu)解。進(jìn)一步，假設(shè)A是原問(wèn)題的包含活動(dòng)1的最優(yōu)解，則A’=A–{1}是活動(dòng)集合E’={i∈E且si≥f1}的一個(gè)最優(yōu)解。反之，如果能夠找到E’的一個(gè)解B’，它包含了比A’更多的活動(dòng)，則將活動(dòng)1加入到B’中將產(chǎn)生E的一個(gè)解B，它包含比A更多的活動(dòng)。這與假設(shè)矛盾。因此，所做的每一步貪心選擇都將產(chǎn)生一個(gè)比原問(wèn)題規(guī)模更小的具有相同特征的子問(wèn)題。由數(shù)學(xué)歸納法可知，貪心法得到的是最優(yōu)解。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析52算法復(fù)雜性分析算法由兩部分組成：第一部分是排序，時(shí)間復(fù)雜度為O(nlogn)；第二部分是選擇合適的活動(dòng)，是一個(gè)定長(zhǎng)循環(huán)，時(shí)間復(fù)雜度為O(n)；故總的時(shí)間復(fù)雜度為O(nlogn)。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析53最優(yōu)裝載問(wèn)題有一批集裝箱要裝上一艘載重為C的輪船。其中集裝箱i的重量為Wi。假定裝載體積不受限制，要將盡可能多(這個(gè)多，是指的貨物數(shù)目)的集裝箱裝上輪船。

該問(wèn)題的形式化描述為：有約束條件

其中，xi=0表示不裝入集裝箱，xi=1反之。2023/2/3計(jì)算機(jī)算法設(shè)計(jì)與分析54最優(yōu)裝載問(wèn)題的貪心算法基本思想：這個(gè)題目比較簡(jiǎn)單，可以用貪心法求解。每次采用