第4章-貪心法

1、1貪心算法又叫登山法，它的根本思想是逐步到達山頂，即逐步獲得最優(yōu)解，以逐步的局部最優(yōu)，達到最終的全局最優(yōu)。第第4章章 貪心法貪心法（Greedy Approach）24.1 貪心法的設計思想貪心法的設計思想4.2 貪心法的正確性證明貪心法的正確性證明4.3 對貪心法得不到最優(yōu)解情況的處理對貪心法得不到最優(yōu)解情況的處理4.4 貪心法的典型應用貪心法的典型應用 4.4.1 最優(yōu)前綴碼最優(yōu)前綴碼 4.4.2 最小生成樹最小生成樹 4.4.3 單源最短路徑單源最短路徑第第4章章 貪心法貪心法（Greedy Approach）3例：幣種統(tǒng)計問題例：幣種統(tǒng)計問題某單位給每個職工發(fā)工資（精確到元）。為了保證

2、不要臨某單位給每個職工發(fā)工資（精確到元）。為了保證不要臨時兌換零錢時兌換零錢, 且取款的張數(shù)最少，取工資前要統(tǒng)計出所有且取款的張數(shù)最少，取工資前要統(tǒng)計出所有職工的工資所需各種幣值職工的工資所需各種幣值(100,50,20,10,5,2,1元共七種元共七種)的的張數(shù)。張數(shù)。注：假若注：假若,某國的幣種是這樣的某國的幣種是這樣的,共共9種種: 100,70,50,20,10,7,5,2,1。4活動選擇問題活動選擇問題輸入：輸入：S =1, 2, , n為為n 項活動的集合，項活動的集合，si, fi 分別為活動分別為活動 i 的開始和結束時間，的開始和結束時間，活動活動 i 與與 j 相容相容 s

3、i fj 或或 sj fi .求：最大的兩兩相容的活動集求：最大的兩兩相容的活動集 A 實例實例策略策略1：排序使得：排序使得 s1 s2 sn，從前向后挑選，從前向后挑選策略策略2：排序使得：排序使得 f1s1 f2s2 fnsn，從前向后挑選，從前向后挑選策略策略3：排序使得：排序使得 f1 f2 fn，從前向后挑選，從前向后挑選以上策略中的挑選都要注意滿足相容性條件以上策略中的挑選都要注意滿足相容性條件4.1貪心法的設計思想貪心法的設計思想i12345678910si1325456882fi45679910111213兩個反例兩個反例 2310 2 5 8 10 15 20 2310 2

4、 5 8 10 15 20 策略策略1：S=1,2,3，s1=0, f1=20, s2=2, f2=5, s3=8, f3=15 策略策略2：S=1,2,3，s1=0, f1=8, s2=7, f2=9, s3=8, f3=15 6貪心算法貪心算法算法算法4.1 Greedy Select輸入：活動集輸入：活動集S，si，fi, i=1,2,n，且，且 f1 fn 輸出：輸出：A S，選中的活動子集，選中的活動子集 1. nlengthS / 活動個數(shù)活動個數(shù) 2. A1 3. j1 /已選入的最后一個活動的標號已選入的最后一個活動的標號 4. for i2 to n do 5. if si

5、fj /判斷相容性判斷相容性 6. then A A i 7. j i 8. return A 最后完成時間最后完成時間 t = max fk: k A 7輸入：輸入：S=1, 2, , 10i12345678910si1305356882fi45678910111213問題：如何證明該算法對所有的實例都能得到正確的解？問題：如何證明該算法對所有的實例都能得到正確的解？算法運行實例算法運行實例解解: : A = 1, 4, 8, t =11時間復雜度：排序時間復雜度：排序+活動選擇活動選擇=O(nlogn)+O(n)=O(nlogn)8算法的正確性證明算法的正確性證明證：證：S=1, 2, ,

6、 n是活動集，是活動集，且且 f1 fn 歸納基礎：歸納基礎：k=1, 證明存在最優(yōu)解包含活動證明存在最優(yōu)解包含活動1任取最優(yōu)解任取最優(yōu)解A, A中的活動按截止時間遞增排列中的活動按截止時間遞增排列. 如果如果A的第的第一個活動為一個活動為 j，j 1, 令令 A= (A j ) 1, 由于由于 f1 fj , A也是最優(yōu)解，且含有也是最優(yōu)解，且含有1. 定理定理4.1 算法算法Select 執(zhí)行到第執(zhí)行到第 k 步步, 選擇選擇 k 項活動項活動 i1= 1, i2, , ik, 那么存在最優(yōu)解那么存在最優(yōu)解 A 包含包含 i1=1, i2, , ik .根據(jù)定理：針對上述問題，算法至多到第

7、根據(jù)定理：針對上述問題，算法至多到第 n 步得到最優(yōu)解步得到最優(yōu)解9)(,.,.,112121 kkkkiBiiiiBiii也是原問題的最優(yōu)解也是原問題的最優(yōu)解. .歸納步驟：假設命題對歸納步驟：假設命題對 k 為真為真, 證明對證明對 k+1 也為真也為真. 算法執(zhí)行到第算法執(zhí)行到第 k 步步, 選擇了活動選擇了活動 i1=1, i2, , ik, 根據(jù)歸納假設根據(jù)歸納假設存在最優(yōu)解存在最優(yōu)解 A 包含包含 i1= 1, i2, , ik , A中剩下的活動選自集合中剩下的活動選自集合 S= i | i S, si fk, 且且 A = i1, i2, , ik B其中其中B是是S的最優(yōu)解的

8、最優(yōu)解.（若不然（若不然, S的最優(yōu)解為的最優(yōu)解為B*, B*的活動的活動比比 B多，那么多，那么B* 1, i2, , ik是是 S 的最優(yōu)解，且比的最優(yōu)解，且比 A的活的活動多動多,與與 A 的最優(yōu)性矛盾的最優(yōu)性矛盾.）根據(jù)歸納基礎，存在根據(jù)歸納基礎，存在 S的最優(yōu)解的最優(yōu)解B含有含有S中的第一個活動，中的第一個活動，即即ik+1, 且且|B|=|B|, 于是于是 算法正確性證明（續(xù)）算法正確性證明（續(xù)）10貪心算法的特點貪心算法的特點設計要素：設計要素：(1)貪心法適用于組合優(yōu)化問題貪心法適用于組合優(yōu)化問題. (2)求解過程是多步判斷過程，最終的判斷序列對應于問題求解過程是多步判斷過程，

9、最終的判斷序列對應于問題 的最優(yōu)解的最優(yōu)解. (3)判斷依據(jù)某種判斷依據(jù)某種“短視的短視的”貪心選擇性質，性質的好壞決貪心選擇性質，性質的好壞決 定了算法的成敗定了算法的成敗. (4)貪心法必須進行正確性證明貪心法必須進行正確性證明貪心法的優(yōu)勢：貪心法的優(yōu)勢：算法簡單，時間和空間復雜性低算法簡單，時間和空間復雜性低11 4.2 貪心法的正確性證明貪心法的正確性證明數(shù)學歸納法數(shù)學歸納法 1. 敘述一個描述算法正確性的命題敘述一個描述算法正確性的命題P(n)，n為算法步數(shù)或者為算法步數(shù)或者 問題規(guī)模問題規(guī)模 2. 歸納基礎：歸納基礎：P(1) 或或 P(n0)為真為真, n0為某個自然數(shù)為某個自然

10、數(shù) 3. 歸納步驟：歸納步驟：P(k) P(k+1) 第一數(shù)學歸納法第一數(shù)學歸納法 k(k | I |； 那么那么 I* 1是關于是關于 N 和和C的解且的解且 | I* 1| | I 1 | = | I| 與與 I 的最優(yōu)性矛盾的最優(yōu)性矛盾.正確性證明正確性證明14最小延遲調(diào)度最小延遲調(diào)度例例4.3 最小延遲調(diào)度最小延遲調(diào)度給定客戶集合給定客戶集合A， i A，ti 為服務時間，為服務時間，di 為客戶期待完成為客戶期待完成時間，時間，ti, di為正整數(shù)為正整數(shù). 一個一個調(diào)度調(diào)度是函數(shù)是函數(shù) f : AN，f(i)為客為客戶戶 i 的開始時間的開始時間. 求求最大延遲達到最小的調(diào)度，即求

11、最大延遲達到最小的調(diào)度，即求 f 使使得得)(maxminiiAifdtif )()(or)()(,iftjfjftifjiAjiji h(A,B) = |ba|minmaxBbAa15實例實例調(diào)度調(diào)度1： f1(1)=0, f1(2)=5, f1(3)=13, f1(4)=17, f1(5)=27 各任務延遲：各任務延遲：0, 1, 2, 16, 10; 最大延遲：最大延遲：16 1 2 3 4 5 5 13 17 27 30 調(diào)度調(diào)度2： f2(1)=0, f2(2)=15, f2(3)=23, f2(4)=5, f2(5)=27 各任務延遲：各任務延遲：0, 11, 12, 4, 10;

12、 最大延遲：最大延遲：12A=1, 2, 3, 4, 5, T=, D= 1 4 2 3 5 5 15 23 27 3016貪心策略選擇貪心策略選擇貪心策略貪心策略1：按照：按照 ti 從小到大安排任務從小到大安排任務貪心策略貪心策略2：按照：按照 di ti 從小到大安排任務從小到大安排任務貪心策略貪心策略3：按照：按照 di 從小到大安排任務從小到大安排任務策略策略1 對某些實例得不到最優(yōu)解對某些實例得不到最優(yōu)解. 反例：反例：t1=1, d1=100, t2=10, d2=10 策略策略2 對某些實例得不到最優(yōu)解對某些實例得不到最優(yōu)解. 反例：反例：t1=1, d1=2, t2=10,

13、d2=10 17算法設計算法設計算法算法4.3 Schedule 輸入：輸入：A, T, D輸出：輸出：f 1. 排序排序A使得使得 d1 d2 dn 2. f(1)0 3. i2 3. while i n do 4. f(i)f(i 1)+ti 1 /任務任務i-1結束時刻是任務結束時刻是任務i開始時刻開始時刻 5. ii+1設計思想：按完成時間從早到晚安排任務，沒有空閑設計思想：按完成時間從早到晚安排任務，沒有空閑 18交換論證：正確性證明交換論證：正確性證明算法的解的性質：算法的解的性質： (1) 沒有空閑時間沒有空閑時間, 沒有逆序沒有逆序. (2) 逆序逆序 (i, j): f(i)

14、 dj 引理引理4.14.1 所有沒有逆序、沒有空閑時間的調(diào)度具有相同的所有沒有逆序、沒有空閑時間的調(diào)度具有相同的最大延遲最大延遲. . 證證: 設設 f 沒有逆序，在沒有逆序，在 f 中具有相同完成時間的客戶中具有相同完成時間的客戶i1, i2, , ik 必被連續(xù)安排必被連續(xù)安排. 在這在這k個客戶中最大延遲是最后一個客個客戶中最大延遲是最后一個客戶，被延遲的時間是戶，被延遲的時間是 與與 i1, i2, , ik 的排列次序無關的排列次序無關. dttkjij 1019交換論證交換論證證明思想：證明思想：從一個沒有空閑時間的最優(yōu)解出發(fā)，在不從一個沒有空閑時間的最優(yōu)解出發(fā)，在不改變最優(yōu)性的

15、條件下，轉變成沒有逆序的解改變最優(yōu)性的條件下，轉變成沒有逆序的解. 根據(jù)引理根據(jù)引理 1，這個解和算法的解具有相同的最大延遲這個解和算法的解具有相同的最大延遲. 證明要點證明要點(1) 相鄰逆序的存在性：如果一個最優(yōu)調(diào)度存在逆序，那么相鄰逆序的存在性：如果一個最優(yōu)調(diào)度存在逆序，那么存在存在 i n 使得使得 (i, i+1) 構成一個逆序構成一個逆序. (2) 交換相鄰的逆序交換相鄰的逆序 i 和和 j ，得到的解的調(diào)度仍舊最優(yōu)，得到的解的調(diào)度仍舊最優(yōu). (3) 每次交換后逆序數(shù)減每次交換后逆序數(shù)減1，至多經(jīng)過，至多經(jīng)過 n(n 1)/2 次交換得到次交換得到一個沒有逆序的最一個沒有逆序的最

16、優(yōu)調(diào)度優(yōu)調(diào)度.定理定理4.3 在一個沒有空閑時間的最優(yōu)解中，最大延遲是在一個沒有空閑時間的最優(yōu)解中，最大延遲是r，如果僅對具有相鄰逆序的客戶進行交換，得到的解的最大如果僅對具有相鄰逆序的客戶進行交換，得到的解的最大延遲不會超過延遲不會超過r。20delay(f,i)=stj+ti di delya(f,j) rdelay(f, j)s+ti+tjdj (1) 交換交換 i, j 對其他客戶的延遲時間沒影響對其他客戶的延遲時間沒影響(2) 交換后不增加交換后不增加 j 的延遲的延遲(3) i 在在 f 的延遲的延遲delay(f,i)小于小于 j 在在 f 的延遲的延遲 delay(f,j),

17、因此小于因此小于f 的最大延遲的最大延遲 rdj di L2i 2得到最優(yōu)解的判定條件得到最優(yōu)解的判定條件定理定理4.6 對每個正整數(shù)對每個正整數(shù)k，假設對所有非負整數(shù)，假設對所有非負整數(shù) y 有有Gk(y)=Fk(y)且存在且存在 p 和和 滿足滿足 vk+1=pvk , 其中其中0 pw3 v3=pv2 p=3, =1. w3+G2( )=1+1 = 2 pw2=31=3 w3+G2( ) p w2結論結論：G3(y)=F3(y), 對于對于y=pv3=28，G4(y)F4(y) 274.4 貪心法的典型應用貪心法的典型應用4.4.1 最優(yōu)前綴碼最優(yōu)前綴碼二元前綴碼二元前綴碼用用0-1字符

18、串作為代碼表示字符，要求任何字符的代碼都字符串作為代碼表示字符，要求任何字符的代碼都不能作為其它字符代碼的前綴不能作為其它字符代碼的前綴非前綴碼的例子非前綴碼的例子 a: 001, b: 00, c: 010, d: 01解碼的歧義，例如字符串解碼的歧義，例如字符串 0100001 解碼解碼1: 01, 00, 001 d, b, a 解碼解碼2: 010, 00, 01 c, b, d 前綴碼的二叉樹及權值前綴碼的二叉樹及權值前綴碼前綴碼： 00000, 00001, 0001, 001, 01, 100, 101, 11頻率頻率: 00000: 5%, 000001: 5%, 0001:

19、10%, 001: 15%, 01: 25%, 100: 10%, 101: 10%, 11: 20% 平均的二進制位數(shù)平均的二進制位數(shù) B=(5+5)5+104 +(15+10+10)3 +(25+20)2/100 =2.85 最優(yōu)前綴碼最優(yōu)前綴碼 權值權值B最小最小 )()(1 niiixdxfB最優(yōu)前綴碼問題最優(yōu)前綴碼問題例例4.6 最優(yōu)前綴碼最優(yōu)前綴碼 給定字符集給定字符集 C=x1, x2, , xn和每個字符和每個字符的頻率的頻率f(xi), i=1,2,n, 求關于求關于C 的一個最優(yōu)前綴碼的一個最優(yōu)前綴碼. 算法算法4.4 Huffman(C) 輸入：輸入：C=x1, x2,

20、, xn， f(xi), i=1, 2, , n. 輸出：輸出：Q / /隊列隊列 1. n|C| 2. QC /按頻率遞增構成隊列按頻率遞增構成隊列Q 3. for i1 to n 1 do 4. zAllocate-Node() / 生成結點生成結點 z 5. z.leftQ中最小元中最小元 / 取出取出Q最小元作最小元作z的左兒子的左兒子 6. z.rightQ中最小元中最小元 / 取出取出Q最小元作最小元作z的右兒子的右兒子 7. f(z)f(x)+f(y) 8. Insert(Q,z) / 將將 z 插入插入Q 9. return Q30例如例如 a:45, b:13; c:12;

21、d:16; e:9; f:5 平均位數(shù)：平均位數(shù)：4 (0.05+0.09)+3 (0.16+0.12+0.13)+1 0.45= 2.24編碼：編碼：f-0000, e-0001, d-001, c-010, b011, a-1fe14dcb253055100a5916121345實例實例31則則T與與T 的權之差為的權之差為其中其中dT(i)為為i 在在T 中的層數(shù)（中的層數(shù)（i 到根的距離）到根的距離） CiCiTTidifidifTBTB0)()() ()(引理引理4.2 設設C是字符集，是字符集， c C, f(c)為頻率，為頻率，x, y C, f(x), f(y) 頻率最小，那么

22、存在最優(yōu)二元前綴碼使得頻率最小，那么存在最優(yōu)二元前綴碼使得 x, y 的碼字等長，的碼字等長，且僅在最后一位不同且僅在最后一位不同. TTfx fafy fba與與 x 交換交換b與與 y 交換交換yabxTbxyaT算法正確性證明算法正確性證明:引理引理4.232引理引理4.3引理引理4.3 設設 T 是二元前綴碼所對應的二叉樹，是二元前綴碼所對應的二叉樹， x, y T, x, y是是樹葉兄弟，樹葉兄弟，z 是是 x, y 的父親，令的父親，令T = T x, y, 且令且令 z 的頻率的頻率 f(z) = f(x)+f(y)，T是對應于二元前綴碼是對應于二元前綴碼 C = (C x, y

23、) z 的二叉樹，那么的二叉樹，那么 B(T)=B(T)+f(x)+f(y). )()() ()()()()()()()()()()()()()()()(, ,yfxfTByfxfzdzfidifydyfxdxfidifidifTBTziTiTTTyxiTiTTiT 證證 c C x,y,有有 dT(c) = dT (c) f(c)dT(c)=f(c)dT (c) dT(x) = dT(y) = dT (z) +1. 33定理定理4.7 Haffman 算法對任意規(guī)模為算法對任意規(guī)模為n（n 2）的字符集）的字符集C 都都得到關于得到關于C 的最優(yōu)前綴碼的二叉樹的最優(yōu)前綴碼的二叉樹. 證明：歸

24、納法證明：歸納法歸納基礎歸納基礎 n=2，字符集，字符集C=x1,x2，Huffman算法得到的代碼算法得到的代碼是是0和和1，是最優(yōu)前綴碼，是最優(yōu)前綴碼.歸納步驟歸納步驟 假設假設Huffman算法對于規(guī)模為算法對于規(guī)模為k 的字符集都得到最的字符集都得到最優(yōu)前綴碼優(yōu)前綴碼. 考慮規(guī)模為考慮規(guī)模為k+1的字符集的字符集C=x1, x2, ., xk+1, 其中其中x1, x2 C是頻率最小的兩個字符是頻率最小的兩個字符. 令令 C=(Cx1,x2) z， f(z)=f(x1)+f(x2)根據(jù)歸納假設，根據(jù)歸納假設，Huffman算法得到一棵關于字符集算法得到一棵關于字符集C 、頻率、頻率f(

25、z)和和f(xi)（i=3,4,.,k+1）的最優(yōu)前綴碼的二叉樹）的最優(yōu)前綴碼的二叉樹T.34把把x1和和 x2作為作為 z 的兒子附加到的兒子附加到T上，得到樹上，得到樹T，那么，那么T是關于是關于字符集字符集C=(Cz) x1,x2 的最優(yōu)前綴碼的二叉樹的最優(yōu)前綴碼的二叉樹. 如若不然，存在更優(yōu)的樹如若不然，存在更優(yōu)的樹T*. 根據(jù)引理根據(jù)引理1，其最深層樹葉是，其最深層樹葉是x1, x2，且，且B(T*)B(T). 去掉去掉T*中的中的x1和和x2，根據(jù)引理，根據(jù)引理2，所得，所得二叉樹二叉樹T*滿足滿足 B(T*)B(T*)(f(x1)+f(x2)B(T)(f(x1)+f(x2) =B

26、(T)與與T是一棵關于是一棵關于C的最優(yōu)前綴碼的二叉樹矛盾的最優(yōu)前綴碼的二叉樹矛盾. 證明：歸納法證明：歸納法(續(xù)續(xù))zTx2x1Tz Huffman樹應用樹應用: :文件歸并文件歸并例例4.7 問題：給定一組不同長度的排好序文件構成的集合問題：給定一組不同長度的排好序文件構成的集合 S = f1, , fn 其中其中 fi 表示第表示第 i 個個文件含有的項數(shù)文件含有的項數(shù). 使用二分歸并將這些文件使用二分歸并將這些文件歸并成一個有序的文件歸并成一個有序的文件. 歸并過程對應于二叉樹：文件為樹葉歸并過程對應于二叉樹：文件為樹葉. fi與與fj 歸并的文件是它歸并的文件是它們的父結點們的父結點

27、. 歸并代價歸并代價(最多的比較次數(shù)最多的比較次數(shù))：結點：結點 fi與與 fj 歸并代價為歸并代價為 fi+fj 1. 總的代價：每個文件總的代價：每個文件(樹葉樹葉)的深度乘以文件大小之和再減掉的深度乘以文件大小之和再減掉歸并次數(shù)歸并次數(shù) n 135)1()( nfidiSi36實例實例順序歸并順序歸并323110702141187388104192212818701032414973119192Huffman樹歸并樹歸并代價代價順序歸并：順序歸并： (21+10+32+41) 3+(18+70) 2 5=483Huffman樹歸并：樹歸并：(10+18) 4+21 3+(70+41+32

28、) 2 5=456實例：實例：S = 21,10,32,41,18,70 37無向連通帶權圖無向連通帶權圖G=(V,E,W)，w(e) W是邊是邊e的權的權. G的一棵的一棵生成樹是包含了生成樹是包含了G的所有頂點的樹的所有頂點的樹, 樹中各邊的權之和稱為樹中各邊的權之和稱為樹的權，具有最小權的生成樹稱為樹的權，具有最小權的生成樹稱為G的的最小生成樹最小生成樹. 命題命題4.1 設設G是是 n階連通圖，那么階連通圖，那么(1) T是是G 的生成樹當且僅當?shù)纳蓸洚斍覂H當 T 有有n1條邊條邊. (2) 如果如果T是是G的生成樹，的生成樹，e T，那么，那么T e含有一個圈含有一個圈 (回回 路

29、路). 問題：給定連通帶權圖問題：給定連通帶權圖G，求，求G的一棵最小生成樹的一棵最小生成樹. 算法：算法：Prim算法算法和和Kruskal算法算法 4.4.2 最小生成樹最小生成樹12435661556365421243566155636542364251Prim算法算法 算法算法4.5 Prim(G,E,W) 1S1；T 2while V S do 3 從從V S中選擇中選擇 j 使得使得 j 到到 S 中頂點的邊中頂點的邊e的權最小的權最小 4 SS j, T T e 39對步數(shù)歸納對步數(shù)歸納定理定理4.8 對于任意對于任意 k 1, 算法對算法對 n 階圖得到一棵最小生成樹階圖得到一

30、棵最小生成樹.證明證明 n=2, 只有一條邊，命題顯然為真只有一條邊，命題顯然為真. 假設對于假設對于n個頂點的圖算法正確，考慮個頂點的圖算法正確，考慮n+1個頂點的圖個頂點的圖G, G中最小權邊中最小權邊 e = i, j，從從G 中中短接短接 i 和和 j，得到圖得到圖G. 根根據(jù)歸納假設，由算法存在據(jù)歸納假設，由算法存在G 的最小生成樹的最小生成樹T.令令T=T e, 則則T 是關于是關于G 的最小生成樹的最小生成樹. 否則存在否則存在G 的含邊的含邊e 的最小生成樹的最小生成樹T*，W(T*)W(T). (如果如果 e T*, 在在T*中加邊中加邊e，形成回路，形成回路. 去掉回路中任

31、意別的邊去掉回路中任意別的邊所得生成樹的權仍舊最小所得生成樹的權仍舊最小). 在在T*中短接中短接 e 得到得到G 的生成的生成樹樹T* e, 且且 W(T* e)=W(T*) w(e)W(T) w(e )=W(T)， 與與T 的最優(yōu)性矛盾的最優(yōu)性矛盾. Kruskal算法正確性證明算法正確性證明算法的實現(xiàn)與時間復雜度算法的實現(xiàn)與時間復雜度數(shù)據(jù)結構：數(shù)據(jù)結構：建立建立FIND數(shù)組，數(shù)組，F(xiàn)INDi 是結點是結點 i 的連通分支標記的連通分支標記. (1) 初始初始FINDi=i. (2) 兩個連通分支合并，則將較小分支結點的兩個連通分支合并，則將較小分支結點的FIND值更新為值更新為 較大分支

32、的標記較大分支的標記時間復雜度：時間復雜度：(1) 每個結點至多更新每個結點至多更新logn次，建立和更新次，建立和更新FIND數(shù)組的總時數(shù)組的總時 間為間為O(nlogn)(2) 算法時間為算法時間為 O(mlogm) + O(nlogn) + O(m) = O(mlogn) 邊排序邊排序 FIND數(shù)組數(shù)組 其他其他45給定帶權有向網(wǎng)絡給定帶權有向網(wǎng)絡G=(V,E,W),每條邊每條邊e=的權的權w(e)為非為非負實數(shù)，表示從負實數(shù)，表示從i到到j 的距離的距離. 源源點點s V，求從，求從 s 出發(fā)到達其出發(fā)到達其它結點的最短路徑它結點的最短路徑.Dijkstra算法：算法： x S x V

33、 且從且從 s 到到 x 的最短路徑長度已知的最短路徑長度已知初始：初始：S=s ，S=V 時算法結束時算法結束從從 s 到到 u 相對于相對于S 的最短路徑：從的最短路徑：從 s 到到 u且僅經(jīng)過且僅經(jīng)過S 中頂點中頂點的最短路徑的最短路徑distu：從：從 s 到到 u 的相對于的相對于S 的最短路徑的長度的最短路徑的長度shortu：從：從 s 到到 u 的最短路徑的長的最短路徑的長distu shortu 4.4.3 單源最短路徑單源最短路徑46 Dijkstra算法算法算法算法4.7 Dijkstra輸入：帶權有向圖輸入：帶權有向圖G=，源點，源點s V輸出：從輸出：從 s 到每個結

34、點到每個結點 i 的最短路徑的最短路徑 1. Ss 2. dists0 3. for i V s do 4. distiw(s,i) / 如果如果s到到i沒有邊沒有邊, w(s,i)= 5. while V S do 6. 從從V S中取出具有相對中取出具有相對S的最短路徑的頂點的最短路徑的頂點 j 7. SS j; 8. for i V S do 9. if distj+w(j,i)disti 10. then disti distj+w(j,i) / 更新更新disti47S=1, dist1=0 dist2=10, dist6=3 dist3=dist4=dist5= 實例實例10416

35、54337376122510416543373761225S=1,6, dist1=0, dist6=3 dist2=5, dist4=9, dist5=4 dist3= 輸入：輸入：G=，源點，源點 1V=1, 2, 3, 4, 5, 648S=1,6,5, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9, dist3= 實例（續(xù)）實例（續(xù)）1041654337376122510416543373761225S=1,6,5,2, dist1=0, dist6=3, dist5=4 dist2=5 dist3=12 dist4=9 49S=1,6,5,2,

36、4, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9, dist3=12 實實 例（續(xù)）例（續(xù)）1041654337376122510416543373761225S=1,6,5,2,4,3, dist1=0, dist6=3, dist5=4 dist2=5, dist4=9 dist3=12 解：解：short1=0, short2=5,short3=12, short4=9，short5=4, short6=3. 50 算法正確性證明算法正確性證明定理定理4.10 當算法進行到第當算法進行到第 k 步時，對于步時，對于S 中每個結點中每個結點 i，

37、disti = shorti 歸納基礎歸納基礎 k=1, S=s, dists=shorts=0, 命題為真命題為真.歸納步驟歸納步驟 假設命題對于假設命題對于k 為真為真. 考慮考慮 k+1步步, 選擇頂點選擇頂點v (邊邊u,v). 假若存在另一條假若存在另一條 s-v 路徑路徑 L (綠色綠色)，最后一次出，最后一次出S 的的頂點為頂點為 x, 在這次從在這次從S 中出來后中出來后經(jīng)過經(jīng)過V S 的第一個頂點為的第一個頂點為 y.時間復雜度時間復雜度 T(n)=O(n2)distv=shortvsuxyvLSdistv disty /v先被選先被選 disty+d(y,v) L 51 貪

38、心法小結貪心法小結(1) 適用于組合優(yōu)化問題，適用于組合優(yōu)化問題， 求解過程是多步判斷求解過程是多步判斷. 判斷的依據(jù)判斷的依據(jù)是局部最優(yōu)策略，使目標值達到最大是局部最優(yōu)策略，使目標值達到最大(或最小或最小)，與前面的，與前面的子問題計算結果無關子問題計算結果無關. (2) 局部最優(yōu)策略的選擇是算法正確性的關鍵局部最優(yōu)策略的選擇是算法正確性的關鍵. (3) 正確性證明方法：數(shù)學歸納法、交換論證正確性證明方法：數(shù)學歸納法、交換論證. 使用數(shù)學歸納使用數(shù)學歸納 法主要通過對算法步數(shù)或者問題規(guī)模進行歸納法主要通過對算法步數(shù)或者問題規(guī)模進行歸納. 如果要證如果要證 明貪心策略是錯誤的，只需舉出反例明貪

39、心策略是錯誤的，只需舉出反例. (4) 自頂向下求解，通過選擇將問題歸約為小的子問題自頂向下求解，通過選擇將問題歸約為小的子問題. (5) 如果貪心法得不到最優(yōu)解，可以對問題的輸入進行分析如果貪心法得不到最優(yōu)解，可以對問題的輸入進行分析 或者估計算法的近似比或者估計算法的近似比. (6) 如果對原始數(shù)據(jù)排序之后，貪心法往往是一輪處理，時如果對原始數(shù)據(jù)排序之后，貪心法往往是一輪處理，時 間復雜度和空間復雜度低間復雜度和空間復雜度低. 52 不同算法策略特點不同算法策略特點(1) 貪心法：貪心法：通過局部最優(yōu)決策到達全局最優(yōu)決策通過局部最優(yōu)決策到達全局最優(yōu)決策 (2) 遞推法：遞推法：由當前問題的

40、逐步解決從而得到整個問題的解，它依賴信由當前問題的逐步解決從而得到整個問題的解，它依賴信息間遞推關系，由小到大。息間遞推關系，由小到大。(3) 遞歸法：遞歸法：利用大問題與其子問題間的遞推關系。將大問題分解成規(guī)利用大問題與其子問題間的遞推關系。將大問題分解成規(guī)模較小的問題，然后從小問題的解構造出大問題的解。模較小的問題，然后從小問題的解構造出大問題的解。 (4) 枚舉法：枚舉法：逐一嘗試。逐一嘗試。(5) 遞歸回溯法：遞歸回溯法：通過遞歸嘗試遍歷問題各個可能解的通路，不同時通過遞歸嘗試遍歷問題各個可能解的通路，不同時回溯上一步?；厮萆弦徊?。 (6) 分治法：分治法：復雜問題分解成獨立子問題并解

41、決，再將它們的解合成。復雜問題分解成獨立子問題并解決，再將它們的解合成。(7) 動態(tài)規(guī)劃法：動態(tài)規(guī)劃法：保留多個階段的決策結果，為以后每個階段提供決保留多個階段的決策結果，為以后每個階段提供決策；問題不能分為獨立階段，且符合最優(yōu)化原理；解決子問題冗余。策；問題不能分為獨立階段，且符合最優(yōu)化原理；解決子問題冗余。53 算法策略間的關聯(lián)算法策略間的關聯(lián)(1)對問題進行分解的算法策略：對問題進行分解的算法策略：分治法、動態(tài)規(guī)劃分治法、動態(tài)規(guī)劃(2)多階段逐步解決問題的策略：多階段逐步解決問題的策略：貪心法、遞推法、遞貪心法、遞推法、遞歸法、動態(tài)規(guī)劃歸法、動態(tài)規(guī)劃(3)全面逐一嘗試：全面逐一嘗試：枚舉

42、法、遞歸回溯法枚舉法、遞歸回溯法整數(shù)的分劃問題整數(shù)的分劃問題( (較復雜的遞歸設計較復雜的遞歸設計) )對于一個正整數(shù)對于一個正整數(shù)n n的分劃就是把的分劃就是把n n寫成一系列正整數(shù)之和的表達寫成一系列正整數(shù)之和的表達式。例如，對于正整數(shù)式。例如，對于正整數(shù)n=6n=6，它可以分劃為：它可以分劃為： 6 6 5+1 5+1 4+2, 4+1+1 4+2, 4+1+1 3+3, 3+2+1, 3+1+1+1 3+3, 3+2+1, 3+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 2+2, 2+2+1+1, 2+1+1+1+1 1+1+1+1+1+11+1+1+1+1+1 根據(jù)例

43、子發(fā)現(xiàn)根據(jù)例子發(fā)現(xiàn)“包括第一行以后的數(shù)據(jù)不超過包括第一行以后的數(shù)據(jù)不超過6 6，包括，包括第二行的數(shù)據(jù)不超過第二行的數(shù)據(jù)不超過5 5，第六行的數(shù)據(jù)不超過，第六行的數(shù)據(jù)不超過1”1”。 因此，定義一個函數(shù)因此，定義一個函數(shù)Q(n,m)Q(n,m)，表示整數(shù)表示整數(shù)n n的的“任何被加任何被加數(shù)都不超過數(shù)都不超過m”m”的分劃的數(shù)目，的分劃的數(shù)目，n n的所有分劃的數(shù)目的所有分劃的數(shù)目P(n)=Q(n,n)P(n)=Q(n,n)。模型建立模型建立 一般地一般地Q(n,mQ(n,m) )有以下遞歸關系：有以下遞歸關系： 1)Q(n,n)=1+Q(n,n-1) 1)Q(n,n)=1+Q(n,n-1)

44、（m=nm=n）Q(n,n-1)Q(n,n-1)表示表示n n的所有其他分劃，即最大被加數(shù)的所有其他分劃，即最大被加數(shù)m=n-1m=n-1的劃分。的劃分。2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (mn)2)Q(n,m)=Q(n,m-1)+Q(n-m,m) (m1/27/81/2， 7/8-1/21/37/8-1/21/3， 7/8-1/2-1/3=1/247/8-1/2-1/3=1/24。過程如下：過程如下： 1)1)找最小的找最小的n n（也就是最大的埃及分數(shù)），使分數(shù)也就是最大的埃及分數(shù)），使分數(shù)f1/nf1/n； 2)2)輸出輸出1/n1/n； 3)3)計算計算f=f-1/

45、nf=f-1/n； 4)4)若此時的若此時的f f是埃及分數(shù)，輸出是埃及分數(shù)，輸出f,f,算法結束算法結束, ,否則返回否則返回1 1）。）。 數(shù)學模型數(shù)學模型 記真分數(shù)記真分數(shù)F=A/BF=A/B；對；對B/AB/A進行整除運算進行整除運算, ,商為商為D, D, 余數(shù)為余數(shù)為0 0K KA A，它們之間的關系及導出關系如下：它們之間的關系及導出關系如下：( (例：例：A=7,B=8 = D=1,K=1)A=7,B=8 = D=1,K=1) B=AB=A* *D+KD+K，B/A=D+K/AB/A=D+K/AD+1D+1，A/BA/B1/(D+1)1/(D+1)，記，記C=D+1C=D+1。

46、 這樣我們就找到了分數(shù)這樣我們就找到了分數(shù)F F所包含的所包含的“最大的最大的”埃及分數(shù)就是埃及分數(shù)就是1/C1/C。進一步計算：進一步計算： A/B-1/C=A/B-1/C=（A A* *C-BC-B）/B/B* *C C 也就是說繼續(xù)要解決的是有關也就是說繼續(xù)要解決的是有關分子為分子為A=AA=A* *C-BC-B, ,分母為分母為B=BB=B* *C C的的問題。問題。 算法設計算法設計 由以上數(shù)學模型，真正的由以上數(shù)學模型，真正的算法過程算法過程如下：如下： 1)1)設某個真分數(shù)的分子為設某個真分數(shù)的分子為A(1A(1），），分母為分母為B B； 2)2)把把B B除以除以A A的商的

47、整數(shù)部分加的商的整數(shù)部分加1 1后的值作為埃及后的值作為埃及 分數(shù)的一個分母分數(shù)的一個分母C;C; 3) 3)輸出輸出1/C1/C； 4)4)將將A A乘以乘以C C減去減去B B作為新的作為新的A A； 5)5)將將B B乘以乘以C C作為新的作為新的B B； 6)6)如果如果A A大于大于1 1且能整除且能整除B,B,則最后一個分母為則最后一個分母為B/AB/A； 7)7)如果如果A A1,1,則最后一個分母為則最后一個分母為B;B;否則轉步驟否則轉步驟(2).(2). 例：例：7/8=1/2+1/3+1/247/8=1/2+1/3+1/24的解題步驟：的解題步驟： 同樣用變量同樣用變量A

48、 A表示分子，變量表示分子，變量B B表示分母；表示分母； C=8/7+1=2 C=8/7+1=2 / /說明說明7/81/27/81/2， 打印打印1/21/2 A=7A=7* *2-8=62-8=6，B=BB=B* *C=16C=16/在計算在計算7/8-1/2=(77/8-1/2=(7* *2-8)/(72-8)/(7* *2)=6/16=A/B2)=6/16=A/B C=16/6+1=3 C=16/6+1=3 / /說明說明16/61/316/61/3，打印，打印1/31/3 A=6A=6* *3-16=2,B=B3-16=2,B=B* *C=16C=16* *3=483=48/在計算

49、在計算6/16-1/3=(66/16-1/3=(6* *3-16)/(163-16)/(16* *3)=2/48=A/B3)=2/48=A/B A1 A1但但B/AB/A為整數(shù)為整數(shù)2424，打印，打印1/24 1/24 結束結束. .算法實現(xiàn)算法實現(xiàn)main（）（） int a,b,c; print(“input element”); input(a); print(“input denominator”); input(b); if(ab) print(“input error”); else if (a=1 or b mod a=0) print( a, /,b, = 1, /,b/a)

50、; else while(a1) c = b / a + 1 a = a * c b；b = b *c； print( 1/,c); if (b mod a =0 ) print (+1/; b / a); a=1; if( a 1) print(+); 取數(shù)游戲取數(shù)游戲 有2個人輪流取2n個數(shù)中的n個數(shù)，取數(shù)之和大者為勝。請編寫算法，讓先取數(shù)者勝，模擬取數(shù)過程。 問題分析 算法設計 算法說明 算法分析 問題分析問題分析 這個游戲一般假設取數(shù)者只能看到這個游戲一般假設取數(shù)者只能看到2n2n個數(shù)中兩邊的數(shù)個數(shù)中兩邊的數(shù), ,用貪婪算法的情況用貪婪算法的情況: : 若一組數(shù)據(jù)為：若一組數(shù)據(jù)為：6,

51、16,27,6,12,9,2,11,6,56,16,27,6,12,9,2,11,6,5。用貪婪策。用貪婪策略每次兩人都取兩邊的數(shù)中較大的一個數(shù)略每次兩人都取兩邊的數(shù)中較大的一個數(shù), ,先取者勝先取者勝. .以以A先先取為例：取為例： 取數(shù)結果為：取數(shù)結果為： A 6,27,12,5,11=61 A 6,27,12,5,11=61 勝勝 B 16,6,9,6,2=39B 16,6,9,6,2=39 但若選另一組數(shù)據(jù)：但若選另一組數(shù)據(jù)：16,27,7,12,9,2,11,616,27,7,12,9,2,11,6。仍都用貪婪。仍都用貪婪算法，先取者算法，先取者A A敗。敗。 取數(shù)結果為：取數(shù)結果為

52、： A 16,7,9,11=43A 16,7,9,11=43 B 27,12,6,2=47 B 27,12,6,2=47 勝勝 其實，若我們只能看到兩邊的數(shù)據(jù)，則此題無論其實，若我們只能看到兩邊的數(shù)據(jù)，則此題無論先取還先取還是后取都無必勝的策略是后取都無必勝的策略。這時一般的策略是用近似貪婪算法。這時一般的策略是用近似貪婪算法。 但但若取數(shù)者能看到全部若取數(shù)者能看到全部2n2n個數(shù)個數(shù)，則此問題可有一些簡單，則此問題可有一些簡單的方法，有的雖不能保證所取數(shù)的和是最大，但確是一個先的方法，有的雖不能保證所取數(shù)的和是最大，但確是一個先取者必勝的策略。取者必勝的策略。 數(shù)學模型建立：數(shù)學模型建立：N

53、個數(shù)排成一行，我們給這個數(shù)排成一行，我們給這N個數(shù)從左到右編號，個數(shù)從左到右編號，依次為依次為1，2，N，因為因為N為偶數(shù)，又因為是我們先取數(shù)，計為偶數(shù)，又因為是我們先取數(shù)，計算機后取數(shù)，所以一開始我們既可以取到一個奇編號的數(shù)（最算機后取數(shù)，所以一開始我們既可以取到一個奇編號的數(shù)（最左邊編號為左邊編號為1的數(shù)）又可以取到一個偶編號的數(shù)（最右邊編號的數(shù)）又可以取到一個偶編號的數(shù)（最右邊編號為為N的數(shù)）。的數(shù)）。 如果我們第一次取奇編號（編號為如果我們第一次取奇編號（編號為1）的數(shù)，則接著計算機）的數(shù)，則接著計算機只能取到偶編號（編號為只能取到偶編號（編號為2或或N）的數(shù)；的數(shù)； 如果我們第一次取

54、偶編號（編號為如果我們第一次取偶編號（編號為N）的數(shù)，則接著計算機的數(shù)，則接著計算機只能取到奇編號（編號為只能取到奇編號（編號為1或或N-1）的數(shù)；的數(shù)； 即無論我們第一次是取奇編號的數(shù)還是取偶編號的數(shù)，接著即無論我們第一次是取奇編號的數(shù)還是取偶編號的數(shù)，接著計算機只能取到另一種編號（偶編號或奇編號）的數(shù)。計算機只能取到另一種編號（偶編號或奇編號）的數(shù)。 這是對第一個回合的分析，顯然對以后整個取數(shù)過程都適這是對第一個回合的分析，顯然對以后整個取數(shù)過程都適用。也就是說，我們能夠控制讓計算機自始自終只取一種編號用。也就是說，我們能夠控制讓計算機自始自終只取一種編號的數(shù)。這樣，我們只要比較奇編號數(shù)之

55、和與偶編號數(shù)之和誰大，的數(shù)。這樣，我們只要比較奇編號數(shù)之和與偶編號數(shù)之和誰大，以決定最開始我們是取奇編號數(shù)還是偶編號數(shù)即可。（如果奇以決定最開始我們是取奇編號數(shù)還是偶編號數(shù)即可。（如果奇編號數(shù)之和與偶編號數(shù)之和同樣大，我們第一次可以任意取數(shù)，編號數(shù)之和與偶編號數(shù)之和同樣大，我們第一次可以任意取數(shù)，因為當兩者所取數(shù)和相同時，先取者為勝。因為當兩者所取數(shù)和相同時，先取者為勝。算法設計：算法設計：有了以上建立的高效數(shù)學模型，算法就很簡單了，算有了以上建立的高效數(shù)學模型，算法就很簡單了，算法只需要分別計算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就法只需要分別計算一組數(shù)的奇數(shù)位和偶數(shù)位的數(shù)據(jù)之和，然后就先

56、了取數(shù)者就可以確定必勝的取數(shù)方式了。先了取數(shù)者就可以確定必勝的取數(shù)方式了。以下面一排數(shù)為例：以下面一排數(shù)為例：1 2 3 10 5 6 7 8 9 4奇編號數(shù)之和為奇編號數(shù)之和為25（=1+3+5+7+9），小于偶編號數(shù)之和為），小于偶編號數(shù)之和為30（=2+10+6+8+4）。我們第一次?。?。我們第一次取4，以后，計算機取哪邊的數(shù)，以后，計算機取哪邊的數(shù)我們就取哪邊的數(shù)（如果計算機取我們就取哪邊的數(shù)（如果計算機取1，我們就取，我們就取2；如果計算機??；如果計算機取9，我們就取，我們就取8）。這樣可以保證我們自始自終取到偶編號的數(shù)，）。這樣可以保證我們自始自終取到偶編號的數(shù)，而計算機自始自終取

57、到奇編號的數(shù)。而計算機自始自終取到奇編號的數(shù)。背包問題背包問題 給定給定n種物品和一個容量為種物品和一個容量為C的背包，物的背包，物品品i的重量是的重量是wi，其價值為其價值為vi，背包問題是如何背包問題是如何選擇裝入背包的物品，使得裝入背包中物品的選擇裝入背包的物品，使得裝入背包中物品的總價值最大總價值最大? 于是，背包問題歸結為尋找一個滿足約束條于是，背包問題歸結為尋找一個滿足約束條件式件式1-1，并使目標函數(shù)式，并使目標函數(shù)式1-2達到最大的解向量達到最大的解向量X=(x1, x2, , xn)。設設xi表示物品表示物品i裝入背包的情況，根據(jù)問題的要求，裝入背包的情況，根據(jù)問題的要求，有

58、如下約束條件和目標函數(shù)：有如下約束條件和目標函數(shù)： )1 (101nixCxwiniii（式（式1-1）niiixv1max（式（式1-2）至少有三種看似合理的貪心策略： （1）選擇價值最大的物品，因為這可以盡可能快地增加背包的總價值。但是，雖然每一步選擇獲得了背包價值的極大增長，但背包容量卻可能消耗得太快，使得裝入背包的物品個數(shù)減少，從而不能保證目標函數(shù)達到最大。 （2）選擇重量最輕的物品，因為這可以裝入盡可能多的物品，從而增加背包的總價值。但是，雖然每一步選擇使背包的容量消耗得慢了，但背包的價值卻沒能保證迅速增長，從而不能保證目標函數(shù)達到最大。 （3）選擇單位重量價值最大的物品，在背包價值

59、增長和背包容量消耗兩者之間尋找平衡。 應用第三種貪心策略，每次從物品集合中選擇單位重量價值最大的物品，如果其重量小于背包容量，就可以把它裝入，并將背包容量減去該物品的重量，然后我們就面臨了一個最優(yōu)子問題它同樣是背包問題，只不過背包容量減少了，物品集合減少了。因此背包問題具有最優(yōu)子結構性質。 60 120 50 背包 180 190 200(a) 三個物品及背包 (b) 貪心策略1 (c) 貪心策略2 (d) 貪心策略3 50 30 10 20 20 3020/30 20 1010/20 30 10例如，有3個物品，其重量分別是20, 30, 10，價值分別為60, 120, 50，背包的容量為

60、50，應用三種貪心策略裝入背包的物品和獲得的價值如圖所示。 設背包容量為C，共有n個物品，物品重量存放在數(shù)組wn中，價值存放在數(shù)組vn中，問題的解存放在數(shù)組xn中。 算法算法背包問題背包問題1改變數(shù)組改變數(shù)組w和和v的排列順序，使其按單位重量價值的排列順序，使其按單位重量價值vi/wi降序排列；降序排列；2將數(shù)組將數(shù)組xn初始化為初始化為0； /初始化解向量初始化解向量3i=1; 4循環(huán)直到循環(huán)直到(wiC) 4.1 xi=1; /將第將第i個物品放入背包個物品放入背包 4.2 C=C-wi; 4.3 i+;5. xi=C/wi;算法的時間主要消耗在將各種物品依其單位重量的價值從算法的時間主要