【正文】 2023年 2月 26日星期日 上午 1時 37分 53秒 01:37: 1最具挑戰(zhàn)性的挑戰(zhàn)莫過于提升自我。 2023年 2月 26日星期日 1時 37分 53秒 01:37:5326 February 2023 1空山新雨后，天氣晚來秋。 上午 1時 37分 53秒 上午 1時 37分 01:37: 沒有失敗，只有暫時停止成功！。 , February 26, 2023 雨中黃葉樹，燈下白頭人。 任務時間表問題的貪心算法的 計算時間復雜性是 。 (1) 任務子集 A是獨立子集。 S的任一時間表可以調(diào)整成 及時優(yōu)先形式 ，即其中所有及時任務先于誤時任務，而不影響原時間表中各任務的及時或誤時性質(zhì)。 任務時間表問題 給定一個 單位時間任務 的有限集 S。 算法 greedy在以貪心選擇構(gòu)造最優(yōu)子集 A時，首次選入集合 A中的元素 x是單元素獨立集中具有最大權(quán)的元素。 下面給出求 帶權(quán)擬陣最優(yōu)子集 的貪心算法。 若對擬陣 M=(S,I)中的 S指定權(quán)函數(shù) W，使得對于任意x? S，有 W(x)0，則稱擬陣 M為 帶權(quán)擬陣 。 (3)I滿足交換性質(zhì)，即若 A?I,B?I且 |A||B|，則存在某一元素 x?BA，使得 A∪{x} ?I。 mn?mn?42 例 8 多機調(diào)度問題 例如， 設 7個獨立作業(yè) {1,2,3,4,5,6,7}由 3臺機器M1， M2和 M3加工處理。對于這一類問題 ,用 貪心選擇策略 有時可以設計出較好的近似算法。 39 例 7 最小生成樹 關(guān)于 集合的一些基本運算 可用于實現(xiàn) Kruskal算法。 35 例 7 最小生成樹 36 例 7 最小生成樹 在上述 Prim算法中，還應當考慮 如何有效地找出滿足條件 i?S,j?VS，且權(quán) c[i][j]最小的邊 (i,j)。這個性質(zhì)有時也稱為MST性質(zhì) 。生成樹上各邊權(quán)的總和稱為該生成樹的 耗費 。一旦 S包含了所有 V中頂點， dist就記錄了從源到所有其它頂點之間的最短路徑長度。這里路的長度是指路上各邊權(quán)之和。 平均碼長 定義為： 使平均碼長達到最小的前綴碼編碼方案稱為給定編碼字符集 C的 最優(yōu)前綴碼 。 22 例 5 哈夫曼編碼 哈夫曼編碼 是廣泛地用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。 for (int i = 1。 算法描述 最優(yōu)裝載問題可用貪心算法求解。如果所給出的活動未按非減序排列，可以用 O(nlogn)的時間重排。i++) { ? if (s[i]=f[j]) { A[i]=true。也就是說，當 si≥fj 或 sj≥fi 時，活動 i與活動 j相容。這正是該問題可用 動態(tài)規(guī)劃算法 求解的另一重要特征。 ? c=w[i]。 float c=M。 問題 1：對于具有 最優(yōu)子結(jié)構(gòu) 的問題應該選用貪心算法還是動態(tài)規(guī)劃算法求解 ? 問題 2：是否能用動態(tài)規(guī)劃算法求解的問題也能用貪心算法求解 ? 貪心算法與動態(tài)規(guī)劃算法的差異 9 例 2 ? 01背包問題： 給定 n種物品和一個背包。 但是，從許多可以用貪心算法求解的問題中看到這 類問題一般具有 2個重要的性質(zhì)： 貪心選擇性質(zhì) 和 最優(yōu)子結(jié)構(gòu)性質(zhì)。 while (r0) { if (m[i])=r) { r=m[i]。 輸出：各種鈔票數(shù) int n[10]。也就是說貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的 局部最優(yōu) 選擇 。 當然， 希望貪心算法得到的最終結(jié)果也是整體最優(yōu)的。 使得 10 10 Σ n[i]*m[i]=v 且 Σ n[i]最小 。 n[i]++。 6 貪心選擇性質(zhì) 所謂貪心選擇性質(zhì)是 指所求問題的整體最優(yōu)解可以通過一系列局部最優(yōu)的選擇（即貪心選擇）來得到。物品 i的重量是 Wi，其價值為 Vi，背包的容量為 C。 ? for (i=1。 ? } ? if (i=n) x[i]=c / w[i]。 實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解 01背包問題。 14 例 3 活動安排問題 例： 設待安排的 11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下： i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14 15 i 1 2 3 4 5 6 7 8 9 10 11 S[i] 1 3 0 5 3 5 6 8 8 2 12 f[i] 4 5 6 7 8 9 10 11 12 13 14 例 3 活動安排問題 算法 greedySelector 的計算過程 如左圖所示。 j=i。 18 例 3 活動安排問題 若被檢查的活動 i的開始時間 Si小于最近選擇的活動 j的結(jié)束時間 fi，則不選擇活動 i，否則選擇活動 i加入集合A中。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。 i = n w[t[i]] = c。其壓縮率通常在 20%～ 90%之間。 )()()( cdcfTB TCc??? 24 構(gòu)造哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為 哈夫曼編碼 。這個問題通常稱為 單源最短路徑問題 。 28 例 6 單源最短路徑 例如 ，對右圖中的有向圖，應用 Dijkstra算法計算從源頂點 1到其它頂點間最短路徑的過程列在下頁的表中。在 G的所有生成樹中，耗費最小的生成樹稱為 G的 最小生成樹 。 33 例 7 最小生成樹 Prim算法 設 G=(V,E)是連通帶權(quán)圖， V={1,2,?,n} 。實現(xiàn)這個目的的較簡單的辦法是設置 2個數(shù)組 closest和lowcost。 按權(quán)的遞增順序查看等價于對 優(yōu)先隊列 執(zhí)行rem