《算法設(shè)計與分析》課件 第6章 貪心算法

算法設(shè)計與分析貪心算法主要內(nèi)容基本概念小數(shù)背包和0-1背包最小生成樹霍夫曼編碼1基本概念是指算法每次做選擇的時是‘貪心’的，也就是盡量選擇從目前看來是最好的如旅行商問中，設(shè)目前處于城市ci，那么就選擇一條從ci到其他城市(還沒有的城市)最短的邊局部最優(yōu)選擇，并不一定能達(dá)到全局最優(yōu)對某些問題是可以得到全局最優(yōu)解，但對另外一些問題是無法獲得全局最優(yōu)解的1例子：錢幣兌換1錢幣兌換：動態(tài)規(guī)劃步驟11錢幣兌換：動態(tài)規(guī)劃步驟21錢幣兌換：動態(tài)規(guī)劃步驟31錢幣兌換：動態(tài)規(guī)劃步驟41錢幣兌換貪心算法先兌換大面額的硬幣，只有在大面額的硬幣無法兌換時，才兌換小面額的硬幣1錢幣兌換貪心算法和動態(tài)規(guī)劃1貪心解是最優(yōu)解嗎？需要證明：貪心算法每次選出的解都屬于最優(yōu)解集合替換法歸納法1貪心解是最優(yōu)解嗎？替換法用貪心算法得出的解(x1,x2,···,xn)和最優(yōu)解(y1,y2,···,yn)中的元素依次進(jìn)行比較，如果元素xi

和yi

相同，則將最優(yōu)解中的yi替換成xi，顯然替換后的解還是最優(yōu)解;如果不同，還是要將yi

替換成xi，但這時，還需要證明替換后的解依然是最優(yōu)解1貪心解是最優(yōu)解嗎？歸納法貪心選擇是正確的

問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)2小數(shù)背包2小數(shù)背包2小數(shù)背包2小數(shù)背包小數(shù)背包貪心算法的正確性證明：替換法設(shè)物品都已經(jīng)按照性價比排好，并設(shè)X=(x1,x2,···,xk,xk+1,···,xn)是貪心算法得出的解，其中0≤xi≤1設(shè)最優(yōu)解為Y=(y1,y2,···,yn)，其中0≤yi≤1找到第一個不相同的元素j，xj

≠yj

2小數(shù)背包2小數(shù)背包2

0-1背包貪心算法不一定能夠得出0-1背包的最優(yōu)解3最小生成樹3最小生成樹3最小生成樹：Kruskal算法3最小生成樹：Kruskal算法3

Kruskal算法對邊排序(語句7)復(fù)雜度為O(mlogm)，第二個for循環(huán)(語句8-13)執(zhí)行m次，循環(huán)體內(nèi)的FIND語句(語句9)的復(fù)雜度為O(logn)，即第二個for循環(huán)的復(fù)雜度為O(mlogn)，所以算法總復(fù)雜度為O(mlogm+mlogn)=O(mlogm)3

最小生成樹3

最小生成樹3

最小生成樹3

最小生成樹：Prim算法3

最小生成樹：Prim算法3

最小生成樹：Prim算法4霍夫曼編碼數(shù)據(jù)壓縮應(yīng)用網(wǎng)絡(luò)、磁盤數(shù)據(jù)壓縮減少數(shù)據(jù)傳輸量減少數(shù)據(jù)存儲量.霍夫曼編碼廣泛的應(yīng)用在數(shù)據(jù)壓縮，可節(jié)省約20%-90%的數(shù)據(jù)量4霍夫曼編碼4霍夫曼編碼4霍夫曼編碼定長和變長編碼形成的編碼樹最優(yōu)編碼樹，每個非葉子節(jié)點都有兩個子節(jié)點4霍夫曼編碼最優(yōu)編碼樹的每個節(jié)點都有兩個節(jié)點4霍夫曼編碼前綴碼：沒有任何碼字是其他碼字的前綴編碼：將每個碼字連接起來即可解碼需要從一串編碼中解碼出每個碼字。簡單，因為沒有重復(fù)的前綴01101000，很容易解碼出為單詞‘bad’霍夫曼編碼是前綴碼4霍夫曼編碼：算法流程4霍夫曼編碼：算法流程因步驟3要重復(fù)n?1次，每次都需排序，復(fù)雜度為O(n2

logn)如果將A中的元素按照頻率組織成最小堆，則取兩個頻率最低元素的復(fù)雜度為logn，插入一個合并后元素的復(fù)雜