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

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

2、2 + 1角*2 8張 .可以采用多種方法求解此問(wèn)題：枚舉、分治、動(dòng)態(tài)規(guī)劃、貪心 問(wèn)題的形式化表示 輸入輸入： 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ù)不超過(guò)該貨幣總張數(shù)： x5元n5元, x2元n2元, x1元n1元 x5角 n5角, x2角 n2角, x1角 n1角優(yōu)化目標(biāo)：優(yōu)化目標(biāo)： 支付的貨幣總張數(shù)最少 對(duì)可行解X=(x5元, x2元, x1元, x5角, x2角, x1角)， min (x5元 +

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

5、從中選出可行解可行解 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 分治法求解本問(wèn)題時(shí)的難點(diǎn)：1）如果只采用1種固定的劃分方法，有可能得不到解 e.g 始終采取2等分方式 4元6角 2元3角 1元1角5分？！2）采用多種問(wèn)題劃分方法，不同劃分導(dǎo)致不同可行/部分解 劃分1：一分為二/2等分 劃分2：m元n角 m元 + n角2）分治法比較難處理最優(yōu)化問(wèn)題 由于帶有最優(yōu)化要求，需要考慮多種劃分方法、可行解 算法效率 動(dòng)態(tài)規(guī)劃求解法x2元=12元x2元=24元x5元=00元滿足約束

6、的部分底層最小子問(wèn)題底層最小子問(wèn)題：對(duì)幣值為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元存在問(wèn)題：各種規(guī)模的子問(wèn)題及其組合的數(shù)目太多，求解費(fèi)時(shí)耗力4元4.6元10 貪心方法求解原理：1） 自上而下，逐步構(gòu)造、擴(kuò)展擴(kuò)展貨幣支付解向量 X=(x5元, x2元, x1元, x5角, x2角, x1角)初始 ( ?, ? , ?, ?, ?, ? )Step1. ( 0, ?, ?, ?, ? ?)Step2. ( 0, 2, ?, ?, ? ?)Step3. ( 0, 2,

7、 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角，當(dāng)前已經(jīng)支付的貨幣總數(shù)Xpayed，計(jì)算當(dāng)前應(yīng)支付錢(qián)數(shù)Xtobepayed，3）根據(jù)Xtobepayed，在滿足前述2個(gè)約束前提下，從剩余可用貨幣中，選擇一種幣值最大的貨幣選擇一種幣值最大的貨幣，計(jì)算應(yīng)支付的張數(shù)通過(guò)6個(gè)步驟，依次考慮各種幣值，從大到小構(gòu)造可行解Xpayed Xtobepayed 0 4.6 0 4.6 4 0.6 4 0.6 4.5 0.1 4.5 0.1 4.6 011 求

8、解時(shí)的局部貪心策略： 構(gòu)造、擴(kuò)展解向量時(shí)，根據(jù)局部信息當(dāng)前應(yīng)支付Xtobepayed ，選1種當(dāng)前可用可用的、最大幣值最大幣值的貨幣，在滿足2種約束的前提下，計(jì)算本類(lèi)貨幣應(yīng)支付的張數(shù) 為何選當(dāng)前可用的最大幣值貨幣？ 為了滿足最優(yōu)化目標(biāo)：支付的貨幣總張數(shù)最少12 問(wèn)題： 付款問(wèn)題中的局部貪心詳略，是否能保證全局最優(yōu)解支付的貨幣的總張數(shù)最少？ 不能保證！E.g.2 付款問(wèn)題中，應(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元, x1元, x8

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

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

11、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)成完整的問(wèn)題解 e.g. 對(duì)S中的X=(x5元, x2元, x1元, x5角, x2角, x1角)， 5*x5元 + 2* x2元 + 1*x1元 + 0.5* x5角 + 0.2*x2角+ 0.1* x1角 = 4元6角？4

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

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

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

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

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

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

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

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

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

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

22、分的物品i。背包問(wèn)題背包問(wèn)題 與0-1背包問(wèn)題類(lèi)似，所不同的是在選擇物品i裝入背包時(shí)，可以選擇物品可以選擇物品i的一部分的一部分，即0 xi 1 ，而不一定要全部裝入背包，1in。 這2類(lèi)問(wèn)題極為相似, 都具有最優(yōu)子結(jié)構(gòu)最優(yōu)子結(jié)構(gòu)性質(zhì)： 對(duì)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個(gè)物品的子問(wèn)題E=1, j-1, j+1, , n的最優(yōu)解去掉第j個(gè)物品。但背包問(wèn)題具有貪心選擇性質(zhì)，可以用貪心算法求解；而0-1背包問(wèn)題卻不能用貪心算法求解。 1）計(jì)算每種物品單位重量的

23、價(jià)值Vi/Wi ，作為貪心選擇的依據(jù)指標(biāo)2）貪心選擇: 選擇單位重量?jī)r(jià)值最高的物品，將盡可能多的 該物品裝入背包 思考：其它貪心策略是否可行？ e.g. 選擇重量最輕、選擇價(jià)值最大3）若將所選擇的物品全部裝入背包后，背包內(nèi)的物品總重量未超過(guò)C，則選擇單位重量?jī)r(jià)值次高的物品，并盡可能多地裝入背包4）依此策略一直地進(jìn)行下去，直到背包裝滿為止 具體算法可描述如下頁(yè)： 用貪心算法解背包問(wèn)題的基本步驟：void Knapsack(int n, float M, float v, float w, float x, N) Sort(n, v, w); /*對(duì)n個(gè)物品，計(jì)算其單位重量?jī)r(jià)值 vi/wi； n個(gè)

24、物品，按照vi/wi從大到小重新排序編號(hào)！ int i; for (i=1; i=n;i+) xi=0; /*解向量賦初值 float C=M; /*當(dāng)前可用背包容量C 初始背包容量M for (i=1; iC) break; /* 物品i的重量超出當(dāng)前可用背包容量，算法停止 xi=1; /*物品i的重量沒(méi)有超出當(dāng)前可用背包容量，將i全部裝入 c-=wi; /* 調(diào)整當(dāng)前可用背包容量，減少 /*通過(guò)for循環(huán)中各步驟裝入的物品都是整體裝入 if (i0) xi=c/wi; /*如果背包還有剩余容量(C0)， 將剩余容量分配給物品i物品總數(shù)物品價(jià)值物品重量解向量背包容量物品集合N=a1,a2,.

25、an對(duì)當(dāng)前考慮的單位價(jià)值最大物品i，盡可能全部放入xi=1最后有剩余容量，放入某一類(lèi)物品的一部分 算法算法knapsack的主要計(jì)算時(shí)間在于將各種物品依其單位的主要計(jì)算時(shí)間在于將各種物品依其單位重量的價(jià)值從大到小排序重量的價(jià)值從大到小排序, 因此算法的計(jì)算時(shí)間上界為因此算法的計(jì)算時(shí)間上界為O(nlogn). 為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選為了證明算法的正確性，還必須證明背包問(wèn)題具有貪心選擇性質(zhì)擇性質(zhì) 見(jiàn)下一節(jié)最優(yōu)裝載問(wèn)題見(jiàn)下一節(jié)最優(yōu)裝載問(wèn)題 對(duì)于0-1背包問(wèn)題背包問(wèn)題，貪心選擇之所以不能得到最優(yōu)解原因：貪心選擇無(wú)法保證最終能將背包裝滿，部分閑置的背包空間使每公斤背包空間的價(jià)

26、值降低了。 e.g. 見(jiàn)P95圖4-2。 事實(shí)上，在考慮0-1背包問(wèn)題時(shí)，應(yīng)比較選擇該物品和不選擇該物品所導(dǎo)致的最終方案，然后再作出最好選擇。 由此就導(dǎo)出許多互相重疊的子問(wèn)題。這正是該問(wèn)題可用動(dòng)動(dòng)態(tài)規(guī)劃算法態(tài)規(guī)劃算法求解的另一重要特征。實(shí)際上也是如此，動(dòng)態(tài)規(guī)劃算法的確可以有效地解0-1背包問(wèn)題。 4.3 最優(yōu)裝載最優(yōu)裝載 有n個(gè)集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。 最優(yōu)裝載問(wèn)題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船裝載的集裝箱數(shù)目極大化，且裝入的總重量不超過(guò)c（裝載重量受限）。 形式化描述：11max0,1,101niiniiiiiixw xcx

27、inxx 表示不裝入集裝箱, 表示裝入集裝箱最優(yōu)裝載問(wèn)題看作是0-1背包問(wèn)題的1個(gè)特例：集裝箱=物品，每種物品價(jià)值函數(shù)vi=1算法描述算法描述貪心選擇策略：重量最輕者先裝，剩余重量空間最大化，以容納更多的其它貨物，可產(chǎn)生最優(yōu)裝載問(wèn)題的最優(yōu)解void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); /*對(duì)n個(gè)集裝箱，按照重量wi從小到大從小到大重新排序排列編號(hào) for (int i = 1; i = n; i+) xi = 0; /*解向量賦初值 for (int i = 1; i = n &a

28、mp; wti = c; i+) /* 在有剩余容量的前提下， 從輕到重，裝入各個(gè)集裝箱 xti = 1; c -= wti; 集裝箱總數(shù)各集裝箱重量解向量總裝載量貪心選擇性質(zhì)貪心選擇性質(zhì)最優(yōu)裝載問(wèn)題具有貪心選擇性質(zhì)。證明：設(shè)集裝箱已按重量從小到大從小到大排序，x1, x2, ., xn 是最優(yōu)裝載問(wèn)題的一個(gè)最優(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；當(dāng)問(wèn)題有最優(yōu)解（有可能是非貪心策略解）時(shí)，（1）當(dāng)k=1，即最輕的第1個(gè)貨物被裝入，貨物選擇的放入順序符合貪心策

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

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

31、13121695定長(zhǎng)碼000001010011100101變長(zhǎng)碼010110011111011100采用定長(zhǎng)編碼時(shí)，每個(gè)字符3 bits，文件需要總的存儲(chǔ)位數(shù)：3*（45+13+12+16+9+5）=300,000 bits采用變長(zhǎng)編碼時(shí)，文件需要總的存儲(chǔ)位數(shù)：45*1 +13*3 +12*3 +16*3 + 9*4 + 5*4）=224,000 bits存儲(chǔ)空間約節(jié)省25%。前綴碼對(duì)每一個(gè)字符規(guī)定一個(gè)0、1串作為其代碼，要求任一字符的代碼都不是其它字符代碼的前綴。這種編碼稱(chēng)為前綴碼前綴碼。 E.g. 表4-1中的變長(zhǎng)碼為前綴碼編碼的前綴性質(zhì)使譯碼方法非常簡(jiǎn)單： 從編碼文件中不斷取出代表某一字

32、符的編碼，轉(zhuǎn)化為原字符編碼的唯一性。e.g. 對(duì)變長(zhǎng)碼字符串001011101， 如下劃分： 0,0,101,1101 , 譯為aabe 構(gòu)造哈夫曼編碼 原理： 1）以編碼字符集中每個(gè)字符c的出現(xiàn)頻率f(c),作為貪心選擇依據(jù)，對(duì)字符集進(jìn)行由小到大的排序?qū)ψ址M(jìn)行由小到大的排序，每個(gè)字符對(duì)應(yīng)于一個(gè)只包含一個(gè)結(jié)點(diǎn)的子樹(shù) 2）先合并最小頻率的2個(gè)字符對(duì)應(yīng)的子樹(shù)，計(jì)算合并后的子樹(shù)的頻率 3）重新排序各個(gè)子樹(shù) 4）對(duì)上述排序后的子樹(shù)序列進(jìn)行合并 5）重復(fù)上述過(guò)程，將全部結(jié)點(diǎn)合并成1棵完整的二叉樹(shù) 6）對(duì)二叉樹(shù)中的邊賦予0、1，得到各字符的變長(zhǎng)編碼字符abcdef頻率4513121695Step1.

33、生成單節(jié)點(diǎn)樹(shù)，并對(duì)其進(jìn)行排序a：45d：16b：13c：12e：9f：5Step2. 合并具有最小、次最小頻率的2棵樹(shù)，并重新進(jìn)行排序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字符abcdef頻率4513121695路徑長(zhǎng)度133344變長(zhǎng)碼010110011111011100特點(diǎn)：

34、 最先合并、具有最小頻率的2個(gè)字符，如e、f，具有相同碼長(zhǎng)，且只有最后一位編碼不相同最優(yōu)前綴碼對(duì)已知出現(xiàn)頻率f(c)的字符集C=c，可以有多個(gè)不同的（等長(zhǎng)、非等長(zhǎng)）前綴碼。E.g. 定長(zhǎng)碼也是前綴碼 a：45c：12b：13f：5e：9d：16100015801280114018601140最優(yōu)前綴碼編碼樹(shù)的平均碼長(zhǎng)編碼樹(shù)的平均碼長(zhǎng)定義為：給定編碼字符集C的最優(yōu)前綴碼：最優(yōu)前綴碼： 使平均碼長(zhǎng)達(dá)到最小的前綴碼編碼方案 表示最優(yōu)前綴碼最優(yōu)前綴碼的二叉樹(shù)總是一棵完全二叉樹(shù)完全二叉樹(shù)，即樹(shù)中任一結(jié)點(diǎn)都有2個(gè)兒子結(jié)點(diǎn)。 據(jù)此可知：前面的定長(zhǎng)編碼不是最優(yōu)前綴碼)()()(cdcfTBTCc 哈夫曼編碼

35、哈夫曼提出構(gòu)造最優(yōu)前綴碼的貪心算法，由此產(chǎn)生的編碼方案稱(chēng)為哈夫曼編碼哈夫曼編碼。哈夫曼算法以自底向上的自底向上的方式構(gòu)造表示最優(yōu)前綴碼的二叉樹(shù)T。算法以|C|個(gè)葉結(jié)點(diǎn)開(kāi)始，執(zhí)行|C|1次的“合并”運(yùn)算后產(chǎn)生最終所要求的樹(shù)T。 算法復(fù)雜性 P110-P111de1算法huffmanTree中，編碼字符集中每一字符c的頻率是f(c)，共有n個(gè)字符。 1）以）以f為鍵值的優(yōu)先隊(duì)列為鍵值的優(yōu)先隊(duì)列Q用在貪心選擇貪心選擇時(shí)有效地確定算法當(dāng)前要合并的2棵具有最小頻率的樹(shù)。 2） 一旦2棵具有最小頻率的樹(shù)合并后，產(chǎn)生一棵新的樹(shù)，并將新樹(shù)插入優(yōu)先隊(duì)列Q。 3）經(jīng)過(guò)n1次的合并后，優(yōu)先隊(duì)列中只剩下一棵樹(shù)，即所要

36、求的樹(shù)T。 4）算法用最小堆實(shí)現(xiàn)優(yōu)先隊(duì)列Q。初始化優(yōu)先隊(duì)列需要O(n)計(jì)算時(shí)間，最小堆的removeMin和put運(yùn)算均需O(logn)時(shí)間，n1次的合并總共需要O(nlogn)計(jì)算時(shí)間。 因此，關(guān)于n個(gè)字符的哈夫曼算法的計(jì)算時(shí)間計(jì)算時(shí)間為O(nlogn) 。哈夫曼算法的正確性哈夫曼算法的正確性要證明哈夫曼算法的正確性，需要證明最優(yōu)前綴碼問(wèn)題具有貪心選擇性質(zhì)貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)最優(yōu)子結(jié)構(gòu)性質(zhì)。(1)貪心選擇性質(zhì)(2)最優(yōu)子結(jié)構(gòu)性質(zhì)問(wèn)題及其子問(wèn)題表述： 原問(wèn)題：字符集C，對(duì)應(yīng)的編碼樹(shù)T 子問(wèn)題：C的子集C，對(duì)應(yīng)的編碼樹(shù)T 優(yōu)化指標(biāo)：B(T), B(T)哈夫曼算法的正確性哈夫曼算法的正確性

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

38、優(yōu)前綴碼T中只有最后一位不同。 假設(shè)：b、c是T中最深葉子且互為兄弟，f(b)=f(c)； 已知：C中2個(gè)最小頻率字符f(x)=f(y)， 但在T中，x、y有可能并非最深結(jié)點(diǎn)！由于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: : 8*1 + 10*3=38 8*3 + 10*1=34: 9*2 + 12*3=54 9*3 + 12

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

40、：13f：5e：9y：16100015801Z:280114018601140T T, C CB(T) vs B(T)?樹(shù)樹(shù)T, B(T)64a：45x：12b：13f：5e：9y：16100015801Z:280114018601140子樹(shù)子樹(shù)T, B(T)e.g. 子問(wèn)題C=a,b,z,e,f證明關(guān)鍵點(diǎn)：1）T的平均碼長(zhǎng)B(T)可用子樹(shù)T的平均碼長(zhǎng)B(T) 表示 B(T) = B(T) + 1*f(x) + 1*f(y)上式：遞推表達(dá)式，表示原問(wèn)題最優(yōu)值與子問(wèn)題最優(yōu)值之間的關(guān)系T所表示的C的前綴碼的碼長(zhǎng)B(T)是最短/最優(yōu)的反證法證明： 假設(shè)有另一個(gè)T，是子問(wèn)題C的最優(yōu)前綴碼，即B(T)B

41、(T)。 節(jié)點(diǎn)z在T還是一個(gè)葉節(jié)點(diǎn)，在T 中將z替換為其子節(jié)點(diǎn)x、y，得到T。 e.g 見(jiàn)下頁(yè)： 66b：13a：45f：5e：9100015801Z:2814018601140子樹(shù)子樹(shù)T , B(T)與T不同之處B(T) B(T)b：13x：12a：45f：5e：9y：16100015801Z:280114018601140與T不同之處T是關(guān)于原問(wèn)題是關(guān)于原問(wèn)題C的的1個(gè)解，同時(shí)個(gè)解，同時(shí)B(T)B(T)，與，與T是最優(yōu)解矛盾。是最優(yōu)解矛盾。樹(shù)樹(shù)T, B(T)由子問(wèn)題解子樹(shù)由子問(wèn)題解子樹(shù)T ,構(gòu)造原問(wèn)題的解構(gòu)造原問(wèn)題的解T：Z替換為替換為x,y4.5 單源最短路徑 給定帶權(quán)有向圖G =(V,

42、 E)，V=1,2,3,., n, 其中每條邊的權(quán)cij是非負(fù)實(shí)數(shù)。 給定V中的一個(gè)頂點(diǎn)v，稱(chēng)為源源。 要求: 計(jì)算從源v到所有其它各頂點(diǎn)的最短路長(zhǎng)度最短路長(zhǎng)度。 路長(zhǎng)度：路上各邊權(quán)之和。一、Dijkstra算法:貪心算法1. 設(shè)置集合S，記錄組成最短路徑的頂點(diǎn) 1) 初始時(shí)S中只有源點(diǎn)v。不斷地作貪心選擇，擴(kuò)充S 2) 1個(gè)頂點(diǎn)屬于集合S，當(dāng)且僅當(dāng)從源到該頂點(diǎn)的最短路徑長(zhǎng)度已知4. 設(shè)u是G的某一個(gè)頂點(diǎn)， 1）從源v到u的全局全局最短路徑長(zhǎng)度為d(v, u)，此最短路徑有可能經(jīng)過(guò)不在S中的頂點(diǎn) 2）從源v到u的、且中間只經(jīng)過(guò)中間只經(jīng)過(guò)S中頂點(diǎn)的路中頂點(diǎn)的路稱(chēng)為從源到u的特殊路徑。 用數(shù)組di

43、stu記錄當(dāng)前S中每個(gè)頂點(diǎn)u所對(duì)應(yīng)的最短特殊路徑長(zhǎng)度。 d(v,u) duvu頂點(diǎn)集合S121451121d(v, u)distu705. 貪心策略： 每每次從次從V-S中取出具有中取出具有(只經(jīng)過(guò)只經(jīng)過(guò)S中頂點(diǎn)中頂點(diǎn))的的最短最短特特殊路長(zhǎng)度殊路長(zhǎng)度distu的頂點(diǎn)的頂點(diǎn)u，將u添加到S中，同時(shí)對(duì)數(shù)組dist作必要的修改e.g. 下圖中，對(duì)Si外的頂點(diǎn)u、u，從當(dāng)前頂點(diǎn)集合Si，選擇u VSi，不選u。vu頂點(diǎn)集合Si1214510827u2擴(kuò)展后的頂點(diǎn)集合Si+1 = Siu0716. 當(dāng)集合S包含V中所有頂點(diǎn)，distu就記錄了從源v到所有其它頂點(diǎn)u之間的最短路徑長(zhǎng)度算法：P113-11

44、4e.g. 對(duì)右圖中的有向圖，應(yīng)用Dijkstra算法計(jì)算從源頂點(diǎn)1到其它頂點(diǎn)間最短路徑的過(guò)程列在下頁(yè)的表中。迭代迭代S Su udist2dist2 dist3dist3 dist4dist4 dist5dist5初始初始1-10+301001 11,221060301002 21,2,44105030903 31,2,4,33105030604 41,2,4,3,5510503060Dijkstra算法的迭代過(guò)程：算法特點(diǎn)：迭代過(guò)程中，每個(gè)節(jié)點(diǎn)迭代過(guò)程中，每個(gè)節(jié)點(diǎn)v的的distv值是非遞值是非遞增的增的 2、計(jì)算復(fù)雜性用帶權(quán)鄰接矩陣表示具有n個(gè)頂點(diǎn)和e條邊的帶權(quán)有向圖G(V, E). Di

45、jkstra算法的主循環(huán)體需要O(n) 時(shí)間。這個(gè)循環(huán)需要執(zhí)行n-1次，所以完成循環(huán)需要O(n2)時(shí)間。 算法的其余部分所需要時(shí)間不超過(guò) O(n2)問(wèn)題及其子問(wèn)題描述！問(wèn)題及其子問(wèn)題描述！ 對(duì)圖G(V, E), 源點(diǎn)v，問(wèn)題從以下三方面描述：1）源點(diǎn)v，圖中頂點(diǎn)集合V, 算法迭代過(guò)程中保持不變2）用于構(gòu)造最短路徑的當(dāng)前頂點(diǎn)集合Si，不斷增加，定義不同規(guī)模的子問(wèn)題3）指標(biāo)：相對(duì)于現(xiàn)有Si，對(duì)各頂點(diǎn)u，distu 不同的不同的Si，定義了不同規(guī)模的子問(wèn)題；，定義了不同規(guī)模的子問(wèn)題； 當(dāng)Si=V時(shí)，算法迭代結(jié)束，最短路徑考慮了圖中全部頂點(diǎn) Si越小，問(wèn)題越簡(jiǎn)單，自下而上求解越小，問(wèn)題越簡(jiǎn)單，自下而上

46、求解3 3、算法正確性、算法正確性貪心選擇性質(zhì)貪心選擇性質(zhì)貪心選擇策略： 在每步迭代時(shí)，從V-S中選擇具有最短特殊路徑distu的頂點(diǎn)u，加入S貪心策略正確性： 需證明 對(duì)任意頂點(diǎn)u， 從v開(kāi)始、經(jīng)過(guò)G中任意頂點(diǎn)到達(dá)u的全局最短路徑的長(zhǎng)度d(v, u) = 從v開(kāi)始、只經(jīng)過(guò)S中頂點(diǎn)到達(dá)u的最短路徑的長(zhǎng)度dist(u) 即：不存在另一條v到u的最短路徑，該路徑上某些節(jié)點(diǎn)x不在V-S 中，且該路徑的長(zhǎng)度d(v,u)distu.vuSV-Sx 反證法假設(shè)：（1）在迭代求解過(guò)程中，頂點(diǎn)u是遇到的第1個(gè)滿足: d(v,u) distu, 即 d(v,u) distu ，的頂點(diǎn)（2）從v到u的全局最短路徑

47、上，第1個(gè)屬于V-S的頂點(diǎn)為xSvp1xup2distuu到v的全局最短路徑d(v,u)由2段組成：(1) p1 = distx=dv,xvx(2) p278 首先，因?yàn)閡是第一個(gè)滿足全局最短路徑不完全在S集合中的頂點(diǎn), 即 d(v, u) distu ，而x是在u之前遇到的頂點(diǎn)，x的最短路徑完全在S中，因此： distx=d(v, x) d(v, x)Svp1xup2distuu到v的全局最短路徑d(v,u)由2段組成：(1) p1 = distx=dv,xvx(2) p279 對(duì)v到u的全局最短路徑，有 d(v, x) + distance(x, u) = d(v ,u) 0, 因此 di

48、stx= 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被選中時(shí)，并沒(méi)有選x，根據(jù)擴(kuò)展S的原則選dist最小的頂點(diǎn)加入S，說(shuō)明此時(shí)： distu distx Svxup2 這與 前面推出的 distx distu相矛盾distu 四、最優(yōu)子結(jié)構(gòu)性質(zhì) 對(duì)頂點(diǎn)u，考察將u加到S之前和之后，distu的變化，添加u之前的S稱(chēng)為老S，加入u之后的S稱(chēng)為新S。 要求：要求：u加到加到S中后，中后，distu不增加。不增加。vu老SV-Sx源i新S對(duì)另外對(duì)另

49、外1個(gè)節(jié)點(diǎn)個(gè)節(jié)點(diǎn)i，考察，考察u的加入對(duì)的加入對(duì)disti的影響：的影響： 1）假設(shè)添加u后, 出現(xiàn)1條從v到i的新路，該路徑先由v經(jīng)過(guò)老S中的頂點(diǎn)到達(dá)u，再?gòu)膗經(jīng)過(guò)一條直接邊到達(dá)ivu老S老V-Sx源i新Sdistucui 該路徑的最短長(zhǎng)度=distu + cuidisti 如果distu + cui 原來(lái)的disti，則算法用distu + cui 替代disti，得到新的disti。否則， disti不更新。2）如果新路徑如下圖所示，先經(jīng)過(guò)u，再回到S中的x，由x直接到達(dá)i。x處于老的S中， 故distx已經(jīng)是最短路徑，x比u先加入S，因此 distx distu + d(u,x)vu老

50、SV-Sx源i新Sdistucxidistxd(u,x) 此時(shí)，從原v到i的最短路徑disti小于路徑（v, u, x, i）的長(zhǎng)度，因此算法更新disti時(shí)不需要考慮該路徑，u的加入對(duì)disti無(wú)影響。因此，無(wú)論算法中因此，無(wú)論算法中distu的值是否變化，它總是關(guān)于當(dāng)前頂點(diǎn)的值是否變化，它總是關(guān)于當(dāng)前頂點(diǎn)集合集合S的到頂點(diǎn)的到頂點(diǎn)u的最短路徑。的最短路徑。也就是說(shuō)：對(duì)于加入也就是說(shuō)：對(duì)于加入u之前、之后的新老之前、之后的新老S所對(duì)應(yīng)的所對(duì)應(yīng)的2個(gè)子問(wèn)題，個(gè)子問(wèn)題，算法執(zhí)行過(guò)程保證了算法執(zhí)行過(guò)程保證了distu始終是始終是u的最優(yōu)解的最優(yōu)解問(wèn)題描述問(wèn)題描述: 1）圖中頂點(diǎn)集合）圖中頂點(diǎn)集合V

51、, 算法迭代過(guò)程中保持不變算法迭代過(guò)程中保持不變2）頂點(diǎn)集合）頂點(diǎn)集合S，可以不斷變化，定義了不同規(guī)模的子問(wèn)題，可以不斷變化，定義了不同規(guī)模的子問(wèn)題3）指標(biāo)：對(duì)各頂點(diǎn)）指標(biāo)：對(duì)各頂點(diǎn)u，相對(duì)于現(xiàn)有相對(duì)于現(xiàn)有S，distu85最短路徑算法的改進(jìn) 參考文獻(xiàn)： 宋青，汪小帆， 最短路徑算法加速技術(shù)研究綜述， 電子科技大學(xué)學(xué)報(bào)，Vol.41 No.2 ，2012年3月 加速技術(shù)：1）優(yōu)先隊(duì)列2）目標(biāo)引導(dǎo)3）分層4.6 最小生成樹(shù) 生成樹(shù): 設(shè)一個(gè)網(wǎng)絡(luò)表示為無(wú)向連通帶權(quán)圖G =(V, E) , E中每條邊(v,w)的權(quán)為cvw。 如果G的子圖G是一棵包含G的所有頂點(diǎn)的樹(shù)，則稱(chēng)G為G的生成樹(shù)。生成樹(shù)的成本

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

53、E為橫跨點(diǎn)集U和VU的邊，即uU，vV- U， 并且2）在所有這樣的邊中，(u,v)的權(quán)cuv最小 , 則一定存在G的一棵最小生成樹(shù)，它以(u,v)為其中一條邊，即(u,v)出現(xiàn)在最小生成樹(shù)中說(shuō)明：真子集U可以任意選取 56324135142U=3, 4, 5, 6, V-U=1,2邊集=, , , 耗費(fèi)=15最小生成樹(shù)56324135142U=5, V-U=1,2,3,4,6邊集= , , 耗費(fèi)=15 MST性質(zhì)證明反證法：假設(shè)對(duì)G的任意一個(gè)最小生成樹(shù)T，針對(duì)點(diǎn)集U和VU， (u,v)E為橫跨這2個(gè)點(diǎn)集的最小權(quán)邊， T不包含該最小權(quán)邊，但T包括節(jié)點(diǎn)u和v。將添加到樹(shù)T中，樹(shù)T將變?yōu)楹芈返淖?/p>

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