【正文】 3 { 1,2 , 3,4} 3 10 50 30 60 4 {1,2 , 3,4 ,5} 5 10 50 30 601) v1 ? v2: 10 2) v1 ? v3: 50 3) v1 ? v4: 30 4) v1 ? v5: 60 ? 10 ? 30 100? ? 50 ? ?? ? ? ? 10? ? 20 ? 60? ? ? ? ?算法設(shè)計(jì)與分析 貪心算法 voidDijkstra(int n, int v,Type dist[], int prev[], Type **c) { bool s[maxint]； for (int i=1。 ? 如果長度改變了，則它必定是由一條從 v0開始，經(jīng)過 u然后到 w的更短路徑所造成的。 算法設(shè)計(jì)與分析 貪心算法 產(chǎn)生最短路徑的貪心方法 ? 選出了結(jié)點(diǎn) u并生成了從 v0到 u的最短路徑之后，結(jié)點(diǎn) u就成為 S中的一個(gè)成員。 ? 擴(kuò)張 S的過程：對(duì)于不在 S中的結(jié)點(diǎn) w，設(shè) DIST(w)是從 v0開始只經(jīng)過 S中的結(jié)點(diǎn)而在結(jié)點(diǎn) w結(jié)束的那條最短路徑的長度，則有 ： – 如果下一條最短路徑是到結(jié)點(diǎn) u，則這條路徑是從 v0處開始而在 u處終止，并且只通過那些在 S中的結(jié)點(diǎn)。 ? 生成從 v0到所有其它結(jié)點(diǎn)的最短路徑的貪心方法就是 按照路徑長度的非降次序生成這些路徑 。 ? 為了使這一量度達(dá)到最小，其單獨(dú)的每一條路徑都必須具有最小長度。 算法設(shè)計(jì)與分析 貪心算法 算法思路 (Dijkstra) :設(shè)最短路長已知的終點(diǎn)集合為 S,初始時(shí) v0?S, 其最短路長為 0,然后用 貪心選擇 逐步擴(kuò)充 S :每次在 VS中 ,選擇 路徑長度值最小的一條最短路徑 的 終點(diǎn) x加入 S. 例 題 構(gòu)造路長最短的最短路徑 :設(shè)已構(gòu)造 i條最短路徑 ,則下一個(gè)加入 S的終點(diǎn) u必是 VS中具有最小路徑長度的終點(diǎn) , 其長度或者是弧 (v0,u), 或者是中間只經(jīng)過 S中的頂點(diǎn)而最后到達(dá)頂點(diǎn) u的路徑 . 例 題 已知一個(gè) n 結(jié)點(diǎn)的有向圖 G=(V,E)和邊的權(quán)函數(shù)c(e)， 求由 G中某指定結(jié)點(diǎn) v0到其他各個(gè)結(jié)點(diǎn)的最短路徑 。也是最優(yōu)樹。 最優(yōu)子結(jié)構(gòu) : 設(shè) T為帶權(quán) w1≤w2≤... ≤wt的最優(yōu)樹 ,若將以帶權(quán)w1和 w2的樹葉為兒子的分枝點(diǎn)改為帶權(quán) w1+w2的樹葉 ,得到一棵新樹 T39。初始化優(yōu)先隊(duì)列需要 O(n)計(jì)算時(shí)間，由于最小堆的removeMin和 put運(yùn)算均需 O(logn)時(shí)間， n－ 1次的合并總共需要 O(nlogn)計(jì)算時(shí)間。經(jīng)過 n－ 1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹 T。 以 f為鍵值的優(yōu)先隊(duì)列 Q用在貪心選擇 時(shí)有效地確定算法當(dāng)前要合并的 2棵具有最小頻率的樹。in。 算法以 |C|個(gè)葉結(jié)點(diǎn)開始，執(zhí)行 |C|－ 1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹 T。 哈夫曼編碼 )()()( cdcfTB TCc???算法思路： 1)以 n個(gè)字母為結(jié)點(diǎn)構(gòu)成 n棵僅含一個(gè)點(diǎn)的二叉樹集合 ,字母的頻率 即為結(jié)點(diǎn)的權(quán)． 2)每次從二叉樹集合中找出兩個(gè)權(quán)最小者合并為一棵二叉樹 :增加一個(gè)根結(jié)點(diǎn)將這兩棵樹作為左右子樹 .新樹的權(quán)為兩棵子樹的權(quán)之和 . 3) 反復(fù)進(jìn)行步驟 2)直到只剩一棵樹為止 . ? 構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為 哈夫曼編碼 。 表示最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹，即樹中任一結(jié)點(diǎn)都有 2個(gè)兒子結(jié)點(diǎn)。 算法設(shè)計(jì)與分析 貪心算法 問題 :通訊過程中需將傳輸?shù)男畔⑥D(zhuǎn)換為二進(jìn)制碼 .由于英文字母使用頻率不同 ,若頻率高的字母對(duì)應(yīng)短的編碼 ,頻率低的字母對(duì)應(yīng)長的編碼 ,傳輸?shù)臄?shù)據(jù)總量就會(huì)降低 .要求找到一個(gè)編碼方案 ,使傳輸?shù)臄?shù)據(jù)量最少 . 見 P109表 41 算法設(shè)計(jì)與分析 貪心算法 前綴碼 為能正確譯碼 ,編碼需采用 前綴碼 , 對(duì)每一個(gè)字符規(guī)定一個(gè) 0,1串作為其代碼，并要求任一字符的代碼都不是其它字符代碼的前綴。 使用貪心算法求解最優(yōu)結(jié)果 。 售貨員希望用數(shù)目最少的硬幣找給小孩 。 當(dāng)然 ， 所裝貨物不能超過車的容量 ， 且同一種物品不得拿走多件 。 規(guī)則規(guī)定從每種貨物中最多只能拿一件 ， 車子的容量為 c， 物品 i 需占用 wi 的空間 ， 價(jià)值為 pi。 思考題 ? 0/1背包問題：在雜貨店比賽中你獲得了第一名 ，獎(jiǎng)品是一車免費(fèi)雜貨 。這正是該問題可用 動(dòng)態(tài)規(guī)劃算法 求解的另一重要特征。事實(shí)上，在考慮 01背包問題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。 為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì) 。 ? } 算法 knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序。 ? c=w[i]。i++) { ? if (w[i]c) break。 ? for (i=1。i++) x[i]=0。 ? for (i=1。 ? 具體算法可描述如下頁： ? void Knapsack(int n,float M,float v[],float w[],float x[]) ? { ? Sort(n,v,w)。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過 C，則選擇單位重量價(jià)值次高的物品并盡可能多地裝入背包。 } if(i= n) x[t[i]] = c/w[t[i]]。 x[t[i]]= 1。i = n。 float c = M。i = n。 //按單位價(jià)值排序 / int i。此結(jié)果為最優(yōu)解。 這種策略下的量度是已裝入物品的累計(jì)效益值與所用容量之比。 即每一次裝入的物品應(yīng)使它占用的每一單位容量獲得當(dāng)前最大的單位效益 。 由剛才的方法可得這種情況下的總效益值為 31， 仍是一個(gè)次優(yōu)解 ， 原因是容量在漫漫消耗的過程中 ， 效益值卻沒有迅速的增加 。 這就要求 按物品重量的非降次序來把物品放入背包 ， 即 (w3,w2,w1)=(10,15,18)。 按上述的數(shù)據(jù)選擇策略 ， 裝入順序是按照物品的效益值從大到小的輸入 ， 由剛才的方法可得這種情況下的總效益值為 ∑ vixi = 25+24*2/15=， 顯然是一個(gè)次優(yōu)解 ， 原因是背包容量消耗過快 。 如上面的實(shí)例所示 ， 可 將物品按效益量非增次序排序： (v1,v2,v3)=(25,24,15)。 可以 選取目標(biāo)函數(shù)為量度標(biāo)準(zhǔn) ， 每裝入一件物品就使背包獲得最大可能的效益值增量 。 ? 算法分析 :算法 loading的主要計(jì)算量在于將集裝箱依其重量從小到大排序，故算法所需的計(jì)算時(shí)間為 O(nlogn)。 ? 最優(yōu)子結(jié)構(gòu)性質(zhì) ? 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 c= w[t[i]]。 w[t[i]] = c。i= n amp。 i ++) x[i] = 0。 //按貨箱重量排序 / for (int i = 1。貨箱 7, 3, 6, 8, 4, 1的 總重量為 390個(gè)單位且已被裝載 , 剩下的裝載能力為 10 ,小于任意 貨箱 .所以得到解 [x1,...x8]=[ 1, 0, 1, 1, 0, 1, 1, 1] 最優(yōu)裝載的貪心算法 算法設(shè)計(jì)與分析 貪心算法 template class Type void Loading(int x[], Type w[], Type c, int n ) { int *t = new int [n + 1]。 [例 ] 設(shè) n=8， [w1， …w 8]=[100, 200, 50, 90, 150, 50, 20, 80]， c=400。 T(n)=O(nlogn) (未排序時(shí) ) [算法分析 ] T(n)=O(n) (排序時(shí) ) [算法證明 ] 算法達(dá)到最優(yōu)解 . [問題描述 ] 輸入 :(x1,x2,...xn), xi=0,貨箱 i不裝船 。當(dāng)輸入的活動(dòng)已按結(jié)束時(shí)間的非減序排列，算法只需 O(n)的時(shí)間安排 n個(gè)活動(dòng)，使最多的活動(dòng)能相容地使用公共資源。也就是說，該算法的貪心選擇的意義是 使剩余的可安排時(shí)間段極大化 ，以便安排盡可能多的相容活動(dòng)。 由于輸入的活動(dòng)以其完成時(shí)間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時(shí)間 的相容活動(dòng)加入集合 A中。圖中每行相應(yīng)于算法的一次迭代。} else A[ i] = false。i+ +) { if (s[i]=f[j]) { A[i] = true。 //從第二個(gè)活動(dòng)開始檢查是否與前一個(gè)相容 for (int i=2。 1 2 3 4 5 6 7 8 9 10 11 [例 ] 1 3 0 5 3 5 6 8 8 2 12 4 5 6 7 8 9 10 11 12 13 14 i s[i] f[i] 設(shè)待安排的 11個(gè)活動(dòng)起止時(shí)間按結(jié)束時(shí)間的非減序排列 最大相容活動(dòng)子集 (1, 4, 8, 11), 也可表示為等長 n元數(shù)組 :(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1) [算法思路 ]將 n個(gè)活動(dòng)按結(jié)束時(shí)間非減序排列 ,依次考慮活動(dòng) i, 若 i與已選擇的活動(dòng)相容 ,則添加此活動(dòng)到相容活動(dòng)子集 . 活動(dòng)安排問題貪心算法 template class Type void GreedySelector(int n, Type s[ ], Type f[ ], bool A[] ) { A[ 1 ] = true。若區(qū)間 [si, fi)與區(qū)間 [sj, fj)不相交，則稱活動(dòng) i與活動(dòng) j是相容的。每個(gè)活動(dòng) i都有一個(gè)要求使用該資源的起始時(shí)間 si和一個(gè)結(jié)束時(shí)間 fi,且 si fi 。貪心算法提供了一個(gè)簡單、漂亮的方法使得盡可能多的活動(dòng)能兼容地使用公共資源。 A(1) A(2) … A(n1) A(n) 某一問題的 n個(gè)輸入 B1(1) B1(2) … B1(m) 該問題的一種解（可行解） 是 A的一 個(gè)子集 滿足一定 的條件 約束條件 Bk(1) Bk(2) … Bk(m) … 目標(biāo)函數(shù) 取極值 最優(yōu)解 算法設(shè)計(jì)與分析 貪心算法 算法設(shè)計(jì)與分析 貪心算法 活動(dòng)安排問題就是要在所給的活動(dòng)集合中選出最大的相容活動(dòng)子集合，是可以用貪心算法有效求解的很好例子。然后，用數(shù)學(xué)歸納法證明，通過每一步作貪心選擇，最終可得到問題的一個(gè)整體 最優(yōu)解。 貪心算法通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求解的問題化簡為規(guī)模更小的問題 對(duì)于一個(gè)具體問題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的最優(yōu)解。 目的：用以求解最優(yōu)化問題 將問題的求解過程看作是一系列選擇 ,每次選擇一個(gè)輸入 ,每次選擇都是當(dāng)前狀態(tài)下的最好選擇 (局部最優(yōu)解).每作一次選擇后 ,所求問題會(huì)簡化為一個(gè)規(guī)模更小的子問題 .從而通過每一步的最優(yōu)解逐步達(dá)到整體的最優(yōu)解。如單源最短路經(jīng)問題，最小生成樹問題等。當(dāng)然，希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。第四章 .貪心算法 (Greed method) 例 題 算法設(shè)計(jì)與分析 貪心算法 顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的 局部最優(yōu) 選擇。雖然貪心算法不能對(duì)所有問題都得到整體最優(yōu)解，但對(duì)許多問題它能產(chǎn)生整體最優(yōu)解。在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的很好近似。