【正文】 計(jì)算機(jī)算法設(shè)計(jì)與分析 Design and Analysis of Computer Algorithms 第四章 貪心算法 Greedy Algorithm 2021年 11月 12日 2 提綱 一、貪心算法的基本思想 二、活動(dòng)安排問(wèn)題 三、最優(yōu)裝載 四、哈夫曼編碼 五、單源最短路徑 六、最小生成樹(shù) 七、多機(jī)調(diào)度問(wèn)題 2021年 11月 12日 3 提綱 一、貪心算法的基本思想 二、活動(dòng)安排問(wèn)題 三、最優(yōu)裝載 四、哈夫曼編碼 五、單源最短路徑 六、最小生成樹(shù) 七、多機(jī)調(diào)度問(wèn)題 2021年 11月 12日 4 貪心算法總體思想 貪心算法總是作出在當(dāng)前看來(lái)最好的選擇 。 也就是說(shuō)貪心算法并不從整體最優(yōu)考慮 ， 它所作出的選擇只是在某種意義上的 局部最優(yōu) 選擇 。 貪心法在解決問(wèn)題的策略上目光短淺 ， 只根據(jù)當(dāng)前已有的信息就做出選擇 ， 而且一旦做出了選擇 ， 不管將來(lái)有什么結(jié)果 ， 這個(gè)選擇都不會(huì)改變 。 這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（ Optimal Solution） ， 但通常能獲得近似最優(yōu)解 （ NearOptimal Solution） 。 2021年 11月 12日 5 貪心算法總體思想 例：用貪心法求解付款問(wèn)題。 假設(shè)有面值為 5元、 2元、 1元、 5角、 2角、 1角的貨幣，需要找給顧客 4元 6角現(xiàn)金，為使付出的貨幣的數(shù)量最少，首先選出 1張面值不超過(guò) 4元 6角的最大面值的貨幣，即 2元，再選出 1張面值不超過(guò) 2元 6角的最大面值的貨幣，即 2元，再選出 1張面值不超過(guò) 6角的最大面值的貨幣，即 5角，再選出 1張面值不超過(guò) 1角的最大面值的貨幣，即 1角，總共付出 4張貨幣。 2021年 11月 12日 6 假設(shè)有面值為 1分、 5分、 1角 1分的貨幣，需要找給顧客 1角 5分現(xiàn)金， 仍按貪心算法如何？ 2021年 11月 12日 7 貪心算法的基本要素 ?貪心選擇性質(zhì) ?所謂貪心選擇性質(zhì)是指所求問(wèn)題的 整體最優(yōu)解 可以通過(guò)一系列 局部最優(yōu) 的選擇，即 貪心選擇 來(lái)達(dá)到。 ?對(duì)于一個(gè)具體問(wèn)題，要確定它是否具有貪心選擇性質(zhì)， 必須證明 每一步所作的貪心選擇最終導(dǎo)致問(wèn)題的整體最優(yōu)解。 ?最優(yōu)子結(jié)構(gòu)性質(zhì) ?當(dāng)一個(gè)問(wèn)題的最優(yōu)解包含其子問(wèn)題的最優(yōu)解時(shí)，稱此問(wèn)題具有 最優(yōu)子結(jié)構(gòu)性質(zhì)。 2021年 11月 12日 8 貪心算法正確性證明方法 ?證明算法所求解的問(wèn)題具有貪心選擇性； ?證明算法所求解的問(wèn)題具有最優(yōu)子結(jié)構(gòu)； ?證明算法確實(shí)按照貪心選擇性進(jìn)行局部?jī)?yōu)化選擇。 2021年 11月 12日 9 動(dòng)態(tài)規(guī)劃與貪心算法的比較 ?相同點(diǎn)： ?都具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 ?不同點(diǎn)： ?貪心算法具有貪心選擇性質(zhì)； ?動(dòng)態(tài)規(guī)劃算法具有子問(wèn)題重疊性，子問(wèn)題空間?。? ?動(dòng)態(tài)規(guī)劃算法通常以 自底向上 的方式解各子問(wèn)題； ?貪心算法則通常以 自頂向下 的方式進(jìn)行，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問(wèn)題簡(jiǎn)化為規(guī)模更小的子問(wèn)題。 ?可用貪心算法時(shí) ， 動(dòng)態(tài)規(guī)劃方法可能不適用； ?可用動(dòng)態(tài)規(guī)劃方法時(shí)，貪心算法可能不適用。 2021年 11月 12日 10 01背包問(wèn)題和背包問(wèn)題 ? 01背包問(wèn)題： ?給定 n種物品和一個(gè)背包。物品 i的重量是 Wi，價(jià)值為Vi，背包容量為 C。應(yīng)如何選擇裝入背包的物品，使得裝入背包中物品的總價(jià)值最大 ? ?在選擇裝入背包的物品時(shí)，對(duì)每種物品 i只有 2種選擇，即裝入或不裝入。 ?背包問(wèn)題： ?與 01背包問(wèn)題類(lèi)似，所不同的是在選擇物品 i裝入背包時(shí)， 可以選擇物品 i的一部分 ，而不一定要全部裝入背包， 1≤i≤n。 2021年 11月 12日 11 01背包問(wèn)題和背包問(wèn)題 ? 01背包問(wèn)題的定義： ?背包問(wèn)題定義： ??niii xv1m a x這 2類(lèi)問(wèn)題都具有 最優(yōu)子結(jié)構(gòu) 性質(zhì)，極為相似，但背包問(wèn)題可以用貪心算法求解，而 01背包問(wèn)題卻不能用貪心算法求解。 ??niii xv1m a x? ? ? ????????????nixCxwiniii11,01 ????????????)1(101nixCxwiniii2021年 11月 12日 12 1 02 03 05 0( a ) 物 品 規(guī) 格 和 背 包 容 量$ 6 0$ 1 0 0 $ 1 2 0背 包 容 量2 03 0＝ $ 2 2 01 02 0＝ $ 1 6 01 03 0＝ $ 1 8 0( b ) 0 1 背 包 問(wèn) 題 的 選 擇 策 略1 02 02 0＝ $ 2 4 0(c)背 包 問(wèn) 題的 貪 心 選 擇 01背包問(wèn)題和背包問(wèn)題 2021年 11月 12日 13 首先計(jì)算每種物品單位重量的價(jià)值 Vi/Wi，然后，依貪心選擇策略，將盡可能多的 單位重量?jī)r(jià)值最高 的物品裝入背包。若將這種物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品并盡可能多地裝入背包。依此策略一直地進(jìn)行下去，直到背包裝滿為止。 具體算法可描述如下頁(yè)： 用貪心算法解背包問(wèn)題的基本步驟： 2021年 11月 12日 14 void Knapsack(int n,float M,float v[],float w[],float x[]) { Sort(n,v,w)。 int i。 for (i=1。i=n。i++) x[i]=0。 float c=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）。 為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì) 。 01背包問(wèn)題和背包問(wèn)題 背包問(wèn)題的貪心選擇性質(zhì)證明見(jiàn)文獻(xiàn) [王曉東，傅清祥，葉東毅，算法與數(shù)據(jù)結(jié)構(gòu)學(xué)習(xí)指導(dǎo)與習(xí)題解析， P6870。電子工業(yè)出版社，2021.] 2021年 11月 12日 15 對(duì)于 01背包問(wèn)題 ，貪心選擇之所以不能得到最優(yōu)解是因?yàn)樵谶@種情況下，它無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)值降低了。事實(shí)上，在考慮 01背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用 動(dòng)態(tài)規(guī)劃算法 求解的另一重要特征。 實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解 01背包問(wèn)題。 2021年 11月 12日 16 貪心算法的步驟 ?優(yōu)化解的結(jié)構(gòu)分析 ?算法設(shè)計(jì) ?算法復(fù)雜性分析 ?算法正確性證明 2021年 11月 12日 17 提綱 一、貪心算法的基本思想 二、活動(dòng)安排問(wèn)題 三、最優(yōu)裝載 四、哈夫曼編碼 五、單源最短路徑 六、最小生成樹(shù) 七、多機(jī)調(diào)度問(wèn)題 2021年 11月 12日 18 問(wèn)題定義（ An activityarranging problem ） ?活動(dòng) ?設(shè) E={1,2,… ,n}是 n個(gè)活動(dòng)的集合，各個(gè)活動(dòng)使用同一個(gè)資源，資源在同一時(shí)間只能為一個(gè)活動(dòng)使用。 ? 每個(gè)活動(dòng) i有起始時(shí)間 si，終止時(shí)間 fi， si fi ?如果選擇了活動(dòng) i，則它在時(shí)間 [si ， fi)內(nèi)占用資源。 ?相容活動(dòng) ?活動(dòng) i和 j是相容的，若 sj?fi或 si?fj，即 Si fi Sj fj j j i fi Si Sj fi fj i和 j不相容 2021年 11月 12日 19 問(wèn)題定義 ?問(wèn)題定義： ?輸入 ： E={1, 2, … , n}， s=[si] ， f=[fi] ， n?i?1 ?輸出 ： E的最大相容集合 2021年 11月 12日 20 貪心選擇 由于活動(dòng)占用資源的時(shí)間沒(méi)有限制 ， 因此 ， 后一種貪心選擇更為合理 。 貪心法求解活動(dòng)安排問(wèn)題的關(guān)鍵是如何選擇貪心策略，使得按照一定的順序選擇相容活動(dòng)，并能安排盡量多的活動(dòng)。至少有兩種看似合理的貪心策略： （ 1） 最早開(kāi)始 時(shí)間：可以增大資源的利用率。 （ 2） 最早結(jié)束 時(shí)間：可以使下一個(gè)活動(dòng)盡早開(kāi)始。 貪心思想 : 為了選擇最多的相容活動(dòng) ， 每次選 fi最小的活動(dòng) ， 使我們能夠選更多的活動(dòng) 。 2021年 11月 12日 21 1. 將所有活動(dòng)按結(jié)束時(shí)間排序，得到活動(dòng)集合E={e1,e2… en}； 2. 先將 e1選入結(jié)果集合 A中，即 A={e1}； 3. 依次掃描每一個(gè)活動(dòng) ei： 如果 ei的開(kāi)始時(shí)間晚于最后一個(gè)選入 A的活動(dòng) ej的結(jié)束時(shí)間，則將 ei選入 A中，否則放棄 ei； 2021年 11月 12日 22 templateclass Type void GreedySelector(int n, Type s[], Type f[], bool A[]) { A[1]=true。 int j=1。 for (int i=2。i=n。i++) { if (s[i]=f[j]) { A[i]=true。 j=i。 } else A[i]=false。 } } 各活動(dòng)的起始時(shí)間和結(jié)束時(shí)間存儲(chǔ)于數(shù)