54.1活動(dòng)安排問題templatevoidGreedySelector(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;}}下面給出解活動(dòng)安排問題的貪心算法GreedySelector:各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)組s和f中且按結(jié)束時(shí)間的非減序排列6第六頁(yè)，共六十頁(yè)。
64.1活動(dòng)安排問題由于輸入的活動(dòng)以其完成時(shí)間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時(shí)間的相容活動(dòng)加入集合A中。直觀上，按這種方法選擇相容活動(dòng)為未安排活動(dòng)留下盡可能多的時(shí)間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時(shí)間段極大化，以便安排盡可能多的相容活動(dòng)。算法greedySelector的效率極高。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需O(n)的時(shí)間安排n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。如果所給出的活動(dòng)未按非減序排列，可以用O(nlogn)的時(shí)間重排。7第七頁(yè)，共六十頁(yè)。
74.1活動(dòng)安排問題例：設(shè)待安排的11個(gè)活動(dòng)的開始時(shí)間和結(jié)束時(shí)間按結(jié)束時(shí)間的非減序排列如下：i1234567891011S[i]130535688212f[i]45678910111213148第八頁(yè)，共六十頁(yè)。
84.1活動(dòng)安排問題算法greedySelector的計(jì)算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長(zhǎng)條表示的活動(dòng)是已選入集合A的活動(dòng)，而空白長(zhǎng)條表示的活動(dòng)是當(dāng)前正在檢查相容性的活動(dòng)。9第九頁(yè)，共六十頁(yè)。
94.1活動(dòng)安排問題若被檢查的活動(dòng)i的開始時(shí)間Si小于最近選擇的活動(dòng)j的結(jié)束時(shí)間fi，則不選擇活動(dòng)i，否則選擇活動(dòng)i加入集合A中。貪心算法并不總能求得問題的整體最優(yōu)解。但對(duì)于活動(dòng)安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動(dòng)集合A的規(guī)模最大。這個(gè)結(jié)論可以用數(shù)學(xué)歸納法證明。10第十頁(yè)，共六十頁(yè)。
104.2貪心算法的基本要素本節(jié)著重討論可以用貪心算法求解的問題的一般特征。對(duì)于一個(gè)具體的問題，怎么知道是否可用貪心算法解此問題，以及能否得到問題的最優(yōu)解呢?這個(gè)問題很難給予肯定的回答。但是，從許多可以用貪心算法求解的問題中看到這類問題一般具有2個(gè)重要的性質(zhì)：貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。11第十一頁(yè)，共六十頁(yè)。
114.2貪心算法的基本要素1、貪心選擇性質(zhì)所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇，即貪心選擇來達(dá)到。這是貪心算法可行的第一個(gè)基本要素，也是貪心算法與動(dòng)態(tài)規(guī)劃算法的主要區(qū)別。動(dòng)態(tài)規(guī)劃算法通常以自底向上的方式解各子問題，而貪心算法則通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡(jiǎn)化為規(guī)模更小的子問題。對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇性質(zhì)，必須證明每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。12第十二頁(yè)，共六十頁(yè)。
124.2貪心算法的基本要素當(dāng)一個(gè)問題的最優(yōu)解包含其子問題的最優(yōu)解時(shí)，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動(dòng)態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。2、最優(yōu)子結(jié)構(gòu)性質(zhì)13第十三頁(yè)，共六十頁(yè)。
134.2貪心算法的基本要素貪心算法和動(dòng)態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)，這是2類算法的一個(gè)共同點(diǎn)。但是，對(duì)于具有最優(yōu)子結(jié)構(gòu)的問題應(yīng)該選用貪心算法還是動(dòng)態(tài)規(guī)劃算法求解?是否能用動(dòng)態(tài)規(guī)劃算法求解的問題也能用貪心算法求解?下面研究2個(gè)經(jīng)典的組合優(yōu)化問題，并以此說明貪心算法與動(dòng)態(tài)規(guī)劃算法的主要差別。3、貪心算法與動(dòng)態(tài)規(guī)劃算法的差異14第十四頁(yè)，共六十頁(yè)。
144.2貪心算法的基本要素0-1背包問題：給定n種物品和一個(gè)背包。物品i的重量是Wi，其價(jià)值為Vi，背包的容量為C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大?在選擇裝入背包的物品時(shí)，對(duì)每種物品i只有2種選擇，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。15第十五頁(yè)，共六十頁(yè)。
154.2貪心算法的基本要素背包問題：與0-1背包問題類似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。16第十六頁(yè)，共六十頁(yè)。
164.2貪心算法的基本要素首先計(jì)算每種物品單位重量的價(jià)值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量?jī)r(jià)值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。具體算法可描述如下頁(yè)：用貪心算法解背包問題的基本步驟：17第十七頁(yè)，共六十頁(yè)。
174.2貪心算法的基本要素voidKnapsack(intn,floatM,floatv[],floatw[],floatx[]){Sort(n,v,w);inti;for(i=1;i<=n;i++)x[i]=0;floatc=M;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的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。因此，算法的計(jì)算時(shí)間上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。18第十八頁(yè)，共六十頁(yè)。
184.2貪心算法的基本要素對(duì)于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮0-1背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動(dòng)態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。19第十九頁(yè)，共六十頁(yè)。
194.3最優(yōu)裝載有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。1、算法描述最優(yōu)裝載問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁(yè)。20第二十頁(yè)，共六十頁(yè)。
204.3最優(yōu)裝載templatevoidLoading(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]];}}21第二十一頁(yè)，共六十頁(yè)。
214.3最優(yōu)裝載2、貪心選擇性質(zhì)可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。3、最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。算法loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為O(nlogn)。22第二十二頁(yè)，共六十頁(yè)。
224.4哈夫曼編碼哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個(gè)用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長(zhǎng)的編碼，可以大大縮短總碼長(zhǎng)。1、前綴碼對(duì)每一個(gè)字符規(guī)定一個(gè)0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼。23第二十三頁(yè)，共六十頁(yè)。
234.4哈夫曼編碼編碼的前綴性質(zhì)可以使譯碼方法非常簡(jiǎn)單。表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。平均碼長(zhǎng)定義為：使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。24第二十四頁(yè)，共六十頁(yè)。
244.4哈夫曼編碼2、構(gòu)造哈夫曼編碼哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個(gè)葉結(jié)點(diǎn)開始，執(zhí)行|C|－1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹T。25第二十五頁(yè)，共六十頁(yè)。
254.4哈夫曼編碼在書上給出的算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列Q。經(jīng)過n－1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹T。算法huffmanTree用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，由于最小堆的removeMin和put運(yùn)算均需O(logn)時(shí)間，n－1次的合并總共需要O(nlogn)計(jì)算時(shí)間。因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間為O(nlogn)。26第二十六頁(yè)，共六十頁(yè)。
264.4哈夫曼編碼3、哈夫曼算法的正確性要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)。(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)27第二十七頁(yè)，共六十頁(yè)。
274.5單源最短路徑給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實(shí)數(shù)。另外，還給定V中的一個(gè)頂點(diǎn)，稱為源?，F(xiàn)在要計(jì)算從源到所有其它各頂點(diǎn)的最短路長(zhǎng)度。這里路的長(zhǎng)度是指路上各邊權(quán)之和。這個(gè)問題通常稱為單源最短路徑問題。1、算法基本思想Dijkstra算法是解單源最短路徑問題的貪心算法。28第二十八頁(yè)，共六十頁(yè)。
284.5單源最短路徑其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。初始時(shí)，S中僅含有源。設(shè)u是G的某一個(gè)頂點(diǎn)，把從源到u且中間只經(jīng)過S中頂點(diǎn)的路稱為從源到u的特殊路徑，并用數(shù)組dist記錄當(dāng)前每個(gè)頂點(diǎn)所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。Dijkstra算法每次從V-S中取出具有最短特殊路長(zhǎng)度的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改。一旦S包含了所有V中頂點(diǎn)，dist就記錄了從源到所有其它頂點(diǎn)之間的最短路徑長(zhǎng)度。29第二十九頁(yè)，共六十頁(yè)。
294.5單源最短路徑例如，對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過程列在下頁(yè)的表中。30第三十頁(yè)，共六十頁(yè)。
304.5單源最短路徑迭代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算法的迭代過程：31第三十一頁(yè)，共六十頁(yè)。
314.5單源最短路徑2、算法的正確性和計(jì)算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計(jì)算復(fù)雜性對(duì)于具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個(gè)圖，那么Dijkstra算法的主循環(huán)體需要時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時(shí)間。算法的其余部分所需要時(shí)間不超過。32第三十二頁(yè)，共六十頁(yè)。
324.6最小生成樹設(shè)G=(V,E)是無(wú)向連通帶權(quán)圖，即一個(gè)網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果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ì)的方案。33第三十三頁(yè)，共六十頁(yè)。
334.6最小生成樹1、最小生成樹性質(zhì)用貪心算法設(shè)計(jì)策略可以設(shè)計(jì)出構(gòu)造最小生成樹的有效算法。本節(jié)介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計(jì)策略的例子。盡管這2個(gè)算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)：設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)?E，且u?U，v?V-U，且在所有這樣的邊中，(u,v)的權(quán)c[u][v]最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個(gè)性質(zhì)有時(shí)也稱為MST性質(zhì)。34第三十四頁(yè)，共六十頁(yè)。
344.6最小生成樹2、Prim算法設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件i?S，j?V-S，且c[i][j]最小的邊，將頂點(diǎn)j添加到S中。這個(gè)過程一直進(jìn)行到S=V時(shí)為止。在這個(gè)過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。35第三十五頁(yè)，共六十頁(yè)。
354.6最小生成樹利用最小生成樹性質(zhì)和數(shù)學(xué)歸納法容易證明，上述算法中的邊集合T始終包含G的某棵最小生成樹中的邊。因此，在算法結(jié)束時(shí)，T中的所有邊構(gòu)成G的一棵最小生成樹。例如，對(duì)于右圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁(yè)圖所示。36第三十六頁(yè)，共六十頁(yè)。
364.6最小生成樹37第三十七頁(yè)，共六十頁(yè)。
374.6最小生成樹在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件i?S,j?V-S，且權(quán)c[i][j]最小的邊(i,j)。實(shí)現(xiàn)這個(gè)目的的較簡(jiǎn)單的辦法是設(shè)置2個(gè)數(shù)組closest和lowcost。在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點(diǎn)j，然后根據(jù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對(duì)closest和lowcost作必要的修改。用這個(gè)辦法實(shí)現(xiàn)的Prim算法所需的計(jì)算時(shí)間為38第三十八頁(yè)，共六十頁(yè)。
384.6最小生成樹3、Kruskal算法Kruskal算法構(gòu)造G的最小生成樹的基本思想是，首先將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í)為止。39第三十九頁(yè)，共六十頁(yè)。
394.6最小生成樹例如，對(duì)前面的連通帶權(quán)圖，按Kruskal算法順序得到的最小生成樹上的邊如下圖所示。40第四十頁(yè)，共六十頁(yè)。
404.6最小生成樹關(guān)于集合的一些基本運(yùn)算可用于實(shí)現(xiàn)Kruskal算法。按權(quán)的遞增順序查看等價(jià)于對(duì)優(yōu)先隊(duì)列執(zhí)行removeMin運(yùn)算?？梢杂枚褜?shí)現(xiàn)這個(gè)優(yōu)先隊(duì)列。對(duì)一個(gè)由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類型并查集UnionFind所支持的基本運(yùn)算。當(dāng)圖的邊數(shù)為e時(shí)，Kruskal算法所需的計(jì)算時(shí)間是。當(dāng)時(shí)，Kruskal算法比Prim算法差，但當(dāng)時(shí)，Kruskal算法卻比Prim算法好得多。41第四十一頁(yè)，共六十頁(yè)。
414.7多機(jī)調(diào)度問題多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個(gè)作業(yè)在盡可能短的時(shí)間內(nèi)由m臺(tái)機(jī)器加工處理完成。這個(gè)問題是NP完全問題，到目前為止還沒有有效的解法。對(duì)于這一類問題,用貪心選擇策略有時(shí)可以設(shè)計(jì)出較好的近似算法。約定，每個(gè)作業(yè)均可在任何一臺(tái)機(jī)器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。42第四十二頁(yè)，共六十頁(yè)。
424.7多機(jī)調(diào)度問題采用最長(zhǎng)處理時(shí)間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計(jì)出解多機(jī)調(diào)度問題的較好的近似算法。按此策略，當(dāng)時(shí)，只要將機(jī)器i的[0,ti]時(shí)間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時(shí)間。當(dāng)時(shí)，首先將n個(gè)作業(yè)依其所需的處理時(shí)間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機(jī)。算法所需的計(jì)算時(shí)間為O(nlogn)。43第四十三頁(yè)，共六十頁(yè)。
434.7多機(jī)調(diào)度問題例如，設(shè)7個(gè)獨(dú)立作業(yè){1,2,3,4,5,6,7}由3臺(tái)機(jī)器M1，M2和M3加工處理。各作業(yè)所需的處理時(shí)間分別為{2,14,4,16,6,5,3}。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時(shí)間為17。44第四十四頁(yè)，共六十頁(yè)。
444.8貪心算法的理論基礎(chǔ)借助于擬陣工具，可建立關(guān)于貪心算法的較一般的理論。這個(gè)理論對(duì)確定何時(shí)使用貪心算法可以得到問題的整體最優(yōu)解十分有用。1、擬陣擬陣M定義為滿足下面3個(gè)條件的有序?qū)?S,I)：(1)S是非空有限集。(2)I是S的一類具有遺傳性質(zhì)的獨(dú)立子集族，即若B?I，則B是S的獨(dú)立子集，且B的任意子集也都是S的獨(dú)立子集?？占?必為I的成員。(3)I滿足交換性質(zhì)，即若A?I,B?I且|A|<|B|，則存在某一元素x?B-A，使得A∪{x}?I。45第四十五頁(yè)，共六十頁(yè)。
454.8貪心算法的理論基礎(chǔ)例如，設(shè)S是一給定矩陣中行向量的集合，I是S的線性獨(dú)立子集族，則由線性空間理論容易證明(S,I)是一擬陣。擬陣的另一個(gè)例子是無(wú)向圖G=(V,E)的圖擬陣。給定擬陣M=(S,I)，對(duì)于I中的獨(dú)立子集A?I，若S有一元素x?A，使得將x加入A后仍保持獨(dú)立性，即A∪{x}?I,則稱x為A的可擴(kuò)展元素。當(dāng)擬陣M中的獨(dú)立子集A沒有可擴(kuò)展元素時(shí)，稱A為極大獨(dú)立子集。46第四十六頁(yè)，共六十頁(yè)。
464.8貪心算法的理論基礎(chǔ)下面的關(guān)于極大獨(dú)立子集的性質(zhì)是很有用的。定理4.1：擬陣M中所有極大獨(dú)立子集大小相同。這個(gè)定理可以用反證法證明。若對(duì)擬陣M=(S,I)中的S指定權(quán)函數(shù)W，使得對(duì)于任意x?S，有W(x)>0，則稱擬陣M為帶權(quán)擬陣。依此權(quán)函數(shù)，S的任一子集A的權(quán)定義為。2、關(guān)于帶權(quán)擬陣的貪心算法許多可以用貪心算法求解的問題可以表示為求帶權(quán)擬陣的最大權(quán)獨(dú)立子集問題。47第四十七頁(yè)，共六十頁(yè)。
474.8貪心算法的理論基礎(chǔ)給定帶權(quán)擬陣M=(S,I)，確定S的獨(dú)立子集A?I使得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)計(jì)算后輸出M的最優(yōu)子集A。48第四十八頁(yè)，共六十頁(yè)。
484.8貪心算法的理論基礎(chǔ)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}49第四十九頁(yè)，共六十頁(yè)。
494.8貪心算法的理論基礎(chǔ)算法greedy的計(jì)算時(shí)間復(fù)雜性為。引理4.2(擬陣的貪心選擇性質(zhì))設(shè)M=(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，且S中元素依權(quán)值從大到小排列。又設(shè)x?S是S中第一個(gè)使得{x}是獨(dú)立子集的元素，則存在S的最優(yōu)子集A使得x?A。算法greedy在以貪心選擇構(gòu)造最優(yōu)子集A時(shí)，首次選入集合A中的元素x是單元素獨(dú)立集中具有最大權(quán)的元素。此時(shí)可能已經(jīng)舍棄了S中部分元素?？梢宰C明這些被舍棄的元素不可能用于構(gòu)造最優(yōu)子集。50第五十頁(yè)，共六十頁(yè)。
504.8貪心算法的理論基礎(chǔ)引理4.3：設(shè)M=(S,I)是擬陣。若S中元素x不是空集?的可擴(kuò)展元素，則x也不可能是S中任一獨(dú)立子集A的可擴(kuò)展元素。引理4.4(擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì))設(shè)x是求帶權(quán)擬陣M＝(S，I)的最優(yōu)子集的貪心算法greedy所選擇的S中的第一個(gè)元素。那么，原問題可簡(jiǎn)化為求帶權(quán)擬陣M’=(S’,I’)的最優(yōu)子集問題，其中：S’={y|y?S且{x,y}?I}I’={B|B?S-{x}且B∪{x}?I}M’的權(quán)函數(shù)是M的權(quán)函數(shù)在S’上的限制(稱M’為M關(guān)于元素x的收縮)。51第五十一頁(yè)，共六十頁(yè)。
514.8貪心算法的理論基礎(chǔ)定理4.5(帶權(quán)擬陣貪心算法的正確性)設(shè)M＝(S,I)是具有權(quán)函數(shù)W的帶權(quán)擬陣，算法greedy返回M的最優(yōu)子集。3、任務(wù)時(shí)間表問題給定一個(gè)單位時(shí)間任務(wù)的有限集S。關(guān)于S的一個(gè)時(shí)間表用于描述S中單位時(shí)間任務(wù)的執(zhí)行次序。時(shí)間表中第1個(gè)任務(wù)從時(shí)間0開始執(zhí)行直至?xí)r間1結(jié)束，第2個(gè)任務(wù)從時(shí)間1開始執(zhí)行至?xí)r間2結(jié)束，…，第n個(gè)任務(wù)從時(shí)間n-1開始執(zhí)行直至?xí)r間n結(jié)束。52第五十二頁(yè)，共六十頁(yè)。
524.8貪心算法的理論基礎(chǔ)具有截止時(shí)間和誤時(shí)懲罰的單位時(shí)間任務(wù)時(shí)間表問題可描述如下。(1)n個(gè)單位時(shí)間任務(wù)的集合S={1,2,…,n}；(2)任務(wù)i的截止時(shí)間,1≤i≤n,1≤≤n，即要求任務(wù)i在時(shí)間之前結(jié)束；(3)任務(wù)i的誤時(shí)懲罰,1≤i≤n,即任務(wù)i未在時(shí)間之前結(jié)束將招致的懲罰；若按時(shí)完成則無(wú)懲罰。任務(wù)時(shí)間表問題要求確定S的一個(gè)時(shí)間表（最優(yōu)時(shí)間表）使得總誤時(shí)懲罰達(dá)到最小。53第五十三頁(yè)，共六十頁(yè)。
534.8貪心算法的理論基礎(chǔ)這個(gè)問題看上去很復(fù)雜，然而借助于擬陣，可以用帶權(quán)擬陣的貪心算法有效求解。對(duì)于一個(gè)給定的S的時(shí)間表，在截止時(shí)間之前完成的任務(wù)稱為及時(shí)任務(wù)，在截止時(shí)間之后完成的任務(wù)稱為誤時(shí)任務(wù)。S的任一時(shí)間表可以調(diào)整成及時(shí)優(yōu)先形式，即其中所有及時(shí)任務(wù)先于誤時(shí)任務(wù)，而不影響原時(shí)間表中各任務(wù)的及時(shí)或誤時(shí)性質(zhì)。類似地，還可將S的任一時(shí)間表調(diào)整成為規(guī)范形式，其中及時(shí)任務(wù)先于誤時(shí)任務(wù)，且及時(shí)任務(wù)依其截止時(shí)間的非減序排列。54第五十四頁(yè)，共六十頁(yè)。
544.8貪心算法的理論基礎(chǔ)首先可將時(shí)間表調(diào)整為及時(shí)優(yōu)先形式，然后再進(jìn)一步調(diào)整及時(shí)任務(wù)的次序。任務(wù)時(shí)間表問題等價(jià)于確定最優(yōu)時(shí)間表中及時(shí)任務(wù)子集A的問題。一旦確定了及時(shí)任務(wù)子集A，將A中各任務(wù)依其截止時(shí)間的非減序列出，然后再以任意次序列出誤時(shí)任務(wù)，即S-A中各任務(wù)，由此產(chǎn)生S的一個(gè)規(guī)范的最優(yōu)時(shí)間表。對(duì)時(shí)間t=1,2,…,n，設(shè)(A)是任務(wù)子集A中所有截止時(shí)間是t或更早的任務(wù)數(shù)?？疾烊蝿?wù)子集A的獨(dú)立性。55第五十五頁(yè)，共六十頁(yè)。
554.8貪心算法的理論基礎(chǔ)引理4.6：對(duì)于S的任一任務(wù)子集A，下面的各命題是等價(jià)的。(1)任務(wù)子集A是獨(dú)立子集。(2)對(duì)于t=1,2,…,n，(A)≤t。(3)若A中任務(wù)依其截止時(shí)間非減序排列，則A中所有任務(wù)都是及時(shí)的。任務(wù)時(shí)間表問題要求使總誤時(shí)懲罰達(dá)到最小，這等價(jià)于使任務(wù)時(shí)間表中的及時(shí)任務(wù)的懲罰值之和達(dá)到最大。下面的定理表明可用帶權(quán)擬陣的貪心算法解任務(wù)時(shí)間表問題。56第五十六頁(yè)，共六十頁(yè)。
564.8貪心算法的理論基礎(chǔ)定理4.7：設(shè)S是帶有截止時(shí)間的單位時(shí)間任務(wù)集，I是S的所有獨(dú)立任務(wù)子集構(gòu)成的集合。則有序?qū)?S,I)是擬陣。由定理4.5可知，用帶權(quán)擬陣的貪心算法可以求得最大權(quán)(懲罰)獨(dú)立任務(wù)子集A，以A作為最優(yōu)時(shí)間表中的及時(shí)任務(wù)子集，容易構(gòu)造最優(yōu)時(shí)間表。任務(wù)時(shí)間表問題的貪心算法的計(jì)算時(shí)間復(fù)雜性是。其中f(n)是用于檢測(cè)任務(wù)子集A的獨(dú)立性所需的時(shí)間。用引理4.6中性質(zhì)(2)容易設(shè)計(jì)一個(gè)時(shí)間算法來檢測(cè)任務(wù)子集的獨(dú)立性。因此，整個(gè)算法的計(jì)算時(shí)間為。具體算法greedyJob可描述如P130。57第五十七頁(yè)，共六十頁(yè)。
574.8貪心算法的理論基礎(chǔ)用抽象數(shù)據(jù)類型并查集UnionFind可對(duì)上述算法作進(jìn)一步改進(jìn)。如果不計(jì)預(yù)處理的時(shí)間，改進(jìn)后的算法fasterJob所需的計(jì)算時(shí)間為。58第五十八頁(yè)，共六十頁(yè)。
58課后作業(yè)習(xí)題4-1，4-4，4-24，4-25，4-26，4-27，4-28，4-31，4-3259第五十九頁(yè)，共六十頁(yè)。
59內(nèi)容總結(jié)第4章貪心算法。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。其基本思想是，設(shè)置頂點(diǎn)集合S并不斷地作貪心選擇來擴(kuò)充這個(gè)集合。一個(gè)頂點(diǎn)屬于集合S當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知。作業(yè)不能拆分成更小的子作業(yè)。將S中元素依權(quán)值W（大者優(yōu)先）組成優(yōu)先隊(duì)列。任務(wù)時(shí)間表問題要求確定S的一個(gè)時(shí)間表（最優(yōu)時(shí)間表）使得總誤時(shí)懲罰達(dá)到最小第六十頁(yè)，共六十頁(yè)。
