【正文】 } 算法描述 Prim算法 設(shè) G=(V,E)是一個連通帶權(quán)圖 , y={l, 2, …, n} 。 生成樹各邊權(quán)的總和稱為該生成樹的耗費(fèi)。 } dist[v]=0； s[v]=true； for (int i=1。 – 所生成的下一條路徑的終點(diǎn) u必定是所有不在 S內(nèi)的結(jié)點(diǎn)中具有最小距離 DIST(u)的結(jié)點(diǎn)。 貪心選擇性 : 設(shè) T為帶權(quán) w1≤w2≤... ≤wt的最優(yōu)樹 , a).帶權(quán) w1和 w2的樹葉 vw1和 vw2是兄弟 . b).以 vw1和 vw2為兒子的分枝點(diǎn) ,其通路長度最長 . 算法證明 算法分析 HuffmanTree初始化優(yōu)先隊(duì)列 Q需要 O(n) DeleteMin和 Insert需 O(logn). n1次的合并總共需要 O(nlogn) 所以 n個字符的哈夫曼算法的計(jì)算時間為 O(nlogn) 算法設(shè)計(jì)與分析 貪心算法 哈夫曼編碼 單源最短路徑 問題 : 給定帶權(quán)有向圖 G=(V,E), 其中每條邊的權(quán)是一個非負(fù)實(shí)數(shù) .要計(jì)算從 V的一點(diǎn) v0(源 )到所有其他各頂點(diǎn)的最短路長度 . 路長指路上各邊權(quán)之和。一旦 2棵具有最小頻率的樹合并后，產(chǎn)生一棵新的樹，其頻率為合并的 2棵樹的頻率之和，并將新樹插入優(yōu)先隊(duì)列 Q。 平均碼長定義為： 使平均碼長達(dá)到最小的前綴碼編碼方案稱為給定編碼字符集C的最優(yōu)前綴碼。如何選擇量度標(biāo)準(zhǔn)才能找到最優(yōu)解 ？ 算法設(shè)計(jì)與分析 貪心算法 思考題 找零錢問題：一個小孩買了價(jià)值為 33美分的糖 ，并將 1美元的錢交給售貨員 。由此就導(dǎo)出許多互相重疊的子問題。 ? x[i]=1。 ? int i。i ++) { if (w[t[i]] c) break。 算法設(shè)計(jì)與分析 貪心算法 [算法思路 ]1).將各物體按單位價(jià)值由高到低排序 . 2).取價(jià)值最高者放入背包 . 3).計(jì)算背包剩余空間 . 4).在剩余物體中取價(jià)值最高者放入背包 . 若背包剩余容量 =0或物體全部裝入背包為止 [例 ] n=3,c=20 (v1,v2,v3)=(25,24,15),(w1,w2,w3)=(18,15,10) ??ni iixw1??ni iixv1{x1,x2,x3} { 0,2/3,1} {0,1,1/2} {...} {1,2/15,0} 20 20 20 31 ... ... 算法設(shè)計(jì)與分析 貪心算法 void Knapsack(int n,float M,float v[ ],float w[ ] ,float x[ ]) { Sort(n, v, w,t)。 先裝入物品 3, x3=1, p3x3 =15，再裝入重量為 10的物品 2， ∑ vixi =15+24*10/15=31。 [最優(yōu)化描述 ] 找一個 n元 向量 (x1,…x n) 0? xi ?1 使得 且 .其中 C, Wi, vi0 , 1 ? i ? n 44 背包問題 (Knapsack Problem) cxwniii ???1??niii xv1m ax[問題描述 ]設(shè)有 n個物體和一個背包 ,物體 i的重量為 wi ,價(jià)值為 vi ,背包的容量為 i的 xi部分 (1?i?n, 0?xi?1)裝入背包 ,則具有價(jià)值為 vi xi. 目標(biāo)是找到一個方案 ,使放入背包的物體總價(jià)值最高 . 約 束 條 件 優(yōu)化函 數(shù) 算法設(shè)計(jì)與分析 貪心算法 背包問題實(shí)例 ? 考慮下列情況的背包問題 – n=3,M=20,(v1,v2,v3)=(25,24,15), (w1,w2,w3)=(18,15,10) – 其中的 4個可行解是： (x1,x2,x3) ∑ wi xi ∑ vixi ① (1/2,1/3,1/4) ② (1,2/15,0) 20 ③ (0,2/3,1) 20 31 ④ (0,1,1/2) 20 算法設(shè)計(jì)與分析 貪心算法 貪心方法的數(shù)據(jù)選擇策略 (1) 用貪心策略求解背包問題時 ， 首先要選出最優(yōu)的度量標(biāo)準(zhǔn) 。amp。 所考察貨箱的次序?yàn)? :7, 3, 6, 8, 4, 1, 5, 2。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。i =n。 [問題陳述 ]設(shè)有 n個活動的集合 E={1,2,… ,n}，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。 基本思想 [算法優(yōu)點(diǎn) ]求解速度快 ,時間復(fù)雜性有較低的階 . [算法缺點(diǎn) ]需證明是最優(yōu)解 . [常見應(yīng)用 ] 背包問題 ,最小生成樹 ,最短路徑 ,作業(yè)調(diào)度等等 [適用問題 ] 具備 貪心選擇 和 最優(yōu)子結(jié)構(gòu) 性質(zhì)的最優(yōu)化問題 貪心選擇 性質(zhì)： 整體的最優(yōu)解可通過一系列局部最優(yōu)解達(dá)到，即貪心選擇到達(dá)。第四章 .貪心算法 (Greed method) 例 題 算法設(shè)計(jì)與分析 貪心算法 顧名思義，貪心算法總是作出在當(dāng)前看來最好的選擇。 貪心算法通常以自頂向下的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每做一次貪心選擇就將所求解的問題化簡為規(guī)模更小的問題 對于一個具體問題，要確定它是否具有貪心選擇的性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的最優(yōu)解。每個活動 i都有一個要求使用該資源的起始時間 si和一個結(jié)束時間 fi,且 si fi 。i+ +) { if (s[i]=f[j]) { A[i] = true。也就是說，該算法的貪心選擇的意義是 使剩余的可安排時間段極大化 ，以便安排盡可能多的相容活動。貨箱 7, 3, 6, 8, 4, 1的 總重量為 390個單位且已被裝載 , 剩下的裝載能力為 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]。 w[t[i]] = c。 可以 選取目標(biāo)函數(shù)為量度標(biāo)準(zhǔn) ， 每裝入一件物品就使背包獲得最大可能的效益值增量 。 由剛才的方法可得這種情況下的總效益值為 31， 仍是一個次優(yōu)解 ， 原因是容量在漫漫消耗的過程中 ， 效益值卻沒有迅速的增加 。 //按單位價(jià)值排序 / int i。 x[t[i]]= 1。 ? for (i=1。 ? c=w[i]。這正是該問題可用 動態(tài)規(guī)劃算法 求解的另一重要特征。 售貨員希望用數(shù)目最少的硬幣找給小孩 。 哈夫曼編碼 )()()( cdcfTB TCc???算法思路： 1)以 n個字母為結(jié)點(diǎn)構(gòu)成 n棵僅含一個點(diǎn)的二叉樹集合 ,字母的頻率 即為結(jié)點(diǎn)的權(quán)． 2)每次從二叉樹集合中找出兩個權(quán)最小者合并為一棵二叉樹 :增加一個根結(jié)點(diǎn)將這兩棵樹作為左右子樹 .新樹的權(quán)為兩棵子樹的權(quán)之和 . 3) 反復(fù)進(jìn)行步驟 2)直到只剩一棵樹為止 . ? 構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為 哈夫曼編碼 。經(jīng)過 n－ 1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹，即所要求的樹 T。 算法設(shè)計(jì)與分析 貪心算法 算法思路 (Dijkstra) :設(shè)最短路長已知的終點(diǎn)集合為 S,初始時 v0?S, 其最短路長為 0,然后用 貪心選擇 逐步擴(kuò)充 S :每次在 VS中 ,選擇 路徑長度值最小的一條最短路徑 的 終點(diǎn) x加入 S. 例 題 構(gòu)造路長最短的最短路徑 :設(shè)已構(gòu)造 i條最短路徑 ,則下一個加入 S的終點(diǎn) u必是 VS中具有最小路徑長度的終點(diǎn) , 其長度或者是弧 (v0,u), 或者是中間只經(jīng)過 S中的頂點(diǎn)而最后到達(dá)頂點(diǎn) u的路徑 . 例 題 已知一個 n 結(jié)點(diǎn)的有向圖 G=(V,E)和邊的權(quán)函數(shù)c(e)， 求由 G中某指定結(jié)點(diǎn) v0到其他各個結(jié)點(diǎn)的最短路徑 。 算法設(shè)計(jì)與分析 貪心算法 產(chǎn)生最短路徑的貪心方法 ? 選出了結(jié)點(diǎn) u并生成了從 v0到 u的最短路徑之后，結(jié)點(diǎn) u就成為 S中的一個成員。in； i++){ int temp=maxint； int u= v； for (int j = 1； j=n； j++) if ((!s[j])amp。 在 G的所有生成樹中 ,耗費(fèi)最小的生成樹稱為 G的最小生成樹 . 抽象描述 : 輸入 :任一連通生成子圖 (該子圖的邊集合 ) 可行解 :圖的生成樹 , 優(yōu)化函數(shù) :生成樹的各邊權(quán)值之和 最優(yōu)解 :使優(yōu)化函數(shù)達(dá)到最小的生成樹 . 4. 6 最小生成樹 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 應(yīng)用領(lǐng)域與圖模型 算法思路 : 首先置 S={1}, T= 216。 例 題 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 問題：如何選取滿足條件 i?S, j?VS,且 c[i][j]最小的邊 (i, j), 成了算法難點(diǎn)問題。i= n。 for (int k = 2。 closest[j] end}。 }}} Prim算法 算法分析 : O(n2). 算法設(shè)計(jì)與分析 貪心算法 最小生成樹 算法思路 :首先將 G的 n個頂點(diǎn)看成 n個孤立的連通分支 , 將所有的邊按權(quán)從小到大排序 , 然后從第一條邊開始 , 依邊權(quán)遞增的順序查看每一條邊，并按下述方法連接兩個通分支： 當(dāng)查看到第 k條邊 (v,w)時 , 如果端點(diǎn) u和 w分別是當(dāng)前兩個不同的連通分支 T1, T2中的頂點(diǎn)時 ,就用邊 (u,w)將 TI和 T2連接成一個連通分支，然后繼續(xù)查看第 k+1條邊 。在最小優(yōu)先隊(duì)列（ min priority q u e u e）中，查找操作用來搜索優(yōu)先權(quán)最小的元素，刪除操作用來刪除該元素；對于最大優(yōu)先隊(duì)列（ max priority queue），查找操作用來搜索優(yōu)先權(quán)最大的元素，刪除操作用來刪除該元素。 ) 并查集的數(shù)學(xué)模型 ? 并查集的數(shù)學(xué)模型是若干不相交的動態(tài)集合的集合 S＝{A,B,C,...}，它支持以下的運(yùn)算： ? (1)INITIAL(A,x)：構(gòu)造一個取名為 A的集合，它只包含一個元素 x； ? (2)MERGE(A,B)：將集合 A和 B合并，其結(jié)果取名為 A或B； ? (3)FIND(x)：找出元素 x的所在集合，并返回該集合的名字。 = 2。 U. Union(a, b)。由于 G具有有限棵生成樹，所以它至少具有一棵最小生成樹。由此可知， T具有最小耗費(fèi)。 // tour 紀(jì)錄路線 / 2. cost:=0。 貪心近似算法 : 采用最長處理時間作業(yè)優(yōu)先的貪心策略 : 當(dāng) n≤m時 , 只要將機(jī)器 i的 [0, ti]時間區(qū)間分配給作業(yè) i即可。在機(jī)器 3上，作業(yè) 5在 0～ 6時刻內(nèi)完成，作業(yè) 6在 6～ 8時刻內(nèi)完成，作業(yè) 3在 11～ 1 5時刻內(nèi)完成，作業(yè) 1在 15～ 17時刻內(nèi)完成。 public: operator int( ) const { return avail。 } 多機(jī)調(diào)度問題的 貪心近似算法 多機(jī)調(diào)度問題的 貪心近似算法 templateclass Type void Greedy(Type a[]