第四章-貪心算法

計(jì)算機(jī)與信息科學(xué)學(xué)院2010-2011學(xué)年第2學(xué)期模擬試卷計(jì)算機(jī)算法設(shè)計(jì)與分析一第四章.貪心算法本卷滿分100分 完卷時(shí)間120分鐘簡答題(每小題2分，共20分)當(dāng)一個(gè)問題具有且具有時(shí)可用貪心算法，如最小生成樹問題(背包問題，活動安排問題等)。在動態(tài)規(guī)劃可行的基礎(chǔ)上滿足才能用貪心。貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的選擇。動態(tài)規(guī)劃算法通常以的方式解各子問題，而貪心算法則通常以的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題貪心算法和動態(tài)規(guī)劃算法都要求問題具有性質(zhì)，這是2類算法的一個(gè)共同點(diǎn)。當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有。對于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要。(〃)時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過。0-1背包問題指：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的最大。有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在不受限制的情況下，將裝上輪船。多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在 —由m臺機(jī)器加工處理完成。.綜合題(1-6題每題7分，7-8題每題9分，共60分)有4個(gè)物品，其重量分別為(4,7,5,3)，物品的價(jià)值分別為(40,42,25,12)，背包容量為10。試設(shè)計(jì)3種貪心策略，并給出在每種貪心策略下背包問題的解。使用prim算法構(gòu)造出如下圖G的一棵最小生成樹。dist(1,2)=6;dist(2,5)=3;dist(5,6)=6;dist(6,4)=2;dist(4,1)=5;dist(1,3)=1;dist(2,3)=5;dist(3,4)=5;dist(3,6)=4;dist(5,3)二6設(shè)有n項(xiàng)獨(dú)立的作業(yè)｛1,2,…，n),由m臺相同的機(jī)器加工處理。作業(yè)i所需要的處理時(shí)間為t。約定：任何一項(xiàng)作業(yè)可在任何一臺機(jī)器上處理，但未完工前不準(zhǔn)中斷處理；任何作業(yè)不能拆分更小的子作業(yè)。多機(jī)調(diào)度問題要求給出一種調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺機(jī)器處理完。設(shè)計(jì)算法，并討論是否可獲最優(yōu)解。設(shè)有n種面值為:dNdN……Nd的錢幣，需要找零錢M,如何選擇錢1 2 n幣d，的數(shù)目X，滿足dXX+……dXXM，使得X+……X最小。k k 1i nn i請選擇貪心策略，并設(shè)計(jì)貪心算法。在下列空格中填入適當(dāng)?shù)恼Z句完成貪心方法的抽象化控制procedureGREEDY(A，n)//A(1：n)包含n個(gè)輸入//TOC\o"1-5"\h\zsolutions—① ；fori—1to②dox—SELECT(A)ifFEASIBLE(solution,x)thensolutions—③ ；endif④ ；return(solution)endGREEDY填空完成背包問題的貪心算法procedureGREEDY-KNAPSACK(P,W,M,X,n)X—0//將解向量初始化為零//cu—M//cu是背包剩余容量//fori—1tondoif① thenexitendifX(i)—②一；TOC\o"1-5"\h\zcu— ③ ；④ ；ifi^nthenX(i)—⑤ ；endifendGREEDY-KNAPSACK填空完成帶有限期的作業(yè)排序lineprocedureJS(D,J,n,k)//D(1)，…，D(n)是期限值。nN1。作業(yè)已按p1^p2^—p被排序。J(i)是最優(yōu)解中的第i個(gè)作業(yè)，1忍i可。終止時(shí)，D(J(i)過(J(I+1)),1^i<k//1integerD(0：n),J(0：n),i,k,n,r2D(0)—J(0)—0//初始化//3k—1；J(1)—1//計(jì)入作業(yè)1//4for①tondo5② ；6while③and④ do7⑤ ；8repeat9ifD(J(r))^D(i)andD(i)>rthen10for⑥ ⑦ by-ldo11⑧?；12repeat13⑨ ；k—k+1；endifrepeatendJS有n個(gè)活動爭用一個(gè)活動室。已知活動i占用的時(shí)間區(qū)域?yàn)椋踫」fi］，活動i,j相容的條件是：sjNfj，問題的解表示為（x」xi=1,2…，n,），xi表示順序?yàn)閕的活動編號活動，求一個(gè)相容的活動子集，且安排的活動數(shù)目最多。三.簡答題（每題5分，共20分）簡述貪心法的設(shè)計(jì)思想。簡述Kruskal算法構(gòu)造G的最小生成樹的基本思想試舉例說明貪心算法對有的問題是有效的，而對一些問題是無效的。簡述貪心算法與動態(tài)規(guī)劃算法的差異

參考答案:、填空題:最優(yōu)子結(jié)構(gòu)性質(zhì)貪心選擇性質(zhì)貪心選擇性局部最優(yōu)自底向上自頂向下最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)7.O（n2）O（n2）總價(jià)值盡可能多的集裝箱盡可能短的時(shí)間內(nèi)二、綜合題：解：重量最輕：裝入1，4，3.總價(jià)值：40+12+25*3/5=67價(jià)值最大：裝入1,2。總價(jià)值：40*3/4+42=72性價(jià)比最?。貉b入1,2.總價(jià)值:40+6/7*42=76〃從第一個(gè)處理機(jī)開始安排〃從第一個(gè)處理機(jī)開始安排〃安排n個(gè)作業(yè)//選下一個(gè)處理機(jī)對于處理機(jī)j,用S[j]表示處理機(jī)j已有的作業(yè)數(shù)，用P[j,k]表示處理機(jī)j的第k個(gè)作業(yè)的序號。1）將作業(yè)按照t[1]Nt[2]N……Nt[n]排序S[1:m]清零j_0fori—1tondoj—jmodm+1S[j]—S[j]+1;P[j,S[j]]—i；Repeat解：貪心原則：每次選擇最大面值硬幣。CU-M;iJ1;X-0 //X為解向量WhileCU#0doX[i]-CUdivd[i]//X[i]為第i中硬幣數(shù)CU—CU-d[i]*X[i-i+1;repeat①①②n③UNION(solution,x)④repeat①W(i)Wcu②1③cu-W(i)④repeat⑤cu/W(i)①i=2 ②r-k③D(J(r))>D(i)④D(J(r))<>r⑤r—rT⑥l—k⑦r+1⑧ J(I+1)—J(l)⑨J(r+1)—i解：解決這個(gè)問題的基本思路是在安排時(shí)應(yīng)該將結(jié)束時(shí)間早的活動盡量往前安排，好給后面的活動安排留出更多的空間，從而達(dá)到安排最多活動的目標(biāo)。據(jù)此，貪心準(zhǔn)則應(yīng)當(dāng)是：在未安排的活動中挑選結(jié)束時(shí)間最早的活動安排。在貪心算法中，將各項(xiàng)活動的開始時(shí)間和結(jié)束時(shí)間分別用兩個(gè)數(shù)組s和f存儲，并使得數(shù)組中元素的順序按結(jié)束時(shí)間非減排列：f1?f2?…？fn。算法如下：GreedyAction(s,f，n)//s[1:n]、f[1:n]分別代表n項(xiàng)活動的起始〃時(shí)間和結(jié)束時(shí)間，并且滿足f[1]?f[2]?…？f[n]j=1;solution={1};//解向量初始化為空集fori—2tondoifsi?fjthensolution=solution?{j}; //將j加入解中j=i;endifendforreturn(solution);endGreedy簡答題把一個(gè)問題分解為一系列較為簡單的局部最優(yōu)選擇，每一步選擇都是對當(dāng)前解的一個(gè)擴(kuò)展，直到獲得問題的完整解。(指根據(jù)當(dāng)前已有信息做出選擇，不從整體最優(yōu)考慮，只選擇局部最優(yōu))首先將G的n個(gè)頂點(diǎn)看成n個(gè)孤立的連通分支。將所有的邊按權(quán)從小到大排序。然后從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個(gè)不同的連通分支：當(dāng)查看到第k條邊(v,w)時(shí)，如果端點(diǎn)v和w分別是當(dāng)前2個(gè)不同的連通分支T1和T2中的頂點(diǎn)時(shí)，就用邊(v,w)將T1和T2連接成一個(gè)連通分支，然后繼續(xù)查看第k+1條邊;如果端點(diǎn)v和w在當(dāng)前的同一個(gè)連通分支中，就直接再查看第k+1條邊。這個(gè)過程一直進(jìn)行到只剩下一個(gè)連通分支時(shí)為止。貪心算有效性：最小生