貪心算法復(fù)習(xí)進(jìn)程

貪心(tānxīn)算法第一頁，共71頁。顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是(zhǐshì)在某種意義上的局部最優(yōu)選擇。第二頁，共71頁。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。雖然貪心算法不能對所有問題都得到整體最優(yōu)解，但對許多問題它能產(chǎn)生整體最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。在一些情況(qíngkuàng)下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。第三頁，共71頁?；顒影才?ānpái)問題設(shè)有n個活動(huódòng)的集合s={1,2,…,n}，其中每個活動(huódòng)都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動(huódòng)能使用這一資源。si,fi分別為活動(huódòng)i的開始時間和結(jié)束時間，活動(huódòng)i和j相容當(dāng)且僅當(dāng)si>=fj或者sj>=fi第四頁，共71頁。怎樣對這n個活動(huódòng)進(jìn)行安排才能令最多的活動(huódòng)可以使用資源？第五頁，共71頁?；顒影才艈栴}(wèntí)也就是要在所給的活動集合中選出最大的相容活動子集合第六頁，共71頁。第七頁，共71頁。思路：按照結(jié)束時間遞增序列將活動排序，使得f1<=f2<=…<=fn滿足相容關(guān)系后，按照標(biāo)號(biāohào)從小到大選擇活動注意：排序，貪心選擇第八頁，共71頁。第九頁，共71頁。活動安排問題的貪心策略(cèlüè)：使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。第十頁，共71頁。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;}}各活動的起始時間和結(jié)束(jiéshù)時間存儲于數(shù)組s和f中且按結(jié)束(jiéshù)時間的非減序排列活動安排(ānpái)問題的貪心算法第十一頁，共71頁。算法GreedySelector的效率極高。當(dāng)輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排(ānpái)n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。第十二頁，共71頁。貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法GreedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容(xiānɡrónɡ)活動集合A的規(guī)模最大。第十三頁，共71頁。貪心(tānxīn)算法的基本要素最優(yōu)子結(jié)構(gòu)性質(zhì)貪心(tānxīn)選擇性質(zhì)第十四頁，共71頁。最優(yōu)子結(jié)構(gòu)性質(zhì)(xìngzhì)一個問題的最優(yōu)解包含了它子問題的最優(yōu)解。舉例：你從北京(běijīnɡ)經(jīng)過廣州到海南的最短距離，肯定包括北京(běijīnɡ)到廣州的最短距離，以及廣州到海南的最短距離第十五頁，共71頁。貪心選擇(xuǎnzé)性質(zhì)所求問題的最優(yōu)解，可以通過一系列的局部最優(yōu)解的選擇(xuǎnzé)，即貪心選擇(xuǎnzé)得到在當(dāng)前狀態(tài)下做出局部最優(yōu)，然后解這個選擇(xuǎnzé)時候產(chǎn)生的子問題從全局看來，運用貪心策略解決的問題在程序的運行過程中無回溯過程第十六頁，共71頁。0-1背包(bèibāo)問題：給定n種物品和一個背包(bèibāo)。物品i的重量是Wi，其價值為Vi，背包(bèibāo)的容量為C。應(yīng)如何選擇裝入背包(bèibāo)的物品，使得裝入背包(bèibāo)中物品的總價值最大?在選擇(xuǎnzé)裝入背包的物品時，對每種物品i只有2種選擇(xuǎnzé)，即裝入背包或不裝入背包。不能將物品i裝入背包多次，也不能只裝入部分的物品i。第十七頁，共71頁。背包問題： 與0-1背包問題類似，所不同的是在選擇物品(wùpǐn)i裝入背包時，可以選擇物品(wùpǐn)i的一部分，而不一定要全部裝入背包，1≤i≤n。這2類問題都具有最優(yōu)子結(jié)構(gòu)性質(zhì)，極為相似，但背包問題可以(kěyǐ)用貪心算法求解，而0-1背包問題卻不能用貪心算法求解。第十八頁，共71頁。用貪心算法解背包問題的基本(jīběn)步驟首先計算每種物品單位重量的價值Vi/Wi，然后，依貪心選擇策略，將盡可能多的單位重量價值最高的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(chāoguò)C，則選擇單位重量價值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。第十九頁，共71頁。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的主要計算時間(shíjiān)在于將各種物品依其單位重量的價值從大到小排序。因此，算法的計算時間(shíjiān)上界為O（nlogn）。為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)。第二十頁，共71頁。對于0-1背包問題，貪心選擇之所以不能得到最優(yōu)解是因為在這種情況下，它無法保證最終能將背包裝滿，部分(bùfen)閑置的背包空間使每公斤背包空間的價值降低了。第二十一頁，共71頁。特殊的0-1背包(bèibāo)問題在0-1背包問題中，若各物品依重量遞增序排列時，其價值恰好依遞減序排列，對這個特殊的0-1背包問題，設(shè)計(shèjì)一個有效的算法找出最優(yōu)解。第二十二頁，共71頁。對于0－1背包問題本來是無法用貪心算法得到最優(yōu)解的，但對于這類特殊的0－1背包問題，則可以用貪心算法去解。首先將各物品依重量遞增序（即也是價值遞減序）排列，然后依照價值遞減順序選擇物品裝入背包，直到背包裝不下下一件物品為止。這里貪心算法的貪心選擇策略是：每次總是(zǒnɡshì)選擇價值最大（同時重量也最小）的物品，然后檢查是否可以裝入背包。第二十三頁，共71頁。最優(yōu)裝載(zhuāngzài)有一批集裝箱要裝上一艘載重量為c的輪船。其中(qízhōng)集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。第二十四頁，共71頁。算法(suànfǎ)描述最優(yōu)裝載問題可用貪心算法求解貪心選擇(xuǎnzé)策略:重量最輕者先裝可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解第二十五頁，共71頁。template<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]];}}第二十六頁，共71頁。貪心(tānxīn)選擇性質(zhì)可以證明(zhèngmíng)最優(yōu)裝載問題具有貪心選擇性質(zhì)。k=min{i|xi=1} 1=<i<=nk=1,>1第二十七頁，共71頁。最優(yōu)子結(jié)構(gòu)性質(zhì)(xìngzhì)最優(yōu)裝載問題具有(jùyǒu)最優(yōu)子結(jié)構(gòu)性質(zhì)。第二十八頁，共71頁。由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。算法Loading的主要計算量在于將集裝箱依其重量從小到大排序(páixù)，故算法所需的計算時間為O(nlogn)。第二十九頁，共71頁。哈夫曼編碼(biānmǎ)哈夫曼編碼是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常(tōngcháng)在20%～90%之間。哈夫曼編碼算法用字符在文件中出現(xiàn)的頻率表來建立一個用0，1串表示各字符的最優(yōu)表示方式。給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。第三十頁，共71頁。abcdef頻率(千次)4513121695定長碼000001010011100101變長碼010110011111011100第三十一頁，共71頁。前綴(qiánzhuì)碼對每一個字符(zìfú)規(guī)定一個0,1串作為其代碼，并要求任一字符(zìfú)的代碼都不是其它字符(zìfú)代碼的前綴。這種編碼稱為前綴碼。第三十二頁，共71頁。編碼的前綴性質(zhì)可以使譯碼方法非常簡單平均碼長定義(dìngyì)為：使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。表示最優(yōu)前綴碼的二叉樹樹中任一結(jié)點都有2個兒子結(jié)點第三十三頁，共71頁。滿二叉樹(FullBinaryTree)

一棵深度為k且有2k-1個結(jié)點的二又樹稱為滿二叉樹。

滿二叉樹的特點：

（1）每一層上的結(jié)點數(shù)都達(dá)到最大值。即對給定的高度，它是具有最多結(jié)點數(shù)的二叉樹。

（2）滿二叉樹中不存在度數(shù)為1的結(jié)點，每個分支結(jié)點均有兩棵高度相同(xiānɡtónɡ)的子樹，且樹葉都在最下一層上。第三十四頁，共71頁。完全二叉樹(CompleteBinaryTree)

若一棵二叉樹至多只有(zhǐyǒu)最下面的兩層上結(jié)點的度數(shù)可以小于2，并且最下一層上的結(jié)點都集中在該層最左邊的若干位置上，則此二叉樹稱為完全二叉樹。

特點：

（1）滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。

（2）在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去若干結(jié)點后得到的二叉樹仍然是一棵完全二叉樹。

（3）在完全二叉樹中，若某個結(jié)點沒有左孩子，則它一定沒有右孩子，即該結(jié)點必是葉結(jié)點。第三十五頁，共71頁。第三十六頁，共71頁。構(gòu)造(gòuzào)哈夫曼編碼哈夫曼提出構(gòu)造(gòuzào)最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼。哈夫曼算法以自底向上的方式構(gòu)造(gòuzào)表示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結(jié)點開始，執(zhí)行|C|－1次的“合并”運算后產(chǎn)生最終所要求的樹T。第三十七頁，共71頁。算法(suànfǎ)huffmanTree中，編碼字符集中每一字符c的頻率是f(c)。以f為鍵值的優(yōu)先隊列Q用在貪心選擇時有效地確定算法(suànfǎ)當(dāng)前要合并的2棵具有最小頻率的樹。一旦2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的2棵樹的頻率之和，并將新樹插入優(yōu)先隊列Q。經(jīng)過n－1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。第三十八頁，共71頁。算法huffmanTree用最小堆實現(xiàn)優(yōu)先隊列(duìliè)Q。初始化優(yōu)先隊列(duìliè)需要O(n)計算時間，由于最小堆的removeMin和put運算均需O(logn)時間，n－1次的合并總共需要O(nlogn)計算時間。因此，關(guān)于n個字符的哈夫曼算法的計算時間為O(nlogn)。第三十九頁，共71頁。選址(xuǎnzhǐ)問題給定n個小區(qū)之間的交通圖。若小區(qū)i與小區(qū)j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權(quán)值表示這條道路的長度?，F(xiàn)在打算(dǎsuàn)在這n個小區(qū)中選定一個小區(qū)建一所醫(yī)院。試問這家醫(yī)院應(yīng)建在哪個小區(qū)，才能使距離醫(yī)院最遠(yuǎn)的小區(qū)到醫(yī)院的路程最短？請設(shè)計一個算法求解上述問題。第四十頁，共71頁。單源最短路徑(lùjìng) 給定帶權(quán)有向圖G=(V,E)，其中每條邊的權(quán)是非負(fù)實數(shù)。另外，還給定V中的一個頂點(dǐngdiǎn)v，稱為源?，F(xiàn)在要計算從源到所有其它各頂點(dǐngdiǎn)的最短路長度。這里路的長度是指路上各邊權(quán)之和。這個問題通常稱為單源最短路徑問題。第四十一頁，共71頁。單源最短路徑(lùjìng) 1、算法基本思想 Dijkstra算法是解決(jiějué)單源最短路徑問題的貪心算法第四十二頁，共71頁。單源最短路徑(lùjìng) 1、算法(suànfǎ)基本思想 Dijkstra算法(suànfǎ)是解決單源最短路徑問題的貪心算法(suànfǎ)。 其基本思想是，設(shè)置頂點集合S并不斷地作貪心選擇來擴(kuò)充這個集合。一個頂點屬于集合S當(dāng)且僅當(dāng)從源到該頂點的最短路徑長度已知。第四十三頁，共71頁。通過分步方法(fāngfǎ)求出最短路徑,每一步產(chǎn)生一個到達(dá)新的目的頂點的最短路徑下一步所能達(dá)到的目的頂點通過如下貪婪準(zhǔn)則選取：在還未產(chǎn)生最短路徑的頂點中，選擇路徑長度最短的目的頂點第四十四頁，共71頁。單源最短路徑(lùjìng)初始時，S中僅含有源。設(shè)u是G的某一個頂點，把從源到u且中間只經(jīng)過S中頂點的路稱為從源到u的特殊路徑，并用(bìnɡyònɡ)數(shù)組dist記錄當(dāng)前每個頂點所對應(yīng)的最短特殊路徑長度Dijkstra算法每次從V-S中取出具有最短特殊路長度的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改。一旦S包含了所有V中頂點，dist就記錄了從源到所有其它頂點之間的最短路徑長度。第四十五頁，共71頁。迭代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}510503060第四十六頁，共71頁。Dijkstra算法的迭代(diédài)過程迭代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}510503060第四十七頁，共71頁。選址(xuǎnzhǐ)問題給定n個小區(qū)之間的交通圖。若小區(qū)i與小區(qū)j之間有路可通，則將頂點i與頂點j之間用邊連接，邊上的權(quán)值表示這條道路的長度?，F(xiàn)在打算在這n個小區(qū)中選定一個小區(qū)建一所醫(yī)院。試問這家醫(yī)院應(yīng)建在哪個(nǎge)小區(qū)，才能使距離醫(yī)院最遠(yuǎn)的小區(qū)到醫(yī)院的路程最短？請設(shè)計一個算法求解上述問題。第四十八頁，共71頁。將n個小區(qū)的交通圖視為一張帶權(quán)無向圖，并利用鄰接矩陣來存放帶權(quán)無向圖。算法(suànfǎ)的思想是：①應(yīng)用Dijkstra算法(suànfǎ)計算每對頂點之間的最短路徑；②找出從每一個頂點到其它各頂點的最短路徑中最長路徑；③在這n條最長路徑中找出最短的一條，則它的出發(fā)點即為所求。第四十九頁，共71頁。單源最短路徑(lùjìng)2、算法的正確性和計算復(fù)雜性(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)(3)計算復(fù)雜性 對于具有(jùyǒu)n個頂點和e條邊的帶權(quán)有向圖，如果用帶權(quán)鄰接矩陣表示這個圖，那么Dijkstra算法的主循環(huán)體需要時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要時間。算法的其余部分所需要時間不超過。第五十頁，共71頁。如何(rúhé)架設(shè)通信網(wǎng)絡(luò)如下圖G，圖中的6個頂點為某鄉(xiāng)的6個村，圖G的邊代表公路，現(xiàn)在要沿公路架設(shè)電線，使各村之間都通電話，問應(yīng)該怎樣(zěnyàng)架線，才能使所用的電線最少？第五十一頁，共71頁。最小生成(shēnɡchénɡ)樹 設(shè)G=(V,E)是無向連通帶權(quán)圖，即一個網(wǎng)絡(luò)。E中每條邊(v,w)的權(quán)為c[v][w]。如果G的子圖G’是一棵包含G的所有頂點的樹，則稱G’為G的生成樹。生成樹上各邊權(quán)的總和(zǒnghé)稱為該生成樹的耗費。在G的所有生成樹中，耗費最小的生成樹稱為G的最小生成樹。第五十二頁，共71頁。Prim算法(suànfǎ)設(shè)G=(V,E)是連通帶權(quán)圖，V={1,2,…,n}。構(gòu)造G的最小生成樹的Prim算法的基本思想是：首先置S={1}，然后，只要S是V的真子集，就作如下的貪心選擇：選取滿足條件iS，jV-S，且c[i][j]最小的邊，將頂點j添加到S中。這個過程(guòchéng)一直進(jìn)行到S=V時為止。在這個過程(guòchéng)中選取到的所有邊恰好構(gòu)成G的一棵最小生成樹。第五十三頁，共71頁。

例如，對于右圖中的帶權(quán)圖，按Prim算法(suànfǎ)選取邊的過程如下頁圖所示。第五十四頁，共71頁。第五十五頁，共71頁。 在上述Prim算法中，還應(yīng)當(dāng)考慮如何有效地找出滿足條件iS,jV-S，且權(quán)c[i][j]最小的邊(i,j)。實現(xiàn)這個目的的較簡單的辦法是設(shè)置2個數(shù)組closest和lowcost。 在Prim算法執(zhí)行過程中，先找出V-S中使lowcost值最小的頂點j，然后根據(jù)(gēnjù)數(shù)組closest選取邊(j,closest[j］)，最后將j添加到S中，并對closest和lowcost作必要的修改。 用這個辦法實現(xiàn)的Prim算法所需的計算時間為第五十六頁，共71頁。Kruskal算法(suànfǎ) Kruskal算法構(gòu)造G的最小生成樹的基本思想是，首先(shǒuxiān)將G的n個頂點看成n個孤立的連通分支。將所有的邊按權(quán)從小到大排序。

第五十七頁，共71頁。Kruskal算法(suànfǎ)從第一條邊開始，依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接2個不同的連通分支：1、當(dāng)查看到第k條邊(v,w)時，如果端點v和w分別是當(dāng)前2個不同的連通分支T1和T2中的頂點時，就用邊(v,w)將T1和T2連接成一個連通分支，然后繼續(xù)查看第k+1條邊；2、如果端點v和w在當(dāng)前的同一個連通分支中，就直接再查看第k+1條邊。這個過程一直進(jìn)行(jìnxíng)到只剩下一個連通分支時為止。第五十八頁，共71頁。第五十九頁，共71頁。 當(dāng)圖的邊數(shù)為e時，Kruskal算法所需的計算(jìsuàn)時間是。當(dāng)時，Kruskal算法比Prim算法差，但當(dāng)時，Kruskal算法卻比Prim算法好得多。第六十頁，共71頁。多機(jī)調(diào)度(diàodù)問題 多機(jī)調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機(jī)器加工處理完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法(jiěfǎ)。對于這一類問題,用貪心選擇策略有時可以設(shè)計出較好的近似算法。約定，每個作業(yè)均可在任何一臺機(jī)器上加工處理(chǔ