第4章貪心算法-預覽頁
【正文】 n)的時間重排。 10 活動安排問題 若被檢查的活動 i的開始時間 Si小于最近選擇的活動 j的結束時間 fi，則不選擇活動 i，否則選擇活動 i加入集合A中。 11 貪心算法的基本要素 本節(jié)著重討論可以用貪心算法求解的問題的一般特征。這是貪心算法可行的第一個基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。問題的最優(yōu)子結構性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關鍵特征。物品 i的重量是 Wi，其價值為 Vi，背包的容量為 C。 這 2類問題都具有 最優(yōu)子結構 性質(zhì)，極為相似，但背包問題可以用貪心算法求解，而 01背包問題卻不能用貪心算法求解。 具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟： 18 貪心算法的基本要素 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w)。i++) x[i]=0。i++) { if (w[i]c) break。 } 算法 knapsack的主要計算時間在于將各種物品依其單位重量的價值從大到小排序。事實上，在考慮 01背包問題時，應比較選擇該物品和不選擇該物品所導致的最終方案，然后再作出最好選擇。 20 最優(yōu)裝載 有一批集裝箱要裝上一艘載重量為 c的輪船。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。 for (int i = 1。 i = n amp。 c = w[t[i]]。 算法 loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。 表示 最優(yōu)前綴碼 的二叉樹總是一棵 完全二叉樹 ，即樹中任一結點都有 2個兒子結點。 算法以 |C|個葉結點開始，執(zhí)行 |C|－ 1次的 “ 合并 ”運算后產(chǎn)生最終所要求的樹 T。經(jīng)過 n－ 1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹 T。 27 哈夫曼編碼 哈夫曼算法的正確性 要證明哈夫曼算法的正確性，只要證明最優(yōu)前綴碼問題具有 貪心選擇性質(zhì) 和 最優(yōu)子結構性質(zhì) 。這里路的長度是指路上各邊權之和。一個頂點屬于集合 S當且僅當從源到該頂點的最短路徑長度已知。一旦 S包含了所有 V中頂點， dist就記錄了從源到所有其它頂點之間的最短路徑長度。算法的其余部分所需要時間不超過 。生成樹上各邊權的總和稱為該生成樹的 耗費 。 34 最小生成樹 最小生成樹性質(zhì) 用貪心算法設計策略可以設計出構造最小生成樹的有效算法。這個性質(zhì)有時也稱為MST性質(zhì) 。 在這個過程中選取到的所有邊恰好構成 G的一棵 最小生成樹 。 37 最小生成樹 38 最小生成樹 在上述 Prim算法中，還應當考慮 如何有效地找出滿足條件 i?S,j?VS，且權 c[i][j]最小的邊 (i,j)。將所有的邊按權從小到大排序。 41 最小生成樹 關于 集合的一些基本運算 可用于實現(xiàn) Kruskal算法。 當圖的邊數(shù)為 e時， Kruskal算法所需的 計算時間是 。對于這一類問題 ,用 貪心選擇策略 有時可以設計出較好的近似算法。 按此策略，當 時，只要將機器 i的 [0, ti]時間區(qū)間分配給作業(yè) i即可，算法只需要 O(1)時間。 mn?mn?44 多機調(diào)度問題 例如， 設 7個獨立作業(yè) {1,2,3,4,5,6,7}由 3臺機器M1， M2和 M3加工處理。這個理論對 確定何時使用貪心算法 可以得到問題的整體最優(yōu)解十分有用。 (3)I滿足交換性質(zhì)，即若 A?I,B?I且 |A||B|，則存在某一元素 x?BA，使得 A∪{x} ?I。 當擬陣 M中的獨立子集 A沒有可擴展元素時，稱 A為 極大獨立子集 。 若對擬陣 M=(S,I)中的 S指定權函數(shù) W，使得對于任意x? S，有 W(x)0，則稱擬陣 M為 帶權擬陣 。這種使 W(A)最大的獨立子集 A稱為擬陣 M的 最優(yōu)子集 。 下面給出求 帶權擬陣最優(yōu)子集 的貪心算法。 if (A∪{x} ?I) A=A∪{x}。 算法 greedy在以貪心選擇構造最優(yōu)子集 A時，首次選入集合 A中的元素 x是單元素獨立集中具有最大權的元素。若 S中元素 x不是空集 的可擴展元素，則 x也不可能是 S中任一獨立子集 A的可擴展元素。 任務時間表問題 給定一個 單位時間任務 的有限集 S。 (1) n個單位時間任務的集合 S={1,2,… ,n}； (2) 任務 i的截止時間 ,1≤i≤n,1≤ ≤n ，即要求任務 i在時間 之前結束； (3) 任務 i的誤時懲罰 ,1≤i≤n, 即任務 i未在時間 之前結束將招致的 懲罰；若按時完成則無懲罰。 S的任一時間表可以調(diào)整成 及時優(yōu)先形式 ，即其中所有及時任務先于誤時任務，而不影響原時間表中各任務的及時或誤時性質(zhì)。一旦確定了及時任務子集 A，將 A中各任務依其截止時間的非減序列出，然后再以任意次序列出誤時任務，即 SA中各任務，由此產(chǎn)生 S的一個規(guī)范的最優(yōu)時間表。 (1) 任務子集 A是獨立子集。下面的 定理 表明可用帶權擬陣的貪心算法解任務時間表問題。 任務時間表問題的貪心算法的 計算時間復雜性是 。具體算法 greedyJob可描述如 P
化學相關推薦
鄂ICP備17016276號-1