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