第4章 貪心算法-2

1、2022年5月9日星期一第4章 貪心算法12022年5月9日星期一第4章 貪心算法22022年5月9日星期一第4章 貪心算法32022年5月9日星期一第4章 貪心算法42022年5月9日星期一第4章 貪心算法52022年5月9日星期一第4章 貪心算法6算法思路算法思路將將n個(gè)活動(dòng)按結(jié)束時(shí)間非減序排列個(gè)活動(dòng)按結(jié)束時(shí)間非減序排列,依依次考慮活動(dòng)次考慮活動(dòng)i, 若若i與已選擇的活動(dòng)相容與已選擇的活動(dòng)相容, 則添加此則添加此活動(dòng)到相容活動(dòng)子集活動(dòng)到相容活動(dòng)子集.設(shè)待安排的設(shè)待安排的1111個(gè)活動(dòng)起止時(shí)間按結(jié)束時(shí)間的非減序排列個(gè)活動(dòng)起止時(shí)間按結(jié)束時(shí)間的非減序排列最大相容活動(dòng)子集最大相容活動(dòng)子集(1, 4

2、, 8, 11),(1, 4, 8, 11),也可表示為等長(zhǎng)也可表示為等長(zhǎng)n n元數(shù)組元數(shù)組:(1, 0, 0, 1, 0, 0, 0, 1, 0, 0, 1)思考如下具有思考如下具有11個(gè)活動(dòng)安排的問題？個(gè)活動(dòng)安排的問題？1 2 3 4 5 6 7 8 9 10 115 0 3 5 3 1 8 6 8 12 2 9 6 5 7 8 4 11 10 12 14 13 1 2 3 4 5 6 7 8 9 10 111 3 0 5 3 5 6 8 8 2 12 4 5 6 7 8 9 10 11 12 13 14isifi2022年5月9日星期一第4章 貪心算法72022年5月9日星期一第4章 貪

3、心算法82022年5月9日星期一第4章 貪心算法92022年5月9日星期一第4章 貪心算法102022年5月9日星期一第4章 貪心算法112022年5月9日星期一第4章 貪心算法122022年5月9日星期一第4章 貪心算法13例例設(shè)設(shè)n=8，w1，w8=100, 200, 50, 90, 150, 50, 20, 80，c=400。算法思路算法思路 將裝船過程劃為多步選擇，每步裝將裝船過程劃為多步選擇，每步裝一個(gè)貨箱，每次從剩下的貨箱中選擇重量最輕一個(gè)貨箱，每次從剩下的貨箱中選擇重量最輕的貨箱的貨箱.如此下去直到所有貨箱均裝上船或船如此下去直到所有貨箱均裝上船或船上不能再容納其他任何一個(gè)貨箱。

4、上不能再容納其他任何一個(gè)貨箱。所考察貨箱的次序?yàn)樗疾熵浵涞拇涡驗(yàn)?:7, 3, 6, 8, 4, 1, 5, 2。貨箱。貨箱7, 3, 6, 8, 4, 1的總重量為的總重量為390個(gè)單位且已被裝載個(gè)單位且已被裝載, 剩下的裝載能剩下的裝載能力為力為10 ,小于任意貨箱小于任意貨箱.所以得到解所以得到解x1,.x8= 1, 0, 1, 1, 0, 1, 1, 12022年5月9日星期一第4章 貪心算法14最優(yōu)裝載的貪心算法template void Loading(int x, Type w, Type c, int n ) int *t = new int n + 1; Sort(w, t

5、, n) ; /按貨箱重量排序按貨箱重量排序/ / for (int i = 1; i = n; i +) xi = 0; for (int i = 1;i= n & wti = c; i+) xti = 1; c-= wti; /調(diào)整調(diào)整剩余空間剩余空間/ /算法分析算法分析: : 排序?yàn)橹饕惴〞r(shí)間,所以 T(n)=O(nlogn) 算法證明算法證明: :該算法能得到最優(yōu)解. 2022年5月9日星期一第4章 貪心算法152022年5月9日星期一第4章 貪心算法16100552530a:4514f:5d:16b:13c:12e:90100001112022年5月9日星期一第4章 貪心

6、算法172022年5月9日星期一第4章 貪心算法182022年5月9日星期一第4章 貪心算法192022年5月9日星期一第4章 貪心算法20 template BinaryTreeHuffmanTree(T f, int n) /根據(jù)權(quán)根據(jù)權(quán)f1:nf1:n構(gòu)造霍夫曼樹構(gòu)造霍夫曼樹 /創(chuàng)建一個(gè)單節(jié)點(diǎn)樹的數(shù)組創(chuàng)建一個(gè)單節(jié)點(diǎn)樹的數(shù)組 Huffman *W=newHuffman n+1； BinaryTree z,zero； for(int i=1；i=n；i+) z.MakeTree(i, zero, zero)； Wi.weight=fi； Wi.tree=z: /數(shù)組變成數(shù)組變成個(gè)最小堆個(gè)最小

7、堆 MinHeapHuffman Q(1)； Q.Initialize(w,n,n)； /將堆中的樹不斷合并將堆中的樹不斷合并 Huffman x, y for(i=1;in;i+) Q.DeleteMin(x)； Q.DeleteMin(y)； z.MakeTree(0, x.tree, y.tree)； x.weight+=y.weight；x.tree=z； Q.Insert(x)； Q. DeleteMin(x)；/最后的樹最后的樹 Q. Deactivate()； delete w； return x.tree；霍夫曼樹算法霍夫曼樹算法2022年5月9日星期一第4章 貪心算法2120

8、22年5月9日星期一第4章 貪心算法22xybcTbyxcT bcxyT F(x)=f(b), f(y) 根樹及其應(yīng)用根樹及其應(yīng)用w w(T)=(T)= w wi i L(L(w wi i) )1234512453345212022年5月9日星期一第4章 貪心算法25設(shè)在設(shè)在1000個(gè)字母的文章中各字母出現(xiàn)的頻率為個(gè)字母的文章中各字母出現(xiàn)的頻率為: a:83, b:14, c:28, d:38, e:131, f:29, g:20, h:53. 14 20 28 29 38 53 83 131 34 28 29 38 53 83 131 34 57 38 53 83 131 57 72 53

9、83 131 72 110 83 131 110 155 131155 2413961100134721313961552411105357833828291420101000110最佳編碼最佳編碼:a:10 ; b:1111; c:0101; d:110; e:00; f:0100; g:1110; h:0111)將權(quán)從小到大排序?qū)?quán)從小到大排序2)每次選取最小權(quán)合并每次選取最小權(quán)合并例例 題題貪心算法貪心算法 哈夫曼編碼哈夫曼編碼2022年5月9日星期一第4章 貪心算法2615432103010506010020例：具有五個(gè)頂點(diǎn)的有向圖，例：具有五個(gè)頂點(diǎn)的有向圖，各邊上的數(shù)即為長(zhǎng)度。對(duì)于給

10、各邊上的數(shù)即為長(zhǎng)度。對(duì)于給定源頂點(diǎn)定源頂點(diǎn)v1，需找出從它到圖，需找出從它到圖中其他任意頂點(diǎn)的最短路徑。中其他任意頂點(diǎn)的最短路徑。2022年5月9日星期一第4章 貪心算法27n下一步所能達(dá)到的目的頂點(diǎn)通過如下貪心準(zhǔn)則選?。合乱徊剿苓_(dá)到的目的頂點(diǎn)通過如下貪心準(zhǔn)則選?。涸谶€未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑長(zhǎng)度最短在還未產(chǎn)生最短路徑的頂點(diǎn)中，選擇路徑長(zhǎng)度最短的目的頂點(diǎn)。即按路徑長(zhǎng)度順序產(chǎn)生最短路徑。的目的頂點(diǎn)。即按路徑長(zhǎng)度順序產(chǎn)生最短路徑。n最初產(chǎn)生從最初產(chǎn)生從v 到它自身的路徑，這條路徑?jīng)]有邊，到它自身的路徑，這條路徑?jīng)]有邊，其長(zhǎng)度為其長(zhǎng)度為0。在貪心算法的每一步中，產(chǎn)生下一個(gè)。在貪心算法的每一

11、步中，產(chǎn)生下一個(gè)最短路徑。最短路徑。艾茲格迪科斯徹 2022年5月9日星期一第4章 貪心算法28Svu1u2V-S用貪心選擇來擴(kuò)充集合用貪心選擇來擴(kuò)充集合S。起初，起初，S中僅包含源點(diǎn)中僅包含源點(diǎn)v。某頂點(diǎn)某頂點(diǎn)uS 從源點(diǎn)從源點(diǎn)v到到u的最短路徑已知。的最短路徑已知。2022年5月9日星期一第4章 貪心算法29 算法描述：算法描述： (1) 用帶權(quán)的鄰接矩陣用帶權(quán)的鄰接矩陣c來表示帶權(quán)有向圖來表示帶權(quán)有向圖, cij表示弧表示弧 上的權(quán)值上的權(quán)值. 若若 V,則置則置cij為為 設(shè)設(shè)S為已知最短路徑的終點(diǎn)的集合為已知最短路徑的終點(diǎn)的集合,它的初始狀態(tài)為空集它的初始狀態(tài)為空集. 從源點(diǎn)從源點(diǎn)v

12、到圖上其余各點(diǎn)到圖上其余各點(diǎn)vi的當(dāng)前最短路徑長(zhǎng)度的初值為：的當(dāng)前最短路徑長(zhǎng)度的初值為： disti=cvi vi V (2) 選擇選擇vj, 使得使得distj=Mindisti | vi V-S vj就是長(zhǎng)度最短的最短路徑的終點(diǎn)。令就是長(zhǎng)度最短的最短路徑的終點(diǎn)。令S=Sj (3) 修改從修改從v到集合到集合V-S上任一頂點(diǎn)上任一頂點(diǎn)vk的當(dāng)前最短路徑長(zhǎng)度的當(dāng)前最短路徑長(zhǎng)度: 如果如果 distj+cjk distk 則修改則修改 distK= distj+cjk (4) 重復(fù)操作重復(fù)操作(2),(3)共共n-1次次.2022年5月9日星期一第4章 貪心算法302022年5月9日星期一第4章

13、 貪心算法31例例 題題1) v1 v2: 102) v1 v3: 503) v1 v4: 304) v1 v5: 60迭代迭代 Svid2d3d4d5初始初始 1 10 30100 1 1,2 2 10 60 30100 2 1,2,4 4 10 50 30 90 3 1,2,3,4 3 10 50 30 60 41,2,3,4,5 5 10 50 30 60 10 30100 50 10 20 60 2022年5月9日星期一第4章 貪心算法32 voidDijkstra(int n, int v,Type dist, int prev, Type *c) bool smaxint； for

14、 (int i=1;i=n; i+) disti=cvi； si=false； if(disti= =maxint) previ=0； else previ=v ; distv=0；sv=true； for (int i=1;in；i+) int temp=maxint； int u= v； for (int j = 1；j=n；j+) if (!sj)&(distjtemp) u=j； temp=distj； su=true； for (int j=1；j=n;j+) ； if(!sj)(cujmaxint) Type newdist=distu)+cuj; if (newdist0

15、dv,x+dx,u distu distx distu 這與假設(shè)矛盾。這與假設(shè)矛盾。假設(shè)有一條從源到假設(shè)有一條從源到u的更短的更短的路徑（經(jīng)過的路徑（經(jīng)過X）。）。2022年5月9日星期一第4章 貪心算法352022年5月9日星期一第4章 貪心算法36問題陳述問題陳述: :設(shè)設(shè)G(V,E)是一個(gè)無(wú)向連通帶權(quán)圖。是一個(gè)無(wú)向連通帶權(quán)圖。E中每條中每條邊邊(v, w)的權(quán)為的權(quán)為cvw,若若G的一個(gè)子圖的一個(gè)子圖G是一棵包含是一棵包含G的所有頂點(diǎn)的樹，則稱的所有頂點(diǎn)的樹，則稱G為為G的生成樹。生成樹各邊的生成樹。生成樹各邊權(quán)的總和稱為該生成樹的耗費(fèi)。在權(quán)的總和稱為該生成樹的耗費(fèi)。在G的所有生成樹中的

16、所有生成樹中,耗費(fèi)最小的生成樹稱為耗費(fèi)最小的生成樹稱為G的的最小生成樹最小生成樹.輸入輸入:任一連通生成子圖任一連通生成子圖 (該子圖的邊集合該子圖的邊集合) 可行解可行解:圖的生成樹圖的生成樹, 優(yōu)化函數(shù)優(yōu)化函數(shù):生成樹的各邊權(quán)值之和生成樹的各邊權(quán)值之和 最優(yōu)解最優(yōu)解:使優(yōu)化函數(shù)達(dá)到最小的生成樹使優(yōu)化函數(shù)達(dá)到最小的生成樹.2022年5月9日星期一第4章 貪心算法37U V-Uuu v v2022年5月9日星期一第4章 貪心算法38算法思路算法思路: 首先置首先置S=1, T= .若若S V, 就作如下的貪心選擇：就作如下的貪心選擇： 選取滿足條件選取滿足條件i S, j V-S,且且cij最

17、小的邊最小的邊(i, j),將頂點(diǎn)將頂點(diǎn)j添加到添加到S中中邊邊(i, j)添加到添加到T中中.這個(gè)過程一直進(jìn)行到這個(gè)過程一直進(jìn)行到S=V時(shí)為止時(shí)為止. T中的所有邊構(gòu)中的所有邊構(gòu)成成G的一棵最小生成樹。的一棵最小生成樹。void Prim(int n, Type * * c) T= ; S =1; while (S!= V) (i, j) = i S且且 j V- S的最小權(quán)邊的最小權(quán)邊; T=T(i,j); S= Sj; 算法描述算法描述 Prim Prim算法算法設(shè)設(shè)G=(V,E)是一個(gè)連通帶權(quán)圖是一個(gè)連通帶權(quán)圖, V=l, 2, , n。2022年5月9日星期一第4章 貪心算法39例例

18、 題題2022年5月9日星期一第4章 貪心算法402022年5月9日星期一第4章 貪心算法41TemplateVoid Prim(int n,Type *c) Type lowcostmaxint; int closestmaxint; bool smaxint; s1=true; for(int i=2;i=n;i+) lowcosti=c1i; closesti=1; si=false; for(int i=1;i=n;i+) Type min=inf; int j=1; for(int k=2;k=n;k+) if(lowcostkmin)&(!sk) min=lowcostk;

19、 j=k; coutjclosetjendl;sj=true;for(int k=2;k=n;k+) if(cjklowcostk&(!sk) lowcostk=cjk; closetk=j; 2022年5月9日星期一第4章 貪心算法422022年5月9日星期一第4章 貪心算法43例例 題題2022年5月9日星期一第4章 貪心算法44template bool Kruskal(int n, int e, EdgeNode E , EdgeNode t ) MinHeap EdgeNode H(1); H. Initialize(E, e, e); UnionFind U(n); int

20、 k = 0; while (e & k n- 1) EdgeNode x; H. DeleteMin(x); e-; int a = U.Find(x.u); int b = U.Eind(x.v); if (a! = b) tk + = x; U. Union(a, b); H. Deactivate( )renturn (k = = n-1)Kruska算法算法2022年5月9日星期一第4章 貪心算法45e1(1)e2(6)e8(9)e6 (2)e9(4)e5(5)e4(7)e10(8)e11(3)e7(10)e3(11)1) 以以G 中全部點(diǎn)為點(diǎn)作圖中全部點(diǎn)為點(diǎn)作圖2) 按權(quán)的

21、大小次序依次添加按權(quán)的大小次序依次添加 各邊各邊,若出若出 現(xiàn)回路則忽略此邊現(xiàn)回路則忽略此邊.3) 加入加入n-1條邊后就得到最小條邊后就得到最小 生成樹生成樹.12537求最小生成樹求最小生成樹( (Kruscal) )最優(yōu)解最優(yōu)解: (e1, e6, e11, e5, e4)2022年5月9日星期一第4章 貪心算法462022年5月9日星期一第4章 貪心算法472022年5月9日星期一第4章 貪心算法48請(qǐng)考慮舉個(gè)反例。請(qǐng)考慮舉個(gè)反例。2022年5月9日星期一第4章 貪心算法49class JobNode friend void Greedy(JobNode * , int, int);

22、friend void main(void); public: operator int () const return time; private: int ID, time; ;class MachineNode friend void Greedy(JobNode *, int, int); public: operator int( ) const return avail; private: int ID, avail; 多機(jī)調(diào)度問題的貪心近似算法多機(jī)調(diào)度問題的貪心近似算法2022年5月9日星期一第4章 貪心算法50templatevoid Greedy(Type a，int n，i

23、nt m)if (n=m) cont”為每個(gè)作業(yè)分配一臺(tái)機(jī)器為每個(gè)作業(yè)分配一臺(tái)機(jī)器.“endl return；Sort(a，n)；MinHeapH(m)；MachineNode x；for(int：i=1；i=1；i-) HDeleteMin(x)； cout”將機(jī)器將機(jī)器”xID“從從” xavail到到” (xavail十十a(chǎn)itime) ”的時(shí)間段分配給作業(yè)的時(shí)間段分配給作業(yè)”ai. IDendl； xavail+=aitime； Hinsert(x)；2022年5月9日星期一第4章 貪心算法512022年5月9日星期一第4章 貪心算法522022年5月9日星期一第4章 貪心算法532022年