算法設(shè)計與分析-4

1、第4章 貪心算法 貪心算法概念與基本要素 （1）最優(yōu)子結(jié)構(gòu)性質(zhì) （2）貪心選擇性質(zhì) 貪心算法與動態(tài)規(guī)劃算法的差異 應(yīng)用范例 （1）活動安排問題 （2）哈夫曼編碼 （3）最優(yōu)裝載問題 （4）單源最短路徑 （5）最小生成樹 （6）多機調(diào)度問題貪心算法概念與基本要素 目標：問題形式化表示、比較不同求解方法效率 E.g.1 付款問題 有5元、2元、1元、5角、2角、1角的貨幣多張，假設(shè)每種面值的貨幣的張數(shù)都足夠多，需要找給客戶4元6角 問題：如何挑選合適的幣值及其張數(shù)，使得付給客戶的貨幣總張數(shù)最少？ 多種 答案： 4元6角= 2元*2 + 5角*1 + 1角*1 4張 4元6角= 1元*4 + 2角*

2、2 + 1角*2 8張 .可以采用多種方法求解此問題：枚舉、分治、動態(tài)規(guī)劃、貪心 問題的形式化表示 輸入輸入： 1）可用幣值及其張數(shù) 2張5元、 2張2元、 4張1元、 4張5角、 4張2角、 4張1角 Available=(5, 2, 1, 0.5, 0.2, 0.1) N=(n5元, n2元, n1元, n5角, n2角, n1角) =(2, 2, 4, 4, 4, 4) 2）應(yīng)付款總數(shù)：X = 4元6角 輸出輸出/解向量解向量： 支付的幣種及其張數(shù) 解向量X=(x5元, x2元, x1元, x5角, x2角, x1角) X1=(x5元, x2元, x1元, x5角, x2角, x1角)

3、=(0, 2, 0, 1, 0, 1) 4 X2=(x5元, x2元, x1元, x5角, x2角, x1角) =(0, 0, 4, 0, 2, 2) 8約束約束：1）已支付數(shù)應(yīng)等于應(yīng)支付數(shù)： 5*x5元 + 2* x2元 + 1*x1元 + 0.5* x5角 + 0.2*x2角+ 0.1* x1角 = X=4元6角2）每種貨幣支付的張數(shù)不超過該貨幣總張數(shù)： x5元n5元, x2元n2元, x1元n1元 x5角 n5角, x2角 n2角, x1角 n1角優(yōu)化目標：優(yōu)化目標： 支付的貨幣總張數(shù)最少 對可行解X=(x5元, x2元, x1元, x5角, x2角, x1角)， min (x5元 +

4、x2元 + x1元 + x5角 + x2角 + x1角) 枚舉法求解： 1. 在滿足約束2支付張數(shù)限制的前提下，考慮解向量X中各 分量xi的各種組合，i= 5元, 2元, 1元, 5角, 2角, 1角，得到1個可能解可能解 X=(x5元, x2元, x1元, x5角, x2角, x1角) 注： N=(n5元, n2元, n1元, n5角, n2角, n1角) =(2, 2, 4, 4, 4, 4)時，共有 (2+1)* (2+1)* (4+1)* (4+1)* (4+1)* (4+1)* (4+1)種組合 2. 判斷每種可能解X=(x5元, x2元, x1元, x5角, x2角, x1角)是否

5、滿足約束1支付總額，從中選出可行解可行解 3. 從可行解中選出貨幣總張數(shù)最少者，作為最優(yōu)解最優(yōu)解 分治法求解4元6角2元3角2元3角2元3角2元3角1元2角1元x2元=1X1角=31角X1角=15角x1元=1 分治法求解本問題時的難點：1）如果只采用1種固定的劃分方法，有可能得不到解 e.g 始終采取2等分方式 4元6角 2元3角 1元1角5分？！2）采用多種問題劃分方法，不同劃分導(dǎo)致不同可行/部分解 劃分1：一分為二/2等分 劃分2：m元n角 m元 + n角2）分治法比較難處理最優(yōu)化問題 由于帶有最優(yōu)化要求，需要考慮多種劃分方法、可行解 算法效率 動態(tài)規(guī)劃求解法x2元=12元x2元=24元x

6、5元=00元滿足約束的部分底層最小子問題底層最小子問題：對幣值為i的單種貨幣，分別取0,1, ni張貨幣x1元=22元x1元=44元.。X5角=10.5元X5角=42元.。X2角=10.2元X1角=10.1元4.6元4元0.6元4.6元存在問題：各種規(guī)模的子問題及其組合的數(shù)目太多，求解費時耗力4元4.6元10 貪心方法求解原理：1） 自上而下，逐步構(gòu)造、擴展擴展貨幣支付解向量 X=(x5元, x2元, x1元, x5角, x2角, x1角)初始 ( ?, ? , ?, ?, ?, ? )Step1. ( 0, ?, ?, ?, ? ?)Step2. ( 0, 2, ?, ?, ? ?)Step

7、3. ( 0, 2, 0, ?, ? ?)Step4. ( 0, 2, 0, 1, ? ?)Step5. ( 0, 2, 0, 1, 0 ?)Step6. ( 0, 2, 0, 1, 0 1)2）根據(jù)應(yīng)付款總數(shù)X=4元6角，當前已經(jīng)支付的貨幣總數(shù)Xpayed，計算當前應(yīng)支付錢數(shù)Xtobepayed，3）根據(jù)Xtobepayed，在滿足前述2個約束前提下，從剩余可用貨幣中，選擇一種幣值最大的貨幣選擇一種幣值最大的貨幣，計算應(yīng)支付的張數(shù)通過6個步驟，依次考慮各種幣值，從大到小構(gòu)造可行解Xpayed Xtobepayed 0 4.6 0 4.6 4 0.6 4 0.6 4.5 0.1 4.5 0.1

8、 4.6 011 求解時的局部貪心策略： 構(gòu)造、擴展解向量時，根據(jù)局部信息當前應(yīng)支付Xtobepayed ，選1種當前可用可用的、最大幣值最大幣值的貨幣，在滿足2種約束的前提下，計算本類貨幣應(yīng)支付的張數(shù) 為何選當前可用的最大幣值貨幣？ 為了滿足最優(yōu)化目標：支付的貨幣總張數(shù)最少12 問題： 付款問題中的局部貪心詳略，是否能保證全局最優(yōu)解支付的貨幣的總張數(shù)最少？ 不能保證！E.g.2 付款問題中，應(yīng)付款還是4元6角，但貨幣面值改為 3元2張、1元4張、8角4張、5角4張、1角4張 N=(n3元, n1元, n8角, n5角, n1角) =(2, 4, 4, 4, 4 ) 局部貪心策略解：X=(x3

9、元, x1元, x8角, x5角, x1角) =(1, 1, 0, 1, 1) 4張 全局最優(yōu)解： X=(x3元, x1元, x8角, x5角, x1角) =(1, 0, 2, 0, 0) 3張貪心算法特點： 在算法進行過程中，當面臨選擇時，總是作出在當前看來最好的選擇。 并不從整體最優(yōu)考慮，只是在某種意義上、基于當前狀況的局部最優(yōu)局部最優(yōu)選擇， e.g.見下例 希望：貪心算法得到的最終結(jié)果也是整體最優(yōu)的。 雖然貪心算法從原理上不能保證對所有問題都得到整體最優(yōu)解，但1）對許多問題它能產(chǎn)生整體最優(yōu)解，如單源最短路經(jīng)問題，最小生成樹問題等2）在一些情況下，即使貪心算法不能得到整體最優(yōu)解，其最終結(jié)果

10、卻是最優(yōu)解的很好近似，同時降低了算法復(fù)雜性！ E.g平面凸多邊形的. 自上而下分治三角剖分, 根據(jù)啟發(fā)式信息選取斷點vk：選取使dist(v0, vk) + dist(vk,vn) 最小的vkSendE.g.3 局部最優(yōu)選擇策略： 從當前位置s出發(fā)，選擇下一步路徑長度最短的路徑，即s到下一結(jié)點t的路徑長度最短； 局部最優(yōu)、非全局最優(yōu)。t15貪心算法的一般要素和步驟要素1. 作為問題輸入的候選集合C，據(jù)此構(gòu)造問題的可行解。 e.g. N=(n5元, n2元, n1元, n5角, n2角, n1角) =(2, 2, 4, 4, 4, 4)2. 由部分解（可行解）組成的解集合S=X e.g. 對X=

11、(x5元, x2元, x1元, x5角, x2角, x1角)，S包括： ( ?, ? , ?, ?, ?, ? ) ( 0, ?, ?, ?, ? ?) ( 0, 2, ?, ?, ? ?) ( 0, 2, 0, ?, ? ?) ( 0, 2, 0, 1, ? ?) ( 0, 2, 0, 1, 0 ?) ( 0, 2, 0, 1, 0 1)163. 解決函數(shù)solution，檢查解集合S中的局部解是否構(gòu)成完整的問題解 e.g. 對S中的X=(x5元, x2元, x1元, x5角, x2角, x1角)， 5*x5元 + 2* x2元 + 1*x1元 + 0.5* x5角 + 0.2*x2角+ 0

12、.1* x1角 = 4元6角？4. 局部貪心選擇策略函數(shù)select，根據(jù)目標函數(shù)，挑選最有希望候選對象，擴展局部解 e.g. 從N=(n5元, n2元, n1元, n5角, n2角, n1角) =(2, 2, 4, 4, 4, 4) 的未用剩余可用貨幣中， 根據(jù)Xtobepayed，選擇一種可用的（有剩余）、且選擇一種可用的（有剩余）、且?guī)胖底畲蟮呢泿艓胖底畲蟮呢泿牛员阌嬎惝斍安襟E下應(yīng)支付的張數(shù)175. 可行函數(shù)feasible，判斷擴展后的局部解是否滿足約束 e.g 在某一步，當 X=(x5元, x2元, x1元, x5角, x2角, x1角) =( 0, 2, 0, ?, ? ?) 按

13、照貪心策略，選擇x5角 =1，擴展了局部解 可行性要求：已付出的貨幣和選擇的貨幣之和不超過應(yīng)付款總數(shù)4元6角： 5*x5元 + 2* x2元 + 1* x1元 + 0.5*x5角 4.618 貪心算法步驟Greedy(C) S= ; /*初始解集合為空 while not solution(S) /*S中的局部解沒有構(gòu)成完整全 局解 x= select(C); /*在候選集合C中貪心選擇 if feasible(S,x) /*用x擴展局部解后，是否可行、 滿足約束 S=S+x; /*用x擴展局部解 C=C-x /*今后擴展局部解時，不再考慮x return S4.1 活動安排問題活動安排問題：

14、 爭用某一公共資源的多個活動組成活動集，從活動集中選出最大的相容活動子集合。 e.g. 多場考試，需占用同一個教室貪心算法: 提供了一個簡單、漂亮的方法，使得盡可能多的活動能兼容地使用公共資源。 設(shè)有n個活動的集合E=1,2,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。 每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si fi 如果選擇了活動i，則它在半開時間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的 當sifj或sjfi時，活動i與活動j相容sisjfifjsi

15、fisjfjsifisjfj相容不相容templatevoid GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; /*當前步驟下，已安排的最后1個活動 for (int i=2;i=fj) /*如果活動i與當前已安排的最后1個活動j相容，則安排j Ai=true; j=i; else Ai=false; 活動安排問題的貪心算法GreedySelector :存儲各活動的起始存儲各活動的起始時間和結(jié)束時間，時間和結(jié)束時間，并按結(jié)束時間的非并按結(jié)束時間的非減序排列減序排列! /*將結(jié)束時間最早的活動安排為第1個活動存儲活

16、動安排，存儲活動安排，Ai=trueAi=true表示安排了表示安排了第第i i個活動個活動算法特點：1）輸入的活動以其完成時間fj的非減序非減序排列，算法每次總是選擇： *與已經(jīng)安排的最后1個任務(wù)相容，且 *具有最早完成時間最早完成時間fj的活動加入集合A中2）直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間3）貪心選擇：使剩余的可安排時間段極大化使剩余的可安排時間段極大化所選的所選的fi越小，越小，剩余的空閑時間越多剩余的空閑時間越多，以便后續(xù)可以安排盡可能多的相容活動算法復(fù)雜性：1）當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動2）如果所給出的活動未

17、按非減序排列，可以用O(nlogn)的時間重排，然后用O(nlogn)時間安排活動 例：例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：i12345678910 11Si 130535688212fi45678910 11 12 13 14算法算法greedySelector: 每行相應(yīng)于算法的一次迭代。 陰影長條表示的活動是已選入集合A的活動， 空白長條表示的活動是當前正在檢查相容性的活動。 若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。按fj非遞減排列選擇 貪心算法并不總能求得問題的整體最優(yōu)解整體最優(yōu)解

18、。 但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解： 在每一步，按照最早結(jié)束時間fi的貪心選擇策略，算法最終確定的相容活動集合A的規(guī)模最大，可安排的活動數(shù)最多。 證明：數(shù)學(xué)歸納法證明4.2 貪心算法的基本要素 如何判斷一個具體問題:1)是否可用貪心算法求解2) 能否得到問題的最優(yōu)解 用貪心算法求解的問題需要具有2個重要的性質(zhì)：1）貪心選擇性質(zhì)貪心選擇性質(zhì)2）最優(yōu)子結(jié)構(gòu)性質(zhì)）最優(yōu)子結(jié)構(gòu)性質(zhì)原問題最優(yōu)解中包括了子問題的最優(yōu)解 貪心選擇性質(zhì)：貪心選擇性質(zhì)： 所求問題的整體最優(yōu)解整體最優(yōu)解可以通過一系列局部最優(yōu)局部最優(yōu)的選擇，即貪心選擇來達到。 這是貪心算法可行的第一個

19、基本要素，也是貪心算法與動態(tài)規(guī)劃算法的主要區(qū)別。 動態(tài)規(guī)劃算法：通常以自底向上自底向上的方式解各子問題 貪心算法：通常以自頂向下的方式進行貪心算法：通常以自頂向下的方式進行e.g. 遞歸分治貪遞歸分治貪心三角剖分心三角剖分，以迭代的方式作出相繼的貪心選擇，每作一次貪心選擇就將所求問題簡化為規(guī)模更小的子問題，逐步擴展部分解，得到全局可行解。 確定一個具體問題是否具有貪心選擇性質(zhì)，必須證明：每一步所作的貪心選擇最終導(dǎo)致問題的整體最優(yōu)解。貪心選擇性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì) 當一個問題的最優(yōu)解包含其子問題的最優(yōu)解時，稱此問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)E.g.1 對活動集E=1, 2, 3,4,5,n，如

20、果i1, i2, ,ik-1,ik是它的1個最大相容集，則i1, i2, ,ik-1是子問題E=1, 2, 3,4,5, ik-1的1個最大相容集 通過去除排在后面的一些活動，得到子問題見下頁ikik-130最優(yōu)子結(jié)構(gòu)性質(zhì)E.g.2. 對活動集E=1, 2, 3,4,5, i1,n，如果A=1, i1, i2, ,ik是它的1個最大相容集，則A=A-1= i1, i2, ,ik是子問題E=iE, 并且sif1(在活動1結(jié)束后才開始的那些活動)的1個最大相容集 通過去除排在最前面的第1個和i1之前的活動，得到子問題 問題的最優(yōu)子結(jié)構(gòu)性質(zhì)是該問題可用動態(tài)規(guī)劃算法或貪心算法求解的關(guān)鍵特征。 共同點：

21、 貪心算法和動態(tài)規(guī)劃算法都要求問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)貪心選擇性質(zhì)： 對于具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)的問題，只有具有貪心選擇性質(zhì)時，才選用貪心算法求解。解題方式：動態(tài)規(guī)劃法自下而上，貪心法自上而下逐步求解 下面研究2個經(jīng)典的組合優(yōu)化問題組合優(yōu)化問題，說明貪心算法與動態(tài)規(guī)劃算法的主要差別。3、貪心算法與動態(tài)規(guī)劃算法的差異0-1背包問題背包問題 給定n種物品和一個背包。物品i的重量是Wi，其價值為Vi，背包的容量為C。 要求：選擇裝入背包的物品，使得裝入背包中物品的總價值最大? 在選擇裝入背包的物品時，對每種物品在選擇裝入背包的物品時，對每種物品i只有只有2種選擇，即裝入種選擇，即裝入背包或不裝入背包

22、。背包或不裝入背包。 不能將物品不能將物品i裝入背包多次，也不能只裝入部分的物品裝入背包多次，也不能只裝入部分的物品i。背包問題背包問題 與0-1背包問題類似，所不同的是在選擇物品i裝入背包時，可以選擇物品可以選擇物品i的一部分的一部分，即0 xi 1 ，而不一定要全部裝入背包，1in。 這2類問題極為相似, 都具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)： 對n種物品E=1, 2, 3, 4, , n，其最優(yōu)解為x1, x2, , xn-1, xn。則Xj= X-xj=x1, x2, , xj-1, xj+1, , xn是n-1個物品的子問題E=1, j-1, j+1, , n的最優(yōu)解去掉第j個物品。但背包

23、問題具有貪心選擇性質(zhì)，可以用貪心算法求解；而0-1背包問題卻不能用貪心算法求解。 1）計算每種物品單位重量的價值Vi/Wi ，作為貪心選擇的依據(jù)指標2）貪心選擇: 選擇單位重量價值最高的物品，將盡可能多的 該物品裝入背包 思考：其它貪心策略是否可行？ e.g. 選擇重量最輕、選擇價值最大3）若將所選擇的物品全部裝入背包后，背包內(nèi)的物品總重量未超過C，則選擇單位重量價值次高的物品，并盡可能多地裝入背包4）依此策略一直地進行下去，直到背包裝滿為止 具體算法可描述如下頁： 用貪心算法解背包問題的基本步驟：void Knapsack(int n, float M, float v, float w,

24、float x, N) Sort(n, v, w); /*對n個物品，計算其單位重量價值 vi/wi； n個物品，按照vi/wi從大到小重新排序編號！ int i; for (i=1; i=n;i+) xi=0; /*解向量賦初值 float C=M; /*當前可用背包容量C 初始背包容量M for (i=1; iC) break; /* 物品i的重量超出當前可用背包容量，算法停止 xi=1; /*物品i的重量沒有超出當前可用背包容量，將i全部裝入 c-=wi; /* 調(diào)整當前可用背包容量，減少 /*通過for循環(huán)中各步驟裝入的物品都是整體裝入 if (i0) xi=c/wi; /*如果背包還

25、有剩余容量(C0)， 將剩余容量分配給物品i物品總數(shù)物品價值物品重量解向量背包容量物品集合N=a1,a2,.an對當前考慮的單位價值最大物品i，盡可能全部放入xi=1最后有剩余容量，放入某一類物品的一部分 算法算法knapsack的主要計算時間在于將各種物品依其單位的主要計算時間在于將各種物品依其單位重量的價值從大到小排序重量的價值從大到小排序, 因此算法的計算時間上界為因此算法的計算時間上界為O(nlogn). 為了證明算法的正確性，還必須證明背包問題具有貪心選為了證明算法的正確性，還必須證明背包問題具有貪心選擇性質(zhì)擇性質(zhì) 見下一節(jié)最優(yōu)裝載問題見下一節(jié)最優(yōu)裝載問題 對于0-1背包問題背包問題

26、，貪心選擇之所以不能得到最優(yōu)解原因：貪心選擇無法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價值降低了。 e.g. 見P95圖4-2。 事實上，在考慮0-1背包問題時，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。 由此就導(dǎo)出許多互相重疊的子問題。這正是該問題可用動動態(tài)規(guī)劃算法態(tài)規(guī)劃算法求解的另一重要特征。實際上也是如此，動態(tài)規(guī)劃算法的確可以有效地解0-1背包問題。 4.3 最優(yōu)裝載最優(yōu)裝載 有n個集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。 最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船裝載的集裝箱數(shù)目極大化，且

27、裝入的總重量不超過c（裝載重量受限）。 形式化描述：11max0,1,101niiniiiiiixw xcxinxx 表示不裝入集裝箱, 表示裝入集裝箱最優(yōu)裝載問題看作是0-1背包問題的1個特例：集裝箱=物品，每種物品價值函數(shù)vi=1算法描述算法描述貪心選擇策略：重量最輕者先裝，剩余重量空間最大化，以容納更多的其它貨物，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); /*對n個集裝箱，按照重量wi從小到大從小到大重新排序排列編號 for (int i = 1

28、; i = n; i+) xi = 0; /*解向量賦初值 for (int i = 1; i = n & wti = c; i+) /* 在有剩余容量的前提下， 從輕到重，裝入各個集裝箱 xti = 1; c -= wti; 集裝箱總數(shù)各集裝箱重量解向量總裝載量貪心選擇性質(zhì)貪心選擇性質(zhì)最優(yōu)裝載問題具有貪心選擇性質(zhì)。證明：設(shè)集裝箱已按重量從小到大從小到大排序，x1, x2, ., xn 是最優(yōu)裝載問題的一個最優(yōu)解。 設(shè)k為最先裝入箱中的最輕貨物，即1 |1minii nki x E.g. 最優(yōu)解為1, 1, 0, 1, 1，則k=1； 最優(yōu)解為0, 1, 0, 1, 1，則k=2；當問

29、題有最優(yōu)解（有可能是非貪心策略解）時，（1）當k=1，即最輕的第1個貨物被裝入，貨物選擇的放入順序符合貪心策略， 1111nnniikiiiiiiiw ywww xw xc11nniiiiyx因此，新方案Y是一個滿足貪心策略的可行解。需進一步判斷裝入的集裝箱數(shù)是否最多？又由于說明2個方案Y具有與最優(yōu)方案一樣的裝箱數(shù)，所以：優(yōu)先將最輕的第1個貨物裝入可以使得裝載的總箱數(shù)最大化！綜上所述，Y是一個滿足貪心策略的最優(yōu)解。最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。證明： 假設(shè)貨物1,2,n已按重量從小到大排序。 對原問題：待裝貨物為1,2, n、容量為C，x1, x2, ., xn是

30、其滿足貪心策略的1個最優(yōu)解, 且x1=1。 e.g. 則對子問題：待裝貨物為2,n、容量為C-w1， x2, ., xn是一個最優(yōu)解, e.g. 由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算法loading的正確性。算法復(fù)雜性算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。 4.4 哈夫曼編碼哈夫曼編碼哈夫曼編碼：哈夫曼編碼： 廣泛用于數(shù)據(jù)文件壓縮的十分有效的編碼方法。其壓縮率通常在20%90%之間。原理：1） 根據(jù)字符在文件中出現(xiàn)的頻率表建立一個用0、1串表示各字符的最優(yōu)表示方式： 出現(xiàn)頻率高的字符用較短的編碼，出現(xiàn)頻率較

31、低的字符用較長的編碼，2）可縮短文件中全部字符編碼的總碼長表1 字符出現(xiàn)的頻率表abcdef頻率（千次）4513121695定長碼000001010011100101變長碼010110011111011100采用定長編碼時，每個字符3 bits，文件需要總的存儲位數(shù)：3*（45+13+12+16+9+5）=300,000 bits采用變長編碼時，文件需要總的存儲位數(shù)：45*1 +13*3 +12*3 +16*3 + 9*4 + 5*4）=224,000 bits存儲空間約節(jié)省25%。前綴碼對每一個字符規(guī)定一個0、1串作為其代碼，要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱為前綴碼前綴

32、碼。 E.g. 表4-1中的變長碼為前綴碼編碼的前綴性質(zhì)使譯碼方法非常簡單： 從編碼文件中不斷取出代表某一字符的編碼，轉(zhuǎn)化為原字符編碼的唯一性。e.g. 對變長碼字符串001011101， 如下劃分： 0,0,101,1101 , 譯為aabe 構(gòu)造哈夫曼編碼 原理： 1）以編碼字符集中每個字符c的出現(xiàn)頻率f(c),作為貪心選擇依據(jù)，對字符集進行由小到大的排序?qū)ψ址M行由小到大的排序，每個字符對應(yīng)于一個只包含一個結(jié)點的子樹 2）先合并最小頻率的2個字符對應(yīng)的子樹，計算合并后的子樹的頻率 3）重新排序各個子樹 4）對上述排序后的子樹序列進行合并 5）重復(fù)上述過程，將全部結(jié)點合并成1棵完整的二叉

33、樹 6）對二叉樹中的邊賦予0、1，得到各字符的變長編碼字符abcdef頻率4513121695Step1. 生成單節(jié)點樹，并對其進行排序a：45d：16b：13c：12e：9f：5Step2. 合并具有最小、次最小頻率的2棵樹，并重新進行排序a：45d：16b：13c：12f：5e：914a：45d：16f：5e：914Step3. c：12b：1325a：45Step4. 30c：12b：1325f：5e：914d：16a：45Step5. Step6. 30c：12b：1325f：5e：914d：1655a：4530c：12b：1325f：5e：914d：16551000101010101

34、字符abcdef頻率4513121695路徑長度133344變長碼010110011111011100特點： 最先合并、具有最小頻率的2個字符，如e、f，具有相同碼長，且只有最后一位編碼不相同最優(yōu)前綴碼對已知出現(xiàn)頻率f(c)的字符集C=c，可以有多個不同的（等長、非等長）前綴碼。E.g. 定長碼也是前綴碼 a：45c：12b：13f：5e：9d：16100015801280114018601140最優(yōu)前綴碼編碼樹的平均碼長編碼樹的平均碼長定義為：給定編碼字符集C的最優(yōu)前綴碼：最優(yōu)前綴碼： 使平均碼長達到最小的前綴碼編碼方案 表示最優(yōu)前綴碼最優(yōu)前綴碼的二叉樹總是一棵完全二叉樹完全二叉樹，即樹中任

35、一結(jié)點都有2個兒子結(jié)點。 據(jù)此可知：前面的定長編碼不是最優(yōu)前綴碼)()()(cdcfTBTCc 哈夫曼編碼 哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱為哈夫曼編碼哈夫曼編碼。哈夫曼算法以自底向上的自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹T。算法以|C|個葉結(jié)點開始，執(zhí)行|C|1次的“合并”運算后產(chǎn)生最終所要求的樹T。 算法復(fù)雜性 P110-P111de1算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)，共有n個字符。 1）以）以f為鍵值的優(yōu)先隊列為鍵值的優(yōu)先隊列Q用在貪心選擇貪心選擇時有效地確定算法當前要合并的2棵具有最小頻率的樹。 2） 一旦2棵具有最小頻率

36、的樹合并后，產(chǎn)生一棵新的樹，并將新樹插入優(yōu)先隊列Q。 3）經(jīng)過n1次的合并后，優(yōu)先隊列中只剩下一棵樹，即所要求的樹T。 4）算法用最小堆實現(xiàn)優(yōu)先隊列Q。初始化優(yōu)先隊列需要O(n)計算時間，最小堆的removeMin和put運算均需O(logn)時間，n1次的合并總共需要O(nlogn)計算時間。 因此，關(guān)于n個字符的哈夫曼算法的計算時間計算時間為O(nlogn) 。哈夫曼算法的正確性哈夫曼算法的正確性要證明哈夫曼算法的正確性，需要證明最優(yōu)前綴碼問題具有貪心選擇性質(zhì)貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)問題及其子問題表述： 原問題：字符集C，對應(yīng)的編碼

37、樹T 子問題：C的子集C，對應(yīng)的編碼樹T 優(yōu)化指標：B(T), B(T)哈夫曼算法的正確性哈夫曼算法的正確性問題及其子問題一、貪心選擇性質(zhì) 需要證明： 設(shè)字符集C=c | f(c)，x和y是其中具有最小頻率f(x)和f(y)的2個字符，則存在C的最優(yōu)前綴碼，使x和y具有相同碼長，且只有最后一位編碼不相同。 e.g. f: 1100, e:1101 如果能證明上述命題，就說明構(gòu)造算法是正確的如果能證明上述命題，就說明構(gòu)造算法是正確的全全局最優(yōu)局最優(yōu)顯然，顯然，C 中只有中只有2個字符個字符x、y時，結(jié)論成立時，結(jié)論成立 證明思路： 設(shè)字符集C的1個最優(yōu)前綴碼表示為二叉樹T 。 采用一定方法，將T

38、修改新樹T，使得1）在T中具有最小頻率的x和y是最深葉子，且互為兄弟2）T還是C的最優(yōu)前綴。 這樣x、y在最優(yōu)前綴碼T中只有最后一位不同。 假設(shè)：b、c是T中最深葉子且互為兄弟，f(b)=f(c)； 已知：C中2個最小頻率字符f(x)=f(y)， 但在T中，x、y有可能并非最深結(jié)點！由于x、y具有最小頻率, 故f(x)=f(b)， f(y)=f(c) x: 8 b:10c:12 y:9T: Step1.在T中交換b和x的位置得到T1Step2. 在T1中交換c和y的位置，得到T x: 8 b:10c:12 y:9T: b:10 x:8c:12 y:9T1: b:10 x:8y:9 c:12T:

39、 : 8*1 + 10*3=38 8*3 + 10*1=34: 9*2 + 12*3=54 9*3 + 12*2=51可以證明：B(T)B(T1) 0，即第一步交換不會增加平均碼長B(T1)B(T) 0，即第二步交換也不會增加平均碼長 故T的碼長仍然是最短的，即T是最優(yōu)前綴碼，并且其最小頻率的x、y具有最深的深度（最長的編碼），且只有最后一位不同。二、最優(yōu)子結(jié)構(gòu)性質(zhì)需要證明： 給定字符集C和其對應(yīng)的最優(yōu)前綴碼T，可以從中得到子問題C (C的子集)及其對應(yīng)的最優(yōu)前綴子樹T 構(gòu)造性證明： 對T中2個互為兄弟的葉節(jié)點x、y，z為其父節(jié)點。將z看做頻率為f(z)=f(x)+f(y)的字符，則T=T-x

40、, y是子問題C= (C-x,y) z的最優(yōu)編碼e.g. 原問題C=a,b,x,y,e,fa：45x：12b：13f：5e：9y：16100015801Z:280114018601140T T, C CB(T) vs B(T)?樹樹T, B(T)64a：45x：12b：13f：5e：9y：16100015801Z:280114018601140子樹子樹T, B(T)e.g. 子問題C=a,b,z,e,f證明關(guān)鍵點：1）T的平均碼長B(T)可用子樹T的平均碼長B(T) 表示 B(T) = B(T) + 1*f(x) + 1*f(y)上式：遞推表達式，表示原問題最優(yōu)值與子問題最優(yōu)值之間的關(guān)系T所表

41、示的C的前綴碼的碼長B(T)是最短/最優(yōu)的反證法證明： 假設(shè)有另一個T，是子問題C的最優(yōu)前綴碼，即B(T)B(T)。 節(jié)點z在T還是一個葉節(jié)點，在T 中將z替換為其子節(jié)點x、y，得到T。 e.g 見下頁： 66b：13a：45f：5e：9100015801Z:2814018601140子樹子樹T , B(T)與T不同之處B(T) B(T)b：13x：12a：45f：5e：9y：16100015801Z:280114018601140與T不同之處T是關(guān)于原問題是關(guān)于原問題C的的1個解，同時個解，同時B(T)B(T)，與，與T是最優(yōu)解矛盾。是最優(yōu)解矛盾。樹樹T, B(T)由子問題解子樹由子問題解子

42、樹T ,構(gòu)造原問題的解構(gòu)造原問題的解T：Z替換為替換為x,y4.5 單源最短路徑 給定帶權(quán)有向圖G =(V, E)，V=1,2,3,., n, 其中每條邊的權(quán)cij是非負實數(shù)。 給定V中的一個頂點v，稱為源源。 要求: 計算從源v到所有其它各頂點的最短路長度最短路長度。 路長度：路上各邊權(quán)之和。一、Dijkstra算法:貪心算法1. 設(shè)置集合S，記錄組成最短路徑的頂點 1) 初始時S中只有源點v。不斷地作貪心選擇，擴充S 2) 1個頂點屬于集合S，當且僅當從源到該頂點的最短路徑長度已知4. 設(shè)u是G的某一個頂點， 1）從源v到u的全局全局最短路徑長度為d(v, u)，此最短路徑有可能經(jīng)過不在S

43、中的頂點 2）從源v到u的、且中間只經(jīng)過中間只經(jīng)過S中頂點的路中頂點的路稱為從源到u的特殊路徑。 用數(shù)組distu記錄當前S中每個頂點u所對應(yīng)的最短特殊路徑長度。 d(v,u) duvu頂點集合S121451121d(v, u)distu705. 貪心策略： 每每次從次從V-S中取出具有中取出具有(只經(jīng)過只經(jīng)過S中頂點中頂點)的的最短最短特特殊路長度殊路長度distu的頂點的頂點u，將u添加到S中，同時對數(shù)組dist作必要的修改e.g. 下圖中，對Si外的頂點u、u，從當前頂點集合Si，選擇u VSi，不選u。vu頂點集合Si1214510827u2擴展后的頂點集合Si+1 = Siu0716

44、. 當集合S包含V中所有頂點，distu就記錄了從源v到所有其它頂點u之間的最短路徑長度算法：P113-114e.g. 對右圖中的有向圖，應(yīng)用Dijkstra算法計算從源頂點1到其它頂點間最短路徑的過程列在下頁的表中。迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10+301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代過程：算法特點：迭代過程中，每個節(jié)點迭代過程中，每個節(jié)點v的的distv值是

45、非遞值是非遞增的增的 2、計算復(fù)雜性用帶權(quán)鄰接矩陣表示具有n個頂點和e條邊的帶權(quán)有向圖G(V, E). Dijkstra算法的主循環(huán)體需要O(n) 時間。這個循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時間。 算法的其余部分所需要時間不超過 O(n2)問題及其子問題描述！問題及其子問題描述！ 對圖G(V, E), 源點v，問題從以下三方面描述：1）源點v，圖中頂點集合V, 算法迭代過程中保持不變2）用于構(gòu)造最短路徑的當前頂點集合Si，不斷增加，定義不同規(guī)模的子問題3）指標：相對于現(xiàn)有Si，對各頂點u，distu 不同的不同的Si，定義了不同規(guī)模的子問題；，定義了不同規(guī)模的子問題； 當Si=

46、V時，算法迭代結(jié)束，最短路徑考慮了圖中全部頂點 Si越小，問題越簡單，自下而上求解越小，問題越簡單，自下而上求解3 3、算法正確性、算法正確性貪心選擇性質(zhì)貪心選擇性質(zhì)貪心選擇策略： 在每步迭代時，從V-S中選擇具有最短特殊路徑distu的頂點u，加入S貪心策略正確性： 需證明 對任意頂點u， 從v開始、經(jīng)過G中任意頂點到達u的全局最短路徑的長度d(v, u) = 從v開始、只經(jīng)過S中頂點到達u的最短路徑的長度dist(u) 即：不存在另一條v到u的最短路徑，該路徑上某些節(jié)點x不在V-S 中，且該路徑的長度d(v,u)distu.vuSV-Sx 反證法假設(shè)：（1）在迭代求解過程中，頂點u是遇到的

47、第1個滿足: d(v,u) distu, 即 d(v,u) distu ，的頂點（2）從v到u的全局最短路徑上，第1個屬于V-S的頂點為xSvp1xup2distuu到v的全局最短路徑d(v,u)由2段組成：(1) p1 = distx=dv,xvx(2) p278 首先，因為u是第一個滿足全局最短路徑不完全在S集合中的頂點, 即 d(v, u) distu ，而x是在u之前遇到的頂點，x的最短路徑完全在S中，因此： distx=d(v, x) d(v, x)Svp1xup2distuu到v的全局最短路徑d(v,u)由2段組成：(1) p1 = distx=dv,xvx(2) p279 對v到

48、u的全局最短路徑，有 d(v, x) + distance(x, u) = d(v ,u) 0, 因此 distx= d(v, x) d(v ,u) distu, 即 distx distu根據(jù)假設(shè)X仍然滿足貪心性質(zhì)80 但是根據(jù)路徑p構(gòu)造方法，在下圖所示情況下，u、x都在集合S之外，即u、x都屬于V-S，但 u被選中時，并沒有選x，根據(jù)擴展S的原則選dist最小的頂點加入S，說明此時： distu distx Svxup2 這與 前面推出的 distx distu相矛盾distu 四、最優(yōu)子結(jié)構(gòu)性質(zhì) 對頂點u，考察將u加到S之前和之后，distu的變化，添加u之前的S稱為老S，加入u之后的S

49、稱為新S。 要求：要求：u加到加到S中后，中后，distu不增加。不增加。vu老SV-Sx源i新S對另外對另外1個節(jié)點個節(jié)點i，考察，考察u的加入對的加入對disti的影響：的影響： 1）假設(shè)添加u后, 出現(xiàn)1條從v到i的新路，該路徑先由v經(jīng)過老S中的頂點到達u，再從u經(jīng)過一條直接邊到達ivu老S老V-Sx源i新Sdistucui 該路徑的最短長度=distu + cuidisti 如果distu + cui 原來的disti，則算法用distu + cui 替代disti，得到新的disti。否則， disti不更新。2）如果新路徑如下圖所示，先經(jīng)過u，再回到S中的x，由x直接到達i。x處于

50、老的S中， 故distx已經(jīng)是最短路徑，x比u先加入S，因此 distx distu + d(u,x)vu老SV-Sx源i新Sdistucxidistxd(u,x) 此時，從原v到i的最短路徑disti小于路徑（v, u, x, i）的長度，因此算法更新disti時不需要考慮該路徑，u的加入對disti無影響。因此，無論算法中因此，無論算法中distu的值是否變化，它總是關(guān)于當前頂點的值是否變化，它總是關(guān)于當前頂點集合集合S的到頂點的到頂點u的最短路徑。的最短路徑。也就是說：對于加入也就是說：對于加入u之前、之后的新老之前、之后的新老S所對應(yīng)的所對應(yīng)的2個子問題，個子問題，算法執(zhí)行過程保證了算

51、法執(zhí)行過程保證了distu始終是始終是u的最優(yōu)解的最優(yōu)解問題描述問題描述: 1）圖中頂點集合）圖中頂點集合V, 算法迭代過程中保持不變算法迭代過程中保持不變2）頂點集合）頂點集合S，可以不斷變化，定義了不同規(guī)模的子問題，可以不斷變化，定義了不同規(guī)模的子問題3）指標：對各頂點）指標：對各頂點u，相對于現(xiàn)有相對于現(xiàn)有S，distu85最短路徑算法的改進 參考文獻： 宋青，汪小帆， 最短路徑算法加速技術(shù)研究綜述， 電子科技大學(xué)學(xué)報，Vol.41 No.2 ，2012年3月 加速技術(shù)：1）優(yōu)先隊列2）目標引導(dǎo)3）分層4.6 最小生成樹 生成樹: 設(shè)一個網(wǎng)絡(luò)表示為無向連通帶權(quán)圖G =(V, E) , E

52、中每條邊(v,w)的權(quán)為cvw。 如果G的子圖G是一棵包含G的所有頂點的樹，則稱G為G的生成樹。生成樹的成本成本/代價代價/耗費（耗費（cost）：）： 生成樹上各邊權(quán)的總和。G的最小生成樹：最小生成樹：在G的所有生成樹中，耗費最小的生成樹。應(yīng)用：e.g. 在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)cvw表示建立城市v和城市w之間的通信線路所需的費用，最小生成樹給出建立通信網(wǎng)絡(luò)的最經(jīng)濟方案 8756324135142耗費=15最小生成樹性質(zhì)基于貪心選擇策略, 構(gòu)造最小生成樹算法1） Kruskal算法算法2） Prim算法算法 這2個算法貪心選擇的方式不同，都利用了最小生成樹最小

53、生成樹性質(zhì)性質(zhì)MST性質(zhì)性質(zhì)： 設(shè)G=(V, E)是連通帶權(quán)圖，頂點集U是V的真子集。 如果：1）(u,v)E為橫跨點集U和VU的邊，即uU，vV- U， 并且2）在所有這樣的邊中，(u,v)的權(quán)cuv最小 , 則一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊，即(u,v)出現(xiàn)在最小生成樹中說明：真子集U可以任意選取 56324135142U=3, 4, 5, 6, V-U=1,2邊集=, , , 耗費=15最小生成樹56324135142U=5, V-U=1,2,3,4,6邊集= , , 耗費=15 MST性質(zhì)證明反證法：假設(shè)對G的任意一個最小生成樹T，針對點集U和VU， (u,v)

54、E為橫跨這2個點集的最小權(quán)邊， T不包含該最小權(quán)邊，但T包括節(jié)點u和v。將添加到樹T中，樹T將變?yōu)楹芈返淖訄D含回路的子圖，并且該回路上并且該回路上有一條不同于 的邊, u U, v V-UuuvvUV-U最小生成樹T,圖T ,cuv cuvcuvcuv92 將刪去，得到另一個樹T，即樹T是通過將T中的邊 替換為得到的。 由于這2條邊的耗費滿足cuv cuv，因此用較小耗費的邊替換后得到的樹T的耗費更小，即： T耗費 T的耗費 這與T是任意最小生成樹的假設(shè)相矛盾uuvvUV-U生成樹T,Prim算法設(shè)G=(V, E)是連通帶權(quán)圖，V=1,2,n。Prim算法的基本原理基本原理：Step1. 首先置頂點集合S=1Step2. 當S是V的真子集時，作如下的貪心選擇貪心選擇： 選取滿足條件iS，jV-S，且cij最小的邊，將頂點j添加到S中，邊加到邊集T中。Step3. 重復(fù)上述過程，直到S=V為止，此時邊集T就是最小生成樹 在這個過程中選取到的所有邊恰好構(gòu)成G的一棵最小生成最小生成樹樹。 算法復(fù)雜性：O(