【正文】 結(jié)構(gòu)性質(zhì) ? （ 2）貪心選擇性質(zhì) ? 貪心算法與動態(tài)規(guī)劃算法的差異 ? 應(yīng)用范例 ? （ 1）活動安排問題； ? （ 2）最優(yōu)裝載問題； ? （ 3）哈夫曼編碼和數(shù)據(jù)壓縮； ? （ 4）單源最短路徑； ? （ 5）最小生成樹； ? （ 6）多機調(diào)度問題。 在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果卻是最優(yōu)解的近似解。 for(i=0。 } for(i=0。 對于一個具體問題，要確定它是否具有貪心選擇性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)致問題的一個整體最優(yōu)解。 10 用貪心算法解背包問題的基本步驟： 首先計算每種物品單位重量的價值 Vi/Wi，然后，依貪心選擇策略，將盡可能多的 單位重量價值最高的物品裝入背包。i++) x[i]=0。因此，算法的計算時間上界為： O（ nlogn）。該問題要求高效地安排一系列爭用某一公共資源的活動。陰影長條表示的活動是已選入集合 A的活動，而空白長條表示的活動是當(dāng)前正在檢查相容性的活動。 ? } ? } 各活動的起始時間和結(jié)束時間存儲于數(shù)組s和 f中且按結(jié)束時間的非減序排列 17 例 3 活動安排問題 由于輸入的活動以其完成時間的 非減序 排列，所以算法 greedySelector每次總是選擇 具有最早完成時間 的相容活動加入集合 A中。但對于活動安排問題，貪心算法 greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合 A的規(guī)模最大。 20 templateclass Type void Loading(int x[], Type w[], Type c, int n) { int *t = new int [n+1]。 c = w[t[i]]。 給出現(xiàn)頻率高的字符較短的編碼，出現(xiàn)頻率較低的字符以較長的編碼，可以大大縮短總碼長。 算法以 |C|個葉結(jié)點開始，執(zhí)行 |C|－ 1次的“合并”運算后產(chǎn)生最終所要求的樹 T。 27 例 6 單源最短路徑 其 基本思想 是，設(shè)置頂點集合 S并不斷地作 貪心選擇來擴(kuò)充這個集合。這個循環(huán)需要執(zhí)行 n1次，所以完成循環(huán)需要 時間。 例如 ，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊 (v,w)的權(quán)c[v][w]表示建立城市 v和城市 w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟(jì)的方案。這個過程一直進(jìn)行到 S=V時為止。 用這個辦法實現(xiàn)的 Prim算法所需的 計算時間 為 )( 2nO37 例 7 最小生成樹 Kruskal算法 Kruskal算法構(gòu)造 G的最小生成樹的 基本思想 是，首先將 G的 n個頂點看成 n個孤立的連通分支。 對一個由連通分支組成的集合不斷進(jìn)行修改，需要用到抽象數(shù)據(jù)類型 并查集 UnionFind所支持的基本運算。 41 例 7 多機調(diào)度問題 采用 最長處理時間作業(yè)優(yōu)先 的貪心選擇策略可以設(shè)計出解多機調(diào)度問題的較好的近似算法。 43 貪心算法的理論基礎(chǔ) 借助于 擬陣 工具，可建立關(guān)于貪心算法的較一般的理論。 給定擬陣 M=(S,I)，對于 I中的獨立子集 A? I，若 S有一元素 x? A，使得將 x加入 A后仍保持獨立性，即 A∪{x} ? I,則稱 x為 A的 可擴(kuò)展元素 。 ??? Ax xWAW )()(46 貪心算法的理論基礎(chǔ) 給定帶權(quán)擬陣 M=(S,I)，確定 S的獨立子集 A?I使得 W(A)達(dá)到最大。 ? 將 S中元素依權(quán)值 W（大者優(yōu)先）組成優(yōu)先隊列； ? while (S!=?) { ? (x)。 ))(log( nnfnnO ?49 貪心算法的理論基礎(chǔ) 引理 ： 設(shè) M=(S,I)是擬陣。 51 貪心算法的理論基礎(chǔ) 具有 截止時間 和 誤時懲罰 的單位時間任務(wù)時間表問題可描述如下。 任務(wù)時間表問題 等價于 確定最優(yōu)時間表中 及時任務(wù)子集 A的問題。 任務(wù)時間表問題 要求使總誤時懲罰達(dá)到最小，這等價于使任務(wù)時間表中的及時任務(wù)的懲罰值之和達(dá)到最大。因此，整個算法的計算時間 為 。 01:37:5301:37:5301:37Sunday, February 26, 2023 1乍見翻疑夢，相悲各問年。 :37:5301:37Feb2326Feb23 1世間成事，不求其絕對圓滿，留一份不足，可得無限完美。 01:37:5301:37:5301:372/26/2023 1:37:53 AM 1越是沒有本領(lǐng)的就越加自命不凡。 上午 1時 37分 53秒 上午 1時 37分 01:37: MOMODA POWERPOINT Lorem ipsum dolor sit, eleifend nulla ac, fringilla purus. Nulla iaculis tempor felis amet, consectetur adipiscing elit. Fusce id urna blanditut cursus. 感謝您的下載觀看 專家告訴 。 01:37:5301:37:5301:37Sunday, February 26, 2023 1知人者智，自知者明。 :37:5301:37:53February 26, 2023 1意志堅強的人能把世界放在手中像泥塊一樣任意揉捏。 2023年 2月 26日星期日 上午 1時 37分 53秒 01:37: 1比不了得就不比，得不到的就不要。 )( 2nO )(nO ))(log( nnfnn ?56 貪心算法的理論基礎(chǔ) 用抽象數(shù)據(jù)類型并查集 UnionFind可對上述算法作進(jìn)一步改進(jìn)。 tN55 貪心算法的理論基礎(chǔ) 定理 ： 設(shè) S是帶有截止時間的單位時間任務(wù)集， I是 S的所有獨立任務(wù)子集構(gòu)成的集合。 對時間 t=1,2,?,n ， 設(shè) (A)是任務(wù)子集 A中所有截止時間是 t或更早的任務(wù)數(shù)。 任務(wù)時間表問題 要求確定 S的一個時間表（最優(yōu)時間表）使得總誤時懲罰達(dá)到最小。 引理 (擬陣的最優(yōu)子結(jié)構(gòu)性質(zhì) ) 設(shè) x是求帶權(quán)擬陣 M＝ (S， I)的最優(yōu)子集的貪心算法greedy所選擇的 S中的第一個元素。 ? } ? return A ? }