4 貪心算法與最優(yōu)策略

4貪婪算法與最優(yōu)戰(zhàn)略1學(xué)習(xí)要點(diǎn)貪婪算法的概念。貪婪算法的根本要素〔1〕最優(yōu)子構(gòu)造性質(zhì)〔2〕貪婪選擇性質(zhì)貪婪算法與動態(tài)規(guī)劃算法的差別運(yùn)用范例〔1〕活動安排問題；〔2〕最優(yōu)裝載問題；〔3〕哈夫曼編碼和數(shù)據(jù)緊縮；〔4〕單源最短途徑；〔5〕最小生成樹；〔6〕多機(jī)調(diào)度問題。2 貪婪算法總是作出在當(dāng)前看來最好的選擇。也就是說貪婪算法并不從整體最優(yōu)思索，它所作出的選擇只是在某種意義上的部分最優(yōu)選擇。當(dāng)然，希望貪婪算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪婪算法不能對一切問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解,如單源最短路經(jīng)問題、最小生成樹問題等。在一些情況下，即使貪婪算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的近似解。3貪婪戰(zhàn)略的思想例1付款問題超市POS給顧客找零，如26.8。“貪婪〞原那么：盡量給顧客大面值的錢。20、5、1、0.5、0.2、0.1問題描畫：知：intm[]={500,200,100,50,20,10,5,2,1};intv;輸出：各種鈔票數(shù)intn[10];使得1010Σn[i]*m[i]=v且Σn[i]最小。i=1i=14voidpay(intm[],intv){inti,r,n[10];for(i=0;i<10;i++)n[i]=0;r=v;i=0;while(r>0){if(m[i])<=r){r-=m[i];n[i]++;}elsei++;}for(i=0;i<10;i++)輸出n[i]個m[i]面值的鈔票。}5本節(jié)討論可以用貪婪算法求解的問題的普通特征。對于一個詳細(xì)的問題，怎樣知道能否可用貪婪算法解此問題，以及能否得到問題的最優(yōu)解呢?這個問題很難給予一定的回答。但是，從許多可以用貪婪算法求解的問題中看到這類問題普通具有2個重要的性質(zhì)：貪婪選擇性質(zhì)和最優(yōu)子構(gòu)造性質(zhì)。6

貪婪選擇性質(zhì)

所謂貪婪選擇性質(zhì)是指所求問題的整體最優(yōu)解可以經(jīng)過一系列部分最優(yōu)的選擇〔即貪婪選擇〕來得到。這是貪婪算法與動態(tài)算法的主要區(qū)別。對于一個詳細(xì)問題，要確定它能否具有貪婪選擇性質(zhì)，我們必需證明每一步所作的貪婪選擇最終導(dǎo)致問題的一個整體最優(yōu)解。

7

最優(yōu)子構(gòu)造性質(zhì)

當(dāng)一個問題的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱此問題具有最優(yōu)子構(gòu)造性質(zhì)。換句話說，問題的整體最優(yōu)性依賴于其部分子問題解的最優(yōu)性。8 共同點(diǎn)：貪婪算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子構(gòu)造性質(zhì)。 不同點(diǎn)：動態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪婪算法那么通常以自頂向下的方式進(jìn)展，以迭代的方式作出相繼的貪婪選擇，每作一次貪婪選擇就將所求問題簡化為規(guī)模更小的子問題。

問題1：對于具有最優(yōu)子構(gòu)造的問題應(yīng)該選用貪婪算法還是動態(tài)規(guī)劃算法求解?問題2：能否能用動態(tài)規(guī)劃算法求解的問題也能用貪婪算法求解?貪婪算法與動態(tài)規(guī)劃算法的差別9例20-1背包問題：給定n種物品和一個背包。物品i的分量是Wi，其價值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價值最大?背包問題： 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。10用貪婪算法解背包問題的根本步驟：

首先計算每種物品單位分量的價值Vi/Wi，然后，依貪婪選擇戰(zhàn)略，將盡能夠多的單位分量價值最高的物品裝入背包。假設(shè)將這種物品全部裝入背包后，背包內(nèi)的物品總分量未超越C，那么選擇單位分量價值次高的物品并盡能夠多地裝入背包。依此戰(zhàn)略不斷地進(jìn)展下去，直到背包裝滿為止。11voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);//各物品依單位分量的價值排序inti;floatc=M;for(i=1;i<=n;i++)x[i]=0;for(i=1;i<=n;i++){if(w[i]>c)break;x[i]=1;c-=w[i];}if(i<=n)x[i]=c/w[i];}算法knapsack的主要計算時間在于將各種物品依其單位分量的價值從大到小排序。因此，算法的計算時間上界為：O〔nlogn〕。為了證明算法的正確性，還必需證明背包問題具有貪婪選擇性質(zhì)。12 對于0-1背包問題，貪婪選擇之所以不能得到最優(yōu)解是由于在這種情況下，它無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了?，F(xiàn)實(shí)上，在思索0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多相互重疊的子問題。這正是該問題可用動態(tài)規(guī)劃算法求解的另一重要特征。 實(shí)踐上也是如此，動態(tài)規(guī)劃算法確實(shí)可以有效地解0-1背包問題。13例3：活動安排問題活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合。該問題要求高效地安排一系列爭用某一公共資源的活動。設(shè)有n個活動的集合E={1,2,…,n}，其中每個活動都要求運(yùn)用同一資源(如演講會場)，而在同一時間內(nèi)只需一個活動能運(yùn)用這一資源。每個活動i都有一個要求運(yùn)用該資源的起始時間si和一個終了時間fi,且si<fi。假設(shè)選擇了活動i，那么它在半開時間區(qū)間[si,fi)內(nèi)占用資源。假設(shè)區(qū)間[si,fi)與區(qū)間[sj,fj)不相交，那么稱活動i與活動j是相容的。也就是說，當(dāng)si≥fj或sj≥fi時，活動i與活動j相容。14例3活動安排問題例：設(shè)待安排的11個活動的開場時間和終了時間按終了時間的非減序陳列如下：i1234567891011S[i]130535688212f[i]456789101112131415i1234567891011S[i]130535688212f[i]4567891011121314例3活動安排問題算法greedySelector的計算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。16例3活動安排問題template<classType>voidGreedySelector(intn,Types[],Typef[],boolA[]){A[1]=true;intj=1;for(inti=2;i<=n;i++){if(s[i]>=f[j]){A[i]=true;j=i;}elseA[i]=false;}}各活動的起始時間和終了時間存儲于數(shù)組s和f中且按終了時間的非減序陳列17例3活動安排問題 由于輸入的活動以其完成時間的非減序陳列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動參與集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡能夠多的時間。也就是說，該算法的貪婪選擇的意義是使剩余的可安排時間段極大化，以便安排盡能夠多的相容活動。 算法greedySelector的效率極高。當(dāng)輸入的活動已按終了時間的非減序陳列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地運(yùn)用公共資源。假設(shè)所給出的活動未按非減序陳列，可以用O(nlogn)的時間重排。18例3活動安排問題假設(shè)被檢查的活動i的開場時間Si小于最近選擇的活動j的終了時間fi，那么不選擇活動i，否那么選擇活動i參與集合A中。 貪婪算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪婪算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學(xué)歸納法證明。19例4最優(yōu)裝載 有一批集裝箱要裝上一艘載分量為c的輪船。其中集裝箱i的分量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡能夠多的集裝箱裝上輪船。1、算法描畫 最優(yōu)裝載問題可用貪婪算法求解。采用分量最輕者先裝的貪婪選擇戰(zhàn)略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。詳細(xì)算法描畫如下頁。20template<classType>voidLoading(intx[],Typew[],Typec,intn){int*t=newint[n+1];Sort(w,t,n);for(inti=1;i<=n;i++)x[i]=0;for(inti=1;i<=n&&w[t[i]]<=c;i++){x[t[i]]=1;c-=w[t[i]];}}212、貪婪選擇性質(zhì) 可以證明最優(yōu)裝載問題具有貪婪選擇性質(zhì)。3、最優(yōu)子構(gòu)造性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子構(gòu)造性質(zhì)。 由最優(yōu)裝載問題的貪婪選擇性質(zhì)和最優(yōu)子構(gòu)造性質(zhì)，容易證明算法loading的正確性。 算法loading的主要計算量在于將集裝箱依其分量從小到大排序，故算法所需的計算時間為O(nlogn)。

22例5哈夫曼編碼 哈夫曼編碼是廣泛地用于數(shù)據(jù)文件緊縮的非常有效的編碼方法。其緊縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。1、前綴碼 對每一個字符規(guī)定一個0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。23 編碼的前綴性質(zhì)可以使譯碼方法非常簡單。 表示最優(yōu)前綴碼的二叉樹總是一棵嚴(yán)厲二叉樹，即樹中任一結(jié)點(diǎn)都有2個兒子結(jié)點(diǎn)。 平均碼長定義為： 使平均碼長到達(dá)最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。

242、構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪婪算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。 哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。 算法以|C|個葉結(jié)點(diǎn)開場，執(zhí)行|C|－1次的“合并〞運(yùn)算后產(chǎn)生最終所要求的樹T。

253、哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只需證明最優(yōu)前綴碼問題具有貪婪選擇性質(zhì)和最優(yōu)子構(gòu)造性質(zhì)。 (1)貪婪選擇性質(zhì) (2)最優(yōu)子構(gòu)造性質(zhì)26例6單源最短途徑 給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個頂點(diǎn)，稱為源。如今要計算從源到一切其它各頂點(diǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短途徑問題。 1、算法根本思想 Dijkstra算法是解單源最短途徑問題的貪婪算法。27例6單源最短途徑 其根本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪婪選擇來擴(kuò)展這個集合。一個頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短途徑長度知。 初始時，S中僅含有源。設(shè)u是G的某一個頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊途徑，并用數(shù)組dist記錄當(dāng)前每個頂點(diǎn)所對應(yīng)的最短特殊途徑長度。Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點(diǎn)u，將u添加到S中，同時對數(shù)組dist作必要的修正。一旦S包含了一切V中頂點(diǎn)，dist就記錄了從源到一切其它頂點(diǎn)之間的最短途徑長度。28例6單源最短途徑 例如，對右圖中的有向圖，運(yùn)用Dijkstra算法計算從源頂點(diǎn)1到其它頂點(diǎn)間最短途徑的過程列在下頁的表中。29例6單源最短途徑迭代Sudist[2]dist[3]dist[4]dist[5]初始{1}-10maxint301001{1,2}21060301002{1,2,4}4105030903{1,2,4,3}3105030604{1,2,4,3,5}510503060Dijkstra算法的迭代過程：30例6單源最短途徑2、算法的正確性和計算復(fù)雜性(1)貪婪選擇性質(zhì)(2)最優(yōu)子構(gòu)造性質(zhì)(3)計算復(fù)雜性 對于具有n個頂點(diǎn)和e條邊的帶權(quán)有向圖，假設(shè)用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需求時間。這個循環(huán)需求執(zhí)行n-1次，所以完成循環(huán)需求時間。算法的其他部分所需求時間不超越。31例7最小生成樹 設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。假設(shè)G的子圖G’是一棵包含G的一切頂點(diǎn)的樹，那么稱G’為G的生成樹。生成樹上各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在G的一切生成樹中，耗費(fèi)最小的生成樹稱為G的最小生成樹。 網(wǎng)絡(luò)的最小生成樹在實(shí)踐中有廣泛運(yùn)用。例如，在設(shè)計通訊網(wǎng)絡(luò)時，用圖的頂點(diǎn)表示城市，用邊(v,w)的權(quán)c[v][w]表示建立城市v和城市w之間的通訊線路所需的費(fèi)用，那么最小生成樹就給出了建立通訊網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。32例7最小生成樹1、最小生成樹性質(zhì) 用貪婪算法設(shè)計戰(zhàn)略可以設(shè)計出構(gòu)造最小生成樹的有效算法。本節(jié)引見的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是運(yùn)用貪婪算法設(shè)計戰(zhàn)略的例子。雖然這2個算法做貪婪選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。假設(shè)(u,v)E，且uU，vV-U，且在一切這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。33例7最小生成樹2、Prim算法 設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。 構(gòu)造G的最小生成樹的Prim算法的根本思想是：首先置S={1}，然后，只需S是V的真子集，就作如下的貪婪選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個過程不斷進(jìn)展到S=V時為止。 在這個過程中選取到的一切邊恰好構(gòu)成G的一棵最小生成樹。34例7最小生成樹 利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T一直包含G的某棵最小生成樹中的邊。因此，在算法終了時，T中的一切邊構(gòu)成G的一棵最小生成樹。 例如，對于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁圖所示。35例7最小生成樹36例7最小生成樹 在上述Prim算法中，還該當(dāng)思索如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)。實(shí)現(xiàn)這個目的的較簡單的方法是設(shè)置2個數(shù)組closest和lowcost。 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對closest和lowcost作必要的修正。 用這個方法實(shí)現(xiàn)的Prim算法所需的計算時間為37例7最小生成樹3、Kruskal算法 Kruskal算法構(gòu)造G的最小生成樹的根本思想是，首先將G的n個頂點(diǎn)看成n個孤立的連通分支。將一切的邊按權(quán)從小到大排序。然后從第一條邊開場，依邊權(quán)遞增的順序查看每一條邊，并按下述方法銜接2個不同的連通分支：當(dāng)查看到第k條邊(v,w)時，假設(shè)端點(diǎn)v和w分別是當(dāng)前2個不同的連通分支T1和T2中的頂點(diǎn)時，就用邊(v,w)將T1和T2銜接成一個連通分支，然后繼續(xù)查看第k+1條邊；假設(shè)端點(diǎn)v和w在當(dāng)前的同一個連通分支中，就直接再查看第k+1條邊。這個過程不斷進(jìn)展到只剩下一個連通分支時為止。38例7最小生成樹 例如，對前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如以下圖所示。39例7最小生成樹 關(guān)于集合的一些根本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。 按權(quán)的遞增順序查看等價于對優(yōu)先隊(duì)列執(zhí)行removeMin運(yùn)算。可以用堆實(shí)現(xiàn)這個優(yōu)先隊(duì)列。 對一個由連通分支組成的集合不斷進(jìn)展修正，需求用到籠統(tǒng)數(shù)據(jù)類型并查集UnionFind所支持的根本運(yùn)算。 當(dāng)圖的邊數(shù)為e時，Kruskal算法所需的計算時間是。當(dāng)時，Kruskal算法比Prim算法差，但當(dāng)時，Kruskal算法卻比Prim算法好得多。40例8多機(jī)調(diào)度問題 多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡能夠短的時間內(nèi)由m臺機(jī)器加工處置完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪婪選擇戰(zhàn)略有時可以設(shè)計出較好的近似算法。商定，每個作業(yè)均可在任何一臺機(jī)器上加工處置，但未完工前不允許中斷處置。作業(yè)不能拆分成更小的子作業(yè)。41例7多機(jī)調(diào)度問題 采用最優(yōu)點(diǎn)理時間作業(yè)優(yōu)先的貪婪選擇戰(zhàn)略可以設(shè)計出解多機(jī)調(diào)度問題的較好的近似算法。 按此戰(zhàn)略，當(dāng)時，只需將機(jī)器i的[0,ti]時間區(qū)間分配給作業(yè)i即可，算法只需求O(1)時間。 當(dāng)時，首先將n個作業(yè)依其所需的處置時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處置機(jī)。算法所需的計算時間為O(nlogn)。42例8多機(jī)調(diào)度問題 例如，設(shè)7個獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺機(jī)器M1，M2和M3加工處置。各作業(yè)所需的處置時間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如以下圖所示，所需的加工時間為17。434.8貪婪算法的實(shí)際根底 借助于擬陣工具，可建立關(guān)于貪婪算法的較普通的實(shí)際。這個實(shí)際對確定何時運(yùn)用貪婪算法可以得到問題的整體最優(yōu)解非常有用。1、擬陣 擬陣M定義為滿足下面3個條件的有序?qū)?S,I)： (1)S是非空有限集。 (2)I是S的一類具有遺傳性質(zhì)的獨(dú)立子集族，即假設(shè)BI，那么B是S的獨(dú)立子集，且B的恣意子集也都是S的獨(dú)立子集?？占貫镮的成員。 (3)I滿足交換性質(zhì)，即假設(shè)AI,BI且|A|<|B|，那么存在某一元素xB-A，使得A∪{x}I。444.8貪婪算法的實(shí)際根底 例如，設(shè)S是一給定矩陣中行向量的集合，I是S的線性獨(dú)立子集族，那么由線性空間實(shí)際容易證明(S,I)是一擬陣。擬陣的另一個例子是無向圖G=(V,E)的圖擬陣。 給定擬陣M=(S,I)，對于I中的獨(dú)立子集AI，假設(shè)S有一元素xA，使得將x參與A后仍堅持獨(dú)立性，即A∪{x}I,那么稱x為A的可擴(kuò)展元素。 當(dāng)擬陣M中的獨(dú)立子集A沒有可擴(kuò)展元素時，稱A為極大獨(dú)立子集。454.8貪婪算法的實(shí)際根底 下面的關(guān)于極大獨(dú)立子集的性質(zhì)是很有用的。 定理4.1：擬陣M中一切極大獨(dú)立子集大小一樣。 這個定理可以用反證法證明。 假設(shè)對擬陣M=(S,I)中的S指定權(quán)函數(shù)W，使得對于恣意xS，有W(x)>0，那么稱擬陣M為帶權(quán)擬陣。依此權(quán)函數(shù)，S的任一子集A的權(quán)定義為。2、關(guān)于帶權(quán)擬陣的貪婪算法 許多可以用貪婪算法求解的問題可以表示為求帶權(quán)擬陣的最大權(quán)獨(dú)立子集問題。

464.8貪婪算法的實(shí)際根底 給定帶權(quán)擬陣M=(S,I)，確定S的獨(dú)立子集AI使得W(A)到達(dá)最大。這種使W(A)最大的獨(dú)立子集A稱為擬陣M的最優(yōu)子集。由于S中任一元素x的權(quán)W(x)是正的，因此，最優(yōu)子集也一定是極大獨(dú)立子集。 例如，在最小生成樹問題可以表示為確定帶權(quán)擬陣的最優(yōu)子集問題。求帶權(quán)擬陣的最優(yōu)子集A的算法可用于解最小生成樹問題。 下面給出求帶權(quán)擬陣最優(yōu)子集的貪婪算法。該算法以具有正權(quán)函數(shù)W的帶權(quán)擬陣M=(S,I)作為輸入，經(jīng)計算后輸出M的最優(yōu)子集A。474.8貪婪算法的實(shí)際根底Setgreedy(M,W){A=;將S中元素依權(quán)值W〔大者優(yōu)先〕組成優(yōu)先隊(duì)列；while(S!=){S.removeMax(x);if(A∪{x}I)A=A∪{x};}returnA}484.8貪婪算法的實(shí)際根底 算法greedy的計算時間復(fù)雜性為。 引理4.2(擬陣的貪婪選擇性質(zhì)) 設(shè)M=(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，且S中元素依權(quán)值從大到小陳列。又設(shè)xS是S中第一個使得{x}是獨(dú)立子集的元素，那么存在S的最優(yōu)子集A使得xA。 算法greedy在以貪婪選擇構(gòu)造最優(yōu)子集A時，初次選入集合A中的元素x是單元素獨(dú)立集中具有最大權(quán)的元素。此時能夠曾經(jīng)舍棄了S中部分元素?？梢宰C明這些被舍棄的元素不能夠用于構(gòu)造最優(yōu)子集。494.8貪婪算法的實(shí)際根底 引理4.3：設(shè)M=(S,I)是擬陣。假設(shè)S中元素x不是空集的可擴(kuò)展元素，那么x也不能夠是S中任一獨(dú)立子集A的可擴(kuò)展元素。 引理4.4(擬陣的最優(yōu)子構(gòu)造性質(zhì)) 設(shè)x是求帶權(quán)擬陣M＝(S，I)的最優(yōu)子集的貪婪算法greedy所選擇的S中的第一個元素。那么，原問題可簡化為求帶權(quán)擬陣M’=(S’,I’)的最優(yōu)子集問題，其中： S’={y|yS且{x,y}I} I’={B|BS-{x}且B∪{x}I} M’的權(quán)函數(shù)是M的權(quán)函數(shù)在S’上的限制(稱M’為M關(guān)于元素x的收縮)。504.8貪婪算法的實(shí)際根底 定理4.5(帶權(quán)擬陣貪婪算法的正確性) 設(shè)M＝(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法greedy前往M的最優(yōu)子集。3、義務(wù)時間表問題 給定一個單位時間義務(wù)的有限集S。關(guān)于S的一個時間表用于描畫S中單位時間義務(wù)的執(zhí)行次序。時間表中第1個義務(wù)從時間0開場執(zhí)行直至?xí)r間1終了，第2個義務(wù)從時間1開場執(zhí)行至?xí)r間2終了，…，第n個義務(wù)從時間n-1開場執(zhí)行直至?xí)r間n終了。514.8貪婪算法的實(shí)際根底 具有截止時間和誤時懲罰的單位時間義務(wù)時間表問題可描畫如下。 (1)n個單位時間義務(wù)的集合S={1,2,…,n}； (2)義務(wù)i的截止時間,1≤i≤n,1≤≤n，即要求義務(wù)i在時間之前終了； (3)義務(wù)i的誤時懲罰,1≤i≤n,即義務(wù)i未在時間之前終了將招