課件算法第八次

15.貪心法解此問題定理16.1（P224）設(shè)Sij是任一非空子問題，am是Sij中具有最早完成時(shí)間的活動(dòng)，即fm=min{fk:ak∈Sij}，則：①活動(dòng)am必定被包含在Sij的某個(gè)最優(yōu)解中②子問題Sim是空集，使得Smj是唯一可能的非空集2定理16.1的簡化作用①分解Sij：二個(gè)子問題簡化為一個(gè)子問題Smj②j-i-1種選擇簡化為一種選擇：選Sij中具有最早完成時(shí)間的活動(dòng)由定理16.1的簡化作用使得求解問題可以采用自頂向下的方法設(shè)計(jì)算法:①從原問題S0,n+1中選最早完成時(shí)間的活動(dòng)am1=a1②從Sm1,n+1中選最早完成時(shí)間的活動(dòng)am2③……3Recursive-Activity-Selector(s,f,i,j) mi+1 whilem<jandsm<fi//在Sij中找第一個(gè)與 domm+1//ai相容的活動(dòng)

ifm<j//sm≥fi，找到相容的活動(dòng)am thenreturn{am}∪Recursive-Activity-Selector(s,f,m,j)elsereturnΦ算法執(zhí)行過程如圖16.1。算法分析：用O(nlgn)的排序算法使f按遞增序排列

∵算法依次從n+2個(gè)活動(dòng)中挑選一個(gè)活動(dòng) ∴遞歸調(diào)用+while循環(huán)的次數(shù)=O(n)

∴算法總時(shí)間為O(nlgn)47.3貪心法應(yīng)用注意事項(xiàng)1.應(yīng)用貪心法的幾項(xiàng)工作①確定問題的最優(yōu)子結(jié)構(gòu)性質(zhì)②將優(yōu)化問題轉(zhuǎn)化為作出一種選擇，即貪心選擇③貪心選擇后應(yīng)只留下一個(gè)子問題，其它子問題均為空④證明貪心選擇的正確性，即本次貪心選擇與剩余子問題的最優(yōu)解可以構(gòu)成原問題的最優(yōu)解例：從3種硬幣11，5，1中選出15分的最少硬幣數(shù)。

52.貪心選擇性質(zhì) 貪心選擇性質(zhì)是應(yīng)用貪心法求解的一個(gè)必要條件。所謂選擇性質(zhì)是指所求問題的最優(yōu)解可以通過一系列局部最優(yōu)的貪心選擇而得到。即：局部最優(yōu)＝>全局最優(yōu) 貪心選擇性質(zhì)是區(qū)別與動(dòng)態(tài)規(guī)劃方法的一個(gè)重要特征，因?yàn)樨澬姆ㄔ谧鞒鲞x擇時(shí)并不依賴于將來的情況，只需根據(jù)當(dāng)前的情況即可作出選擇。3.最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)也是應(yīng)用貪心法求解的一個(gè)必要條件。局部最優(yōu)+一系列貪心選擇產(chǎn)生原問題的一個(gè)最優(yōu)解。64.貪心法與動(dòng)態(tài)規(guī)劃方法比較①貪心法效率更高，表現(xiàn)在子問題不需要都計(jì)算，而選擇數(shù)為1。②動(dòng)態(tài)規(guī)劃方法的應(yīng)用面更廣，問題只需具有最優(yōu)子結(jié)構(gòu)即可，而貪心法不僅需要具有最優(yōu)子結(jié)構(gòu)性質(zhì)，還需要具有貪心選擇性質(zhì)。例如：背包問題 給定n個(gè)物品和一個(gè)背包，物品i的重量為wi,其價(jià)值為vi,背包可裝載的總重量為W。問題是如何選擇裝入背包的物品，使得物品的總價(jià)值最大？0/1背包(0-1knapsack):物品不能拆分零頭背包(fractionalknapsack)：物品可以拆分見書P230圖16.277.4Huffman編碼例如:一個(gè)包含100,000個(gè)字符的數(shù)據(jù)文件進(jìn)行壓縮存儲(chǔ)，編碼方式為： a b c d e f頻度(千次)4513121695等長碼000001010011100101變長碼010110011111011100編碼后文件的二進(jìn)位總長為：等長碼：100,000×3＝300,000位變長碼：(45+(13+12+16)×3+(9+5)×4)×1000=224,000位8前綴碼(prefixcode)

前綴碼是指前綴碼中任一字符編碼都不是其它字符編碼的前綴。

0101

01

010

0101010101

01等長碼變長碼100861458281410025553014a:45b:13c:12d:16e:9f:5a:45c:12b:13f:5e:9d:1692.最優(yōu)前綴碼令C為譯碼字符集，T為相關(guān)前綴碼樹f(c)={c∈C：字符c的頻度}dt(c)：字符c在樹T中的深度B(T)=∑f(c).dt(c)，c∈CB(T)表示所有字符編碼的總長，則使B(T)值達(dá)到最小的前綴碼稱為最優(yōu)前綴碼。Huffman編碼就是一種最優(yōu)前綴碼。Huffman樹有二個(gè)特點(diǎn)：①樹中所有葉結(jié)點(diǎn)均為譯碼字符，沒有空余葉結(jié)點(diǎn)。這種樹有稱為滿(full)二叉樹②if葉結(jié)點(diǎn)數(shù)為|C|then內(nèi)部結(jié)點(diǎn)數(shù)為|C|-1個(gè)103.構(gòu)造Huffman編碼Huffman(C) n|c| QC//Q為一隊(duì)列，存放字符頻度值f(c) fori1ton-1 do new(z) left[z]xextract-min(Q) right[z]yextract-min(Q) f[z]f[x]+f[y] insert(Q,z) returnextract-min(Q)貪心選擇策略：每次挑選二個(gè)頻度值最小的字符。11例：構(gòu)造包含6個(gè)字符的Huffman編碼C={f:5,e:9,c:12,b:13,d:16,a:45}算法分析： 初始化建堆時(shí)間為：O(n)

∵當(dāng)采用二叉堆管理隊(duì)列時(shí)，一次extractg-min(Q)的時(shí)間為O(lgn)

∴n次抽取最小值操作時(shí)間的時(shí)間為O(nlgn)

∵一次insert(Q,z)的時(shí)間為O(lgn)

∴n次插入操作的時(shí)間為O(nlgn)

∴總時(shí)間為O(nlgn)124.最優(yōu)前綴碼的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)引理16.2貪心選擇性質(zhì) 令C為一字符集，C中每個(gè)字符c∈C的頻度為f[c]，x,y∈C是二個(gè)具有最小頻度值的字符，則必定存在C的一種最優(yōu)前綴碼，使x,y的碼長相同且僅最后一位不同。proof：①首先證明最優(yōu)前綴碼樹是一棵葉結(jié)點(diǎn)滿二叉樹 設(shè)T是相關(guān)于C的最優(yōu)前綴碼樹，但T的葉結(jié)點(diǎn)不滿 ∵T是最優(yōu)前綴碼樹

∴B(T)最小 令z是T的一個(gè)內(nèi)部結(jié)點(diǎn)且葉結(jié)點(diǎn)不滿，則存在z的二種情況：13Z的孩子沒有內(nèi)部結(jié)點(diǎn)情況：T：T’d-1d-1dB(T’)<B(T)與假設(shè)矛盾Z的孩子有內(nèi)部結(jié)點(diǎn)情況：T：T’d-2d-2d-1d-1d B(T’)<B(T)與假設(shè)矛盾100100zxx100zyx100zyx14②令T是最優(yōu)前綴碼樹，證明x,y碼長相同且僅最后一位不同 設(shè)a,b∈C是T中深度最大的一對葉結(jié)點(diǎn)

∵x,y是頻度最小的二個(gè)字符 ∴f[a]≥f[x]，f[b]≥f[y]

∵a,b深度最大 ∴dt(a)≥dt(x)，dt(b)≥dt(y)

在樹T中交換a和x，b和y的位置，得到新樹T’TT’

xybaabxy15∵dt(a)=dt’(x)，dt(b)=dt’(y)，dt(x)=dt’(a)，dt(y)=dt’(b)16引理16.3最優(yōu)子結(jié)構(gòu)性質(zhì)令C為一字符集，C中每個(gè)字符c∈C的頻度為f[c]，x,y∈C是二個(gè)具有最小頻度值的字符，若在C中去除字符x,y，加上頻度為f[z]=f[x]+f[y]的新字符z，則構(gòu)成一新的字符集C’=C-{x,y}∪{z}。令T’是C’的一棵最優(yōu)前綴碼樹，那么當(dāng)用孩子結(jié)點(diǎn)為x,y的內(nèi)部結(jié)點(diǎn)替換C’中的葉結(jié)點(diǎn)z后得到的新樹T是一棵最優(yōu)前綴碼樹。proof：1)計(jì)算B(T)值 ∵對所有的c∈C-{x,y}有：dt(c)=dt’(c)

∴f[c]dt(c)=f[c]dt’(c)

∵dt(x)=dt(y)=dt’(z)+1

∴f[x]dt(x)+f[y]dt(y)=(f[x]+f[y])dt(x)

=(f[x]+f[y])(dt’(z)+1) =f[z]dt,(z)+f[x]+f[y]17187.6貪心法的理論基礎(chǔ)胚（matroids)def：一個(gè)胚應(yīng)是滿足下述條件的有序?qū)=(S,I)①S是有窮非空集②I是S的一個(gè)非空獨(dú)立子集族，使得若B∈I且AB，則A∈I。滿足此性質(zhì)的I具有遺傳性，即B獨(dú)立，B的子集亦獨(dú)立，其中Φ∈I。③