[高等教育]《算法設(shè)計與分析》第06章ppt課件

1、l貪婪法是經(jīng)過分步?jīng)Q策貪婪法是經(jīng)過分步?jīng)Q策stepwise decision的的方法來求解問題的。方法來求解問題的。l貪婪法每一步上用作決策根據(jù)的選擇準那么被稱貪婪法每一步上用作決策根據(jù)的選擇準那么被稱為最優(yōu)量度規(guī)范為最優(yōu)量度規(guī)范optimization criterion。l在根據(jù)最優(yōu)量度規(guī)范選擇分量的過程中，還需求在根據(jù)最優(yōu)量度規(guī)范選擇分量的過程中，還需求運用一個可行解斷定函數(shù)。運用一個可行解斷定函數(shù)。l貪婪戰(zhàn)略并不是從整體上加以思索的，它所做出貪婪戰(zhàn)略并不是從整體上加以思索的，它所做出的選擇只是當前看似最正確選擇，必需進一步證的選擇只是當前看似最正確選擇，必需進一步證明該算法最終導(dǎo)致問題

2、的一個整體最優(yōu)解。明該算法最終導(dǎo)致問題的一個整體最優(yōu)解。某一問題的n個輸入該問題的一種解可行解是A的一個子集滿足一定的條件約束條件目的函數(shù)取極值最優(yōu)解78l知一個載重為知一個載重為M的背包和的背包和n件物品，第件物品，第i件物品的分件物品的分量為量為 wi，假設(shè)將第，假設(shè)將第i件物品全部裝入背包，將有收益件物品全部裝入背包，將有收益pi，這里，這里，wi0，pi0，0in。所謂背包問題是指。所謂背包問題是指求一種最正確裝載方案，使得收益最大。所以，背求一種最正確裝載方案，使得收益最大。所以，背包問題是現(xiàn)實世界一個常見的最優(yōu)化問題。包問題是現(xiàn)實世界一個常見的最優(yōu)化問題。l兩類背包問題兩類背包問題

3、:假設(shè)每一件物品不能分割，只能作假設(shè)每一件物品不能分割，只能作為整體或者裝入背包，或者不裝入，稱為為整體或者裝入背包，或者不裝入，稱為 0/1背包問背包問題；假設(shè)物品是可以分割的，也就是允許將其中的題；假設(shè)物品是可以分割的，也就是允許將其中的一部分裝入背包為普通背包問題或簡稱背包問題。一部分裝入背包為普通背包問題或簡稱背包問題。 n i0 , 1x0 ,0w Mxwii1n0iii n i0 ,1x0 ,0p xpmax ii1n0iii 方案1：按物品價值降序裝包方案2：按物品分量升序裝包方案3：按物品價值與分量比值的降序裝包templatevoid Knapsack:GreedyKnaps

4、ack(float* x) /前置條件：前置條件：wi已按已按pi/wi的非增次序陳列的非增次序陳列 float u=m; for (int i=0;in;i+) xi=0; for (i=0;iu) break; xi=1.0; u=u-wi; if (i=n) xi=u/wi; Mxwii Mywii Mywii Myiiw1-1)()(nikkkkiiiyzwzyw1-01-1-0/)(/)(niiiinikiikkkkkiiniiiwpwzywpwyzypzp1-01-/)()(nikkinikiikkkiiwpwzywyzyp1-0niiiyp差值0iiiiypzpiiiiypzp

5、設(shè)有n個活動的集合E=1,2,n，其中每個活動都要求運用同一資源，如演講會場等，而在同一時間內(nèi)只需一個活動能運用這一資源。每個活動i都有一個要求運用該資源的起始時間si和一個終了時間fi,且si fi 。假設(shè)選擇了活動i，那么它在半開時間區(qū)間si, fi)內(nèi)占用資源。假設(shè)區(qū)間si, fi)與區(qū)間sj, fj)不相交，那么稱活動i與活動j是相容的。也就是說，當sifj或sjfi時，活動i與活動j相容。下面給出解活動安排問題的貪婪算法GreedySelector :各活動的起始時間和終各活動的起始時間和終了時間存儲于數(shù)組了時間存儲于數(shù)組s s和和f f中且按終了時間的非減中且按終了時間的非減序陳列

6、序陳列 YaXbXY x.zy.x t ty.xx.z t t.a.b ta return k; return k; for (i=0;in;i+) if(ndi) b=n;else b=di; int r=s.Find(b); if (fr) x+k=i; int t=s.Find(fr-1); s.Union(t,r); fr=ft; delete f; return k; 商定，每個作業(yè)均可在任何一臺機器上加工處置，但未商定，每個作業(yè)均可在任何一臺機器上加工處置，但未完工前不允許中斷處置。作業(yè)不能拆分成更小的子作業(yè)。完工前不允許中斷處置。作業(yè)不能拆分成更小的子作業(yè)。 m1kkklwWPL

7、l兩路合并最正確方式的貪婪算法簡述如下：兩路合并最正確方式的貪婪算法簡述如下：l設(shè)設(shè)W Ww0,w1 ,w0,w1 ,wn,wn11是是n n個有序文件的長度；個有序文件的長度；以每個權(quán)值作為根結(jié)點值，構(gòu)造以每個權(quán)值作為根結(jié)點值，構(gòu)造n n棵只需根的二叉樹；棵只需根的二叉樹；l選擇兩棵根結(jié)點權(quán)值最小的樹，作為左右子樹構(gòu)選擇兩棵根結(jié)點權(quán)值最小的樹，作為左右子樹構(gòu)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)造一棵新二叉樹，新樹根的權(quán)值是兩棵子樹根的權(quán)值之和；值之和；l反復(fù)第反復(fù)第2 2步，直到合并成一棵二叉樹為止。步，直到合并成一棵二叉樹為止。template BTNode* CreateHfmT

8、ree (T* w,int n) /w 為一維數(shù)組保管為一維數(shù)組保管n個權(quán)值個權(quán)值PrioQueue HNode pq(2*n-1); BTNode*p;HNode a,b; for (int i=0;in;i+) p=new BTNode(wi); a.ptr=p;a.weight=wi; pq.Append(a); for (i=1;in;i+) pq.Serve(a);pq.Serve(b); a.weight+=b.weight; p=new BTNode(a.weight,a.ptr,b.ptr); a.ptr=p; pq.Append(a); pq.Serve(a); return

9、 a.ptr; template class Graphpublic: Graph (int mSize); void Prim(); protected: void Prim(int k,int* nearest,T* lowcost); ENode* a; int n; ;templatevoid Graph:Prim(int s)/公有成員函數(shù)公有成員函數(shù)int* nearest=new intn,*lowcost=new intn;Prim(s,nearest,lowcost);for(int j=0;jn;j+) cout(nearestj,“ j,lowcostj) ;couten

10、dl; delete nearest; delete lowcost;templatevoid Graph:Prim(int k, int* nearest,T* lowcost)/私有成員函數(shù)私有成員函數(shù) bool* mark=new booln; ENode *p; if (kn-1) throw OutofBounds; for (int i=0;in;i+) nearesti=-1;marki=false; lowcosti=INFTY; lowcostk=0; nearestk=k; markk=true; for (i=1;inextArc) int j= p-adjVex; if

11、 (!markj )&(lowcostjp-w) lowcostj=p-w; nearestj=k; T min=INFTY; for (int j=0;jn;j+) if (!markj)&(lowcostjmin) min=lowcostj; k=j; markk=true; 普里姆算法的運轉(zhuǎn)時間是普里姆算法的運轉(zhuǎn)時間是O(n2)。l 【程序【程序69】克魯斯卡爾算法】克魯斯卡爾算法 ltemplate lvoid Graph:Kruskal(l PrioQueueeNode & pq)l leNode x;lUFSet s(n); lint u,v,k=0; l

12、while (kn-1 & !pq.IsEmpty() pq.Serve(x); u=s.Find(x.u); v=s.Find(x.v); if (u!=v) s.Union(u,v); k+; cout(x.u, x.v,x.w) ; coutendl; if (kn-2) throw NonConnected; 克魯斯卡爾算法的時間復(fù)雜度為克魯斯卡爾算法的時間復(fù)雜度為 Oelog e。 private: int Choose(int* d, bool* s); T*a; int n; ; template int MGraph:Choose(int* d, bool* s) in

13、t i,minpos; T min; min=INFTY; minpos=-1; for (i=1;in;i+) if (dimin &!si) min=di;minpos=i; return minpos; template void MGraph:Dijkstra(int s, T*& d,int*& path) int k,i,j; if (sn-1) throw OutOfBounds; bool *inS=new booln; d=new Tn;path=new intn; for (i=0;in;i+) inSi=false;di=asi; if (i!=s

14、 & diINFTY) pathi=s; else pathi=-1; inSs=true; ds=0; for (i=1;in-1;i+) k=Choose(d,inS); inSk=true; for (j=0; jn; j+) if (!inSj & dk+akj dj) dj=dk+akj; pathj=k; 1n0kktn1 mj0j)D(Il選擇最優(yōu)量度規(guī)范是運用貪婪法求解問題的中心選擇最優(yōu)量度規(guī)范是運用貪婪法求解問題的中心問題。問題。l貪婪算法每一步作出的選擇可以依賴以前作出的貪婪算法每一步作出的選擇可以依賴以前作出的選擇，但不依賴未來的選擇，也不依賴于子問題的選擇，但不依賴未來的選擇，也不依賴于子問題的解。解。l 對于一個貪婪算法，必需證明所采用的量度規(guī)范對于一個貪婪算法，必需證明所采用的量度規(guī)范可以導(dǎo)致一個整體最優(yōu)解?？梢詫?dǎo)致一個整體最優(yōu)解。l 最優(yōu)子構(gòu)造特性是關(guān)于問題最優(yōu)解的特性。當一最優(yōu)子構(gòu)造特性是關(guān)于問題最優(yōu)解的特性。當一個問題的最優(yōu)解中包含了子問題的