《《算法設(shè)計與分析》第06章.ppt》由會員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計與分析》第06章.ppt（112頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、,第2部分 算法設(shè)計策略,,,6.1 一般方法 6.2 背包問題 6.3 帶時限的作業(yè)排序 6.4 最佳合并模式 6.5 最小代價生成樹 6.6 單源最短路徑 6.7 磁帶最優(yōu)存儲 6.8 貪心法的基本要素,第6章 貪心法,,最優(yōu)化問題（optimization problems）是指這樣一類問題，問題給定某些約束條件（constraint），滿足這些約束條件的問題解稱為可行解（feasible solution）。通常滿足約束條件的解不是惟一的。為了衡量可行解的好壞，問題還給出了某個數(shù)值函數(shù)，稱為目標函數(shù)（objective function），使目標函數(shù)取最大（或最小）值的可行解稱為最優(yōu)解

2、（optimal solution）。,6.1 一般方法,,貪心法是通過分步?jīng)Q策（stepwise decision）的方法來求解問題的。 貪心法每一步上用作決策依據(jù)的選擇準則被稱為最優(yōu)量度標準（optimization criterion）。 在根據(jù)最優(yōu)量度標準選擇分量的過程中，還需要使用一個可行解判定函數(shù)。 貪心策略并不是從整體上加以考慮的，它所做出的選擇只是當前看似最佳選擇，必須進一步證明該算法最終導致問題的一個整體最優(yōu)解。,,貪心技術(shù)(Greedy Technique),某一問題的n個輸入,該問題的一種解（可行解）,,是A的一 個子集,滿足一定 的條件,約束條件,,目標函數(shù),,取極值,

3、最優(yōu)解,,【程序61】貪心法 SolutionType Greedy(SType a,int n) SolutionType solution=; for(int i=0;i

4、,d4=1，n=48 該問題的一個解是： 1個25，2個10，3個1，且該解是最優(yōu)的。 這種方法稱為貪心法，建議通過一系列步驟來構(gòu)造問題的解，每一步對目前構(gòu)造的部分解做一個擴展，直到獲得問題的完全解。 必須滿足：可行、局部最優(yōu)、不可取消,,8,又如：d1=11,d2=5,d3=1,n=15 該問題的一個解是： 1個11，4個1，該解不是最優(yōu)的。 最優(yōu)解：3個5 本質(zhì)上由硬幣面值種類決定（問題其本身固有的特點） 。,,貪心策略最優(yōu)解的證明,基本思想 設(shè)X=x1,x2,...,xn為貪心策略得到的解 設(shè)Y=y1,y2,...,yn為該問題的最優(yōu)解 很明顯，XY，

5、如果成立，則不用證明了。 證明過程： 依次比較X和Y中的每個元素，如果發(fā)現(xiàn)不一樣，則用X中的替換Y中相應(yīng)元素，比較完后得到一個新的解Y=X 此時，如能證明Y的最優(yōu)值就是Y的最優(yōu)值或者比Y還好，則說明X就是最優(yōu)解。,,問題 對容量為M的背包進行最佳裝載的問題。,6.2 背包問題,,6.2.1 問題描述,已知一個載重為M的背包和n件物品，第i件物品的重量為 wi，如果將第i件物品全部裝入背包，將有收益pi，這里，wi0，pi0，0i

6、或者不裝入，稱為 0/1背包問題；如果物品是可以分割的，也就是允許將其中的一部分裝入背包為一般背包問題或簡稱背包問題。,,,,,6.2.2 貪心法求解,背包問題 背包問題的解可以表示成一個n-元組：X=(x0,x1,,xn1)，0 xi1，0i

7、品價值降序裝包,方案2：按物品重量升序裝包,方案3：按物品價值與重量比值的降序裝包,,,【程序62】背包問題的貪心算法 template class Knapsack public: Knapsack(int mSize,float cap,float *wei,T *prof); void GreedyKnapsack(float* x); private: float m,*w; T *p; int n; ;,,template void Knapsack::GreedyKnapsack(float* x) //前置條件：wi已按pi/

8、wi的非增次序排列 float u=m; for (int i=0;iu) break; xi=1.0; u=u-wi; if (i<=n) xi=u/wi; ,,6.2.3 算法正確性,定理61 如果p0/w0p1/w1pn1/wn1，則程序62求得的背包問題的解是最優(yōu)解。,,,,證明： 設(shè)X=(x0, x1, , xn-1)， 0 xj 1 ,0in是貪心背包算法所生成的貪心解。 如果所有的xi都等于1,則顯然X就是問題的最優(yōu)解。否則， 設(shè)j是使xi1的最小下標。由算法的執(zhí)行過程可知， 解的形式為： X=(1, , 1,xj,0, , 0)

9、 即xi=1 0ij, 0 xj 1,xi=0 jin-1,,,假設(shè)Y是問題的最優(yōu)解：Y=(y0, y1, , yn-1) 且有： 若X Y，則X就是最優(yōu)解。否則， X和Y至少在1個分量上存在不同。 設(shè)k是使得yk xk的最小下標，則有yk xk?？煞忠韵虑闆r說明： a) 若k

10、k ，因為ykxk,為保持解的可行性，必須從(yk+1,,yn-1)中減去同樣多的量。設(shè)調(diào)整后的解為Z=(z0, z1, ,zk,zk+1, , zn-1)，其中zixi，0ik，且有： Z的效益值有：,差值0,,由以上分析得， 若 ，則Y將不是最優(yōu)解； 若 ，則或者Z=X，則X就是最優(yōu)解； 或者ZX，則重復以上替代過程，或者證明Y不是最優(yōu)解，或者把Y轉(zhuǎn)換成X，從而證明X是最優(yōu)解,,最優(yōu)裝載,有一批集裝箱要裝上一艘載重量為c的輪船。其中集裝箱i的重量為Wi。最優(yōu)裝載問題要求確定在裝載體積不受限制的情況下，將盡可能多的集裝箱裝上輪船。 1.算法描述 最優(yōu)裝載

11、問題可用貪心算法求解。采用重量最輕者先裝的貪心選擇策略，可產(chǎn)生最優(yōu)裝載問題的最優(yōu)解。具體算法描述如下頁。,,template void Loading(int x, Type w, Type c, int n) int *t = new int n+1; Sort(w, t, n); for (int i = 1; i <= n; i++) xi = 0; for (int i = 1; i <= n ,,2.貪心選擇性質(zhì) 可以證明最優(yōu)裝載問題具有貪心選擇性質(zhì)。 3.最優(yōu)子結(jié)構(gòu)性質(zhì) 最優(yōu)裝載問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。 由最優(yōu)裝載問題的貪心選擇性質(zhì)和最優(yōu)子結(jié)構(gòu)性質(zhì)，容易證明算

12、法loading的正確性。 算法loading的主要計算量在于將集裝箱依其重量從小到大排序，故算法所需的計算時間為 O(nlogn)。,,活動安排問題,活動安排問題就是要在所給的活動集合中選出最大的相容活動子集合，是可以用貪心算法有效求解的很好例子。該問題要求高效地安排一系列爭用某一公共資源的活動。貪心算法提供了一個簡單、漂亮的方法使得盡可能多的活動能兼容地使用公共資源。,,設(shè)有n個活動的集合E=1,2,,n，其中每個活動都要求使用同一資源，如演講會場等，而在同一時間內(nèi)只有一個活動能使用這一資源。每個活動i都有一個要求使用該資源的起始時間si和一個結(jié)束時間fi,且si

13、動i，則它在半開時間區(qū)間si, fi)內(nèi)占用資源。若區(qū)間si, fi)與區(qū)間sj, fj)不相交，則稱活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。,,template void GreedySelector(int n, Type s, Type f, bool A) A1=true; int j=1; for (int i=2;i=fj) Ai=true; j=i; else Ai=false; ,下面給出解活動安排問題的貪心算法GreedySelector :,各活動的起始時間和結(jié)束時間存儲于數(shù)組s和f中且按結(jié)束時間的非減序排列,,由于

14、輸入的活動以其完成時間的非減序排列，所以算法greedySelector每次總是選擇具有最早完成時間的相容活動加入集合A中。直觀上，按這種方法選擇相容活動為未安排活動留下盡可能多的時間。也就是說，該算法的貪心選擇的意義是使剩余的可安排時間段極大化，以便安排盡可能多的相容活動。 算法greedySelector的效率極高。當輸入的活動已按結(jié)束時間的非減序排列，算法只需O(n)的時間安排n個活動，使最多的活動能相容地使用公共資源。如果所給出的活動未按非減序排列，可以用O(nlogn)的時間重排。,,例：設(shè)待安排的11個活動的開始時間和結(jié)束時間按結(jié)束時間的非減序排列如下：,,算法greedySe

15、lector 的計算過程如左圖所示。圖中每行相應(yīng)于算法的一次迭代。陰影長條表示的活動是已選入集合A的活動，而空白長條表示的活動是當前正在檢查相容性的活動。,,若被檢查的活動i的開始時間Si小于最近選擇的活動j的結(jié)束時間fi，則不選擇活動i，否則選擇活動i加入集合A中。 貪心算法并不總能求得問題的整體最優(yōu)解。但對于活動安排問題，貪心算法greedySelector卻總能求得的整體最優(yōu)解，即它最終所確定的相容活動集合A的規(guī)模最大。這個結(jié)論可以用數(shù)學歸納法證明。,,6.3.1 問題描述,設(shè)有一個單機系統(tǒng)、無其它資源限制且每個作業(yè)運行相等時間，不妨假定每個作業(yè)運行1個單位時間?，F(xiàn)有n個作業(yè)，每個作業(yè)

16、都有一個截止期限di0，di為整數(shù)。如果作業(yè)能夠在截止期限之內(nèi)完成，可獲得pi0的收益。問題要求得到一種作業(yè)調(diào)度方案，該方案給出作業(yè)的一個子集和該作業(yè)子集的一種排列，使得若按照這種排列次序調(diào)度作業(yè)運行，該子集中的每個作業(yè)都能如期完成，并且能夠獲得最大收益。也就是說這種作業(yè)調(diào)度是最優(yōu)的。,,,6.3 帶時限的作業(yè)排序,,6.3.2 貪心法求解,例62 設(shè)有4個作業(yè)，每個作業(yè)的時限為(d0,d1,d2,d3)=(2,1,2,1),收益為(p0,p1,p2,p3)=(100,10,15,27)。,,,,,【程序63】帶時限作業(yè)排序的貪心算法 void GreedyJob(int d, Set X,

17、int n) //前置條件：p0p1,,pn-1 X=0; for (int i=1;i

18、 (由算法的處理規(guī)則可得：對于在Y中而不在X中的作業(yè)所有b，有：papb),,設(shè)和分別是X和Y的可行的調(diào)度表。因為X和Y都是可行解，故這樣的調(diào)度表一定存在； 設(shè)x是既屬于X又屬于Y的一個作業(yè)，并設(shè)x在調(diào)度表中的調(diào)度時刻是t，t+1，而在中的調(diào)度時刻是t，t+1。 在X和Y中作如下調(diào)整： 若tt，則將中在t，t+1時刻調(diào)度的那個作業(yè)（如果有的話）與x相交換。如果X中在t，t+1時刻沒有作業(yè)調(diào)度，則直接將x移到t，t+1調(diào)度。新的調(diào)度表也是可行的。,, 若tt，則在中作類似的調(diào)換，即將中在t，t+1時刻調(diào)度的那個作業(yè)（如果有的話）與x相交換。如果Y中在t，t+1時刻沒有作業(yè)調(diào)度，則直接

19、將x移到t，t+1調(diào)度。同樣，新的調(diào)度表也是可行的。 對X和Y中共有的所有作業(yè)作上述的調(diào)整。設(shè)調(diào)整后得到的調(diào)度表為和，則在和中X和Y中所有的共有作業(yè)將在相同時間被調(diào)度。,,設(shè)a在中的調(diào)度時刻是ta, ta+1， b是中該時刻調(diào)度的作業(yè)，則有papb（為什么？）。 在中，去掉作業(yè)b，而去調(diào)度作業(yè)a，得到的是作業(yè)集合Y=（Y-b）a的 一個可行的調(diào)度表，且Y的效益值不小于X的效益值。而Y中比Y少了一個與X不同的作業(yè)。 重復上述的轉(zhuǎn)換，可使Y在不減效益值的情況下轉(zhuǎn)換成X。從而X至少有和Y一樣的效益值。所以X也是最優(yōu)解。 證畢。,,,=（x z ） =（ z x ） =（y x

20、） =（ y x ） (a) x與z交換前 (b) x與z交換后 =（y x ） =（ y x ） =（x z ） =（ z x ） (c) x與z交換前 (d) x與z交換后 圖6-1 使相同作業(yè)在相同時刻被調(diào)度,,,,6.3.4 可行性判定,定理63 X=（x0,x1,,xk）是k個作業(yè)的集合，=（0, 1,,k）是X 的一種特定排列，它使得d 0 d1dk ，其中， dj是作業(yè)j的時限。X是一個可行解當且僅當X中的作業(yè)能夠按次序調(diào)度而不會有作業(yè)超期。,,,,方法一：枚舉法，檢驗X中作業(yè)所有可能的排列，對于任一種次序排列的作業(yè)序列，判斷這些作業(yè)是否能夠在其期限前完成 若X中有

21、k個作業(yè)，則將要檢查k!個序列 判斷策略： 對于一個給定作業(yè)處理序列i1i2ik,由于作業(yè)ij完成的最早時間是j，因此只要判斷出排列中的每個作業(yè)的期限有dijj，就可得知是一個允許的調(diào)度序列，從而X是一可行解。 反之，如果排列中有一個作業(yè)有dijj,則將是一個行不通的調(diào)度序列，因為至少作業(yè)ij不能在其期限之前完成。,方法二：檢查X中作業(yè)的一個特定序列就可判斷X的可行性：這一特定序列是按照作業(yè)期限的非降次序排列的作業(yè)序列,,證明： 如果X中的作業(yè)可以按照的次序而又不違反任何一個作業(yè)期限的情況來處理，則X是一個可行解 現(xiàn)證若X是一個可行解，是否代表一個可行的調(diào)度序列？ X是可行解

22、 必存在一可行的調(diào)度序列 r1r2rk，使得drjj, 1jk。 若 ，則即是可行的調(diào)度序列。否則， ，令a是使得raia的最小下標（如下圖）,, i1 i2 ia ic ik r1 r2 ra rb rk,,,設(shè)rb=ia。則有： ba 且 dradrb 故，在中調(diào)換ra與rb，所得的新序列 s1s2sk的處理次序不違反任何一個期限，而中位置a及a之前的作業(yè)均與相同。 重復上述過程，則可將轉(zhuǎn)換成且不違反任何一個期限，故是一個可行的調(diào)度序列 故定理得證。,,,,6.3.5 作業(yè)排序貪心算法,,,定理63提供了一種高效的可行解判定方法。使得在按最

23、優(yōu)量度標準，即按作業(yè)收益的非增次序選擇下一個作業(yè)后，可以有效地判定是否可將該作業(yè)加入已生成的部分解向量X。,,【程序64】帶時限的作業(yè)排序程序 int JS(int *d, int *x, int n) //設(shè)p0p1pn-1 int k=0; x0=0; for (int j=1;j=0 ,,6.3.6 一種改進算法,本小節(jié)將介紹一種帶時限作業(yè)排序的快速算法，它采用不同于前者的可行解判定方法，可使算法的時間從(n2)減少到接近O(n)。,,,,,,,例63 設(shè)n=5個作業(yè)， 作業(yè)的時限為:(d0,d1,d2,d3,d4)=(2,2,1,3,3), 收益為: (p0,p1,p2,p3,p

24、4)=(20,15,10,5,1)。,,,【程序65】使用并查集的帶時限作業(yè)排序 int FJS(int *d,int *x,int n) UFSet s(n); int b,k=-1,*f=new intn+1; for (int i=0;i<=n;i++) fi=i;,,for (i=0;i

25、 delete f; return k; ,,,多機調(diào)度問題,多機調(diào)度問題要求給出一種作業(yè)調(diào)度方案，使所給的n個作業(yè)在盡可能短的時間內(nèi)由m臺機器加工處理完成。 這個問題是NP完全問題，到目前為止還沒有有效的解法。對于這一類問題,用貪心選擇策略有時可以設(shè)計出較好的近似算法。,約定，每個作業(yè)均可在任何一臺機器上加工處理，但未完工前不允許中斷處理。作業(yè)不能拆分成更小的子作業(yè)。,,采用最長處理時間作業(yè)優(yōu)先的貪心選擇策略可以設(shè)計出解多機調(diào)度問題的較好的近似算法。 按此策略，當 nm時，只要將機器i的0, ti時間區(qū)間分配給作業(yè)i即可，算法只需要O(1)時間。

26、 當nm時，首先將n個作業(yè)依其所需的處理時間從大到小排序。然后依此順序?qū)⒆鳂I(yè)分配給空閑的處理機。算法所需的計算時間為O(nlogn)。,,,例如，設(shè)7個獨立作業(yè)1,2,3,4,5,6,7由3臺機器M1，M2和M3加工處理。各作業(yè)所需的處理時間分別為2,14,4,16,6,5,3。按算法greedy產(chǎn)生的作業(yè)調(diào)度如下圖所示，所需的加工時間為17。,,6.4.1 問題描述,兩路合并外排序算法通過反復執(zhí)行將兩個有序子文件合并成一個有序文件的操作，最終將n個長度不等的有序子文件合并成一個有序文件。 合并n個有序子文件成為一個有序文件的合并過程可以有多種方式，稱為合并模式。 在整個合并過程中，需從外存

27、讀寫的記錄數(shù)最少的合并方案稱為最佳合并模式（optimal merge pattern）。,,,6.4 最佳合并模式,,例64 設(shè)有5個有序子文件（F1,F2,F3,F4,F5），其長度分別為（20，30，30，10，5）?，F(xiàn)通過兩兩合并將其合并成一個有序文件。,,,帶權(quán)外路徑長度是針對擴充二叉樹而言的。擴充二叉樹（extended binary tree）中除葉子結(jié)點外，其余結(jié)點都必須有兩個孩子。擴充二叉樹的帶權(quán)外路徑長度（weighted external path length）定義為：,,,6.4.2貪心法求解,兩路合并最佳模式問題的最優(yōu)量度標準為帶權(quán)外路徑長度最小。,,,,兩路合并最

28、佳模式的貪心算法簡述如下： 設(shè)Ww0,w1 ,,wn1是n個有序文件的長度；以每個權(quán)值作為根結(jié)點值，構(gòu)造n棵只有根的二叉樹； 選擇兩棵根結(jié)點權(quán)值最小的樹，作為左右子樹構(gòu)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)值之和； 重復第2步，直到合并成一棵二叉樹為止。,,【程序66】兩路合并最佳模式的貪心算法 template struct HNode //優(yōu)先權(quán)隊列中的元素的類型 operator T()const return weight; BTNode *ptr; T weight; ;,,template BTNode* CreateHfmTree (T* w,int n) //w

29、為一維數(shù)組保存n個權(quán)值 PrioQueue pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;i(wi); a.ptr=p;a.weight=wi; pq.Append(a); ,,for (i=1;i(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a); return a.ptr; ,,6.4.3 算法正確性,定理64 設(shè)有n個權(quán)值W=w0,w1 ,,wn1作為外結(jié)點的權(quán)值，構(gòu)造兩路合并樹的

30、貪心算法將生成一棵具有最小帶權(quán)外路徑長度的二叉樹。,,,,,,,,6.5.1 問題描述,問題 一個無向連通圖的生成樹是一個極小連通子圖，它包括圖中全部結(jié)點，并且有盡可能少的邊。 一棵生成樹的代價是樹中各條邊上的代價之和。一個網(wǎng)絡(luò)的各生成樹中，具有最小代價的生成樹稱為該網(wǎng)絡(luò)的最小代價生成樹（minimum-cost spanning tree）。,6.5 最小代價生成樹,,網(wǎng)絡(luò)的最小生成樹在實際中有廣泛應(yīng)用。例如，在設(shè)計通信網(wǎng)絡(luò)時，用圖的頂點表示城市，用邊(v,w)的權(quán)cvw表示建立城市v和城市w之間的通信線路所需的費用，則最小生成樹就給出了建立通信網(wǎng)絡(luò)的最經(jīng)濟的方案。,,6.5.2 貪心法求解

31、,最優(yōu)量度標準 選擇使得迄今為止已入選S中邊的代價之和增量最小的邊 克魯斯卡爾算法的貪心準則是：按邊代價的非減次序考察E中的邊，從中選擇一條代價最小的邊e=(u,v)。 普里姆算法的貪心準則是：在保證S所代表的子圖是一棵樹的前提下選擇一條最小代價的邊e=(u,v)。,,,,最小生成樹性質(zhì) 用貪心算法設(shè)計策略可以設(shè)計出構(gòu)造最小生成樹的有效算法。將介紹的構(gòu)造最小生成樹的Prim算法和Kruskal算法都可以看作是應(yīng)用貪心算法設(shè)計策略的例子。盡管這兩個算法做貪心選擇的方式不同，它們都利用了下面的最小生成樹性質(zhì)： 設(shè)G=(V,E)是連通帶權(quán)圖，U是V的真子集。如果(u,v)E，且uU，vV-U，且

32、在所有這樣的邊中，(u,v)的權(quán)cuv最小，那么一定存在G的一棵最小生成樹，它以(u,v)為其中一條邊。這個性質(zhì)有時也稱為MST性質(zhì)。,,【程序67】最小代價生成樹的貪心算法 ESetType SpanningTree(ESetType E, int n) //G=(V,E)為無向圖 ESetType S=; int u,v,k=0; EType e; while (k

33、e* nextArc; ;,,,,,template class Graph public: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost); ENode** a; int n; ;,,template void Graph::Prim(int s) //公有成員函數(shù) int* nearest=new intn,*lowcost=new intn; Prim(s,nearest,lowcost); for(int j=0;j

34、cout<<(<

35、lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true;,,for (i=1;inextArc) int j= p-adjVex; if ((!markj ) 普里姆算法的運行時間是O(n2)。,,,,6.5.4 克魯斯卡爾算法,,克魯斯卡爾算法從邊的集合E中，按照邊的權(quán)值從小到大的次序依次選取邊加以考察。 template struct eNode operator T ()const return w; int u,v; T w; ;,,,,,,,,【程序69】克魯斯卡爾算法 template v

36、oid Graph::Kruskal( PrioQueue ,,while (k

37、有向圖G=(V,E)和圖中結(jié)點sV，求從s到其余各結(jié)點的最短路徑，其中，s稱為源點。,6.6 單源最短路徑,,,,6.6.2 貪心法求解,迪杰斯特拉（Dijkstra） 算法 首先求得長度最短的一條最短路徑，再求得長度次短的一條最短路徑，依此類推，直到從源點到其它所有結(jié)點之間的最短路徑都已求得為止。,,,,6.6.3 迪杰斯特拉算法,【程序610】迪杰斯特拉算法 template class MGraph public: MGraph(int mSize); void Dijkstra(int s,T* ,,,,private: int Choose(int* d, bool* s);

38、 T**a; int n; ;,,template int MGraph::Choose(int* d, bool* s) int i,minpos; T min; min=INFTY; minpos=-1; for (i=1;i

39、 inSk=true; for (j=0; j

40、和（vi,vk=t）必定分別是從s到vi 和vi到t的最短路徑。 定理610 已知帶非負權(quán)值的有向圖G=(V,E)，其源點為s，迪杰斯特拉算法結(jié)束時，對所有結(jié)點i，有di=(s,i)。,,6.7.1 單帶最優(yōu)存儲,問題 設(shè)有n個程序編號為0,,n-1，存放在長度為L的磁帶上，程序i在磁帶上的存儲長度為ai，0i

41、計算迄今為止已選的那部分程序的D值，選擇下一個程序應(yīng)使得該值增加最小。 定理611 設(shè)有n個程序0,1,,n-1, 程序i的長度為ai，0i

42、d Store(int n, int m) int j = 0; for (int i=0; i