ImageVerifierCode 换一换
格式:PPT , 页数:35 ,大小:340.50KB ,
文档编号:4306785      下载积分:25 文币
快捷下载
登录下载
邮箱/手机:
温馨提示:
系统将以此处填写的邮箱或者手机号生成账号和密码,方便再次下载。 如填写123,账号和密码都是123。
支付方式: 支付宝    微信支付   
验证码:   换一换

优惠套餐
 

温馨提示:若手机下载失败,请复制以下地址【https://www.163wenku.com/d-4306785.html】到电脑浏览器->登陆(账号密码均为手机号或邮箱;不要扫码登陆)->重新下载(不再收费)。

已注册用户请登录:
账号:
密码:
验证码:   换一换
  忘记密码?
三方登录: 微信登录  
下载须知

1: 试题类文档的标题没说有答案,则无答案;主观题也可能无答案。PPT的音视频可能无法播放。 请谨慎下单,一旦售出,概不退换。
2: 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。
3: 本文为用户(晟晟文业)主动上传,所有收益归该用户。163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!。
4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
5. 本站仅提供交流平台,并不能对任何下载内容负责。
6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

版权提示 | 免责声明

1,本文(国外算法设计与分析课件2.ppt)为本站会员(晟晟文业)主动上传,163文库仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。
2,用户下载本文档,所消耗的文币(积分)将全额增加到上传者的账号。
3, 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(发送邮件至3464097650@qq.com或直接QQ联系客服),我们立即给予删除!

国外算法设计与分析课件2.ppt

1、Copyright Li Zimao 2007-2008-1 SCUECGreedy Algorithms(I)Greed,for lack of a better word,is good!Greed is right!Greed works!-Michael Douglas,U.S.actor in the role of Gordon Gecko,in the film Wall Street,1987Main topicsnIdea of the greedy approachnChange-making problemnMinimum spanning tree problemnPr

2、ims algorithmnKruskals algorithmnProperties of minimum spanning tree(additive part)nBottleneck spanning tree(additive part)Expected OutcomesnStudent should be able tonsummarize the idea of the greedy techniquenlist several applications of the greedy techniquenapply the greedy technique to change-mak

3、ing problemndefine the minimum spanning tree problemndescribe ideas of Prim and Kruskals algorithms for computing minimum spanning tree nprove the correctness of the two algorithmsnanalyze the time complexities of the two algorithms under different data structuresnprove the various properties of min

4、imum spanning treeGlossarynGreedy:贪婪的nChange-making problem:找零钱问题nCashier:收银员nDenomination:货币单位,面额nQuarter,dime,nickel,penny:2角5分,1角,5分,1分(美国硬币单位)nIrrevocable:不可取消的,不可逆的 nSpanning tree:生成树,支撑树Anticipatory Set:Change Making ProblemnHow to make 48 cents of change using coins of denominations of 25(1 q

5、uarter coin),10(1 dime coin),5(1 nickel coin),and 1(1 penny coin)so that the total number of coins is the smallest?nThe idea:nTake the coin with largest denomination without exceeding the remaining amount of cents,nmake the locally best choice at each step.nIs the solution optimal?Yes,the proof is l

6、eft as exercise.General Change-Making ProblemGiven unlimited amounts of coins of denominations d1 dm,give change for amount n with the least number of coins.Does the greedy algorithm always give an optimal solution for the general change-making problem?We give the following example,Example:d1=7c,d2=

7、5c,d3=1c,and n=10c,not always produces an optimal solution.in fact,for some instances,the problem may not have a solution at all!consider instance d1=7c,d2=5c,d3=3c,and n=11c.But,this problem can be solved by dynamic programming,please try to design an algorithm for the general change-making problem

8、 after class.Greedy AlgorithmsnA greedy algorithm makes a locally optimal choice step by step in the hope that this choice will lead to a globally optimal solution.The choice made at each step must be:nFeasiblenSatisfy the problems constraintsnlocally optimalnBe the best local choice among all feasi

9、ble choicesnIrrevocablenOnce made,the choice cant be changed on subsequent steps.nDo greedy algorithms always yield optimal solutions?nExample:change making problem with a denomination set of 7,5 and 1,and n=10?Applications of the Greedy StrategynOptimal solutions:nsome instances of change makingnMi

10、nimum Spanning Tree(MST)nSingle-source shortest paths nHuffman codesnApproximations:nTraveling Salesman Problem(TSP)nKnapsack problemnother optimization problemsMinimum Spanning Tree(MST)nSpanning tree of a connected graph G is a connected acyclic subgraph(tree)of G that includes all of Gs vertices.

11、nNote:a spanning tree with n vertices has exactly n-1 edges.nMinimum Spanning Tree of a weighted,connected graph G is a spanning tree of G of minimum total weight.nExample:MST ProblemnGiven a connected,undirected,weighted graph G=(V,E),find a minimum spanning tree for it.nCompute MST through Brute F

12、orce?nKruskal:1956,Prim:1957Brute forceGenerate all possible spanning trees for the given graph.Find the one with minimum total weight.Feasibility of Brute forcePossible too many trees(exponential for dense graphs)The Prims AlgorithmnIdea of the Prims algorithmnPseudo-code of the algorithmnCorrectne

13、ss of the algorithm(important)nTime complexity of the algorithmIdea of PrimnGrow a single tree by repeatedly adding the least cost edge(greedy step)that connects a vertex in the existing tree to a vertex not in the existing treenIntermediate solution is always a subtree of some minimum spanning tree

14、.Prims MST algorithmnStart with a tree,T0,consisting of one vertexn“Grow”tree one vertex/edge at a time Construct a series of expanding subtrees T1,T2,Tn-1.At each stage construct Ti from Ti-1 by nadding the minimum weight edge that connecting a vertex in tree(Ti-1)to a vertex not yet in the treenth

15、is is the“greedy”step!nAlgorithm stops when all vertices are includedPseudocode of the PrimALGORITHM Prim(G)/Prims algorithm for constructing a minimum spanning tree/Input:A weighted connected graph G=(V,E)/Output:ET,the set of edges composing a minimum spanning tree of GVT v0 /v0 can be arbitrarily

16、 selectedET for i 1 to|V|-1 do find a minimum-weight edge e*=(v*,u*)among all the edges(v,u)such that v is in VT and u is in V-VT VT VT u*ET ET e*return ETAn exampleaedcb1524637The Prims algorithm is greedy!nThe choice of edges added to current subtree satisfying the three properties of greedy algor

17、ithms.nFeasible,each edge added to the tree does not result in a cycle,guarantee that the final ET is a spanning treenLocal optimal,each edge selected to the tree is always the one with minimum weight among all the edges crossing VT and V-VT nIrrevocable,once an edge is added to the tree,it is not r

18、emoved in subsequent steps.Correctness of PrimnProve by induction that this construction process actually yields MST.nT0 is a subset of all MSTsnSuppose that Ti-1 is a subset of some MST T,we should prove that Ti which is generated from Ti-1 is also a subset of some MST.nBy contradiction,assume that

19、 Ti does not belong to any MST.nLet ei=(u,v)be the minimum weight edge from a vertex in Ti-1 to a vertex not in Ti-1 used by Prims algorithm to expanding Ti-1 to Ti,according to our assumption,ei can not belong to MST T.nAdding ei to T results in a cycle containing another edge e=(u,v)connecting a v

20、ertex u in Ti-1 to a vertex v not in it,and w(e)w(ei)according to the greedy Prims algorithm.nRemoving e from T and adding ei to T results in another spanning tree T with weight w(T)w(T),indicating that T is a minimum spanning tree including Ti which contradict to assumption that Ti does not belong

21、to any MST.Correctness of PrimImplementation of PrimnHow to implement the steps in the Prims algorithm?nFirst idea,label each vertex with either 0 or 1,1 represents the vertex in VT,and 0 otherwise.nTraverse the edge set to find an minimum weight edge whose endpoints have different labels.nTime comp

22、lexity:O(VE)if adjacency linked list and O(V3)for adjacency matrixnFor sparse graphs,use adjacency linked listnAny improvement?NotationsnT:the expanding subtree.nQ:the remaining vertices.At each stage,the key point of expanding the current subtree T is to nDetermine which vertex in Q is the nearest

23、vertex to T.nQ can be thought of as a priority queue:nThe key(priority)of each vertex,keyv,means the minimum weight edge from v to a vertex in T.Keyv is if v is not linked to any vertex in T.nThe major operation is to to find and delete the nearest vertex(v,for which keyv is the smallest among all t

24、he vertices)nRemove the nearest vertex v from Q and add it and the corresponding edge to T.nWith the occurrence of that action,the key of vs neighbors will be changed.To remember the edges of the MST,an array is introduced to record the parent of each vertex.That is v is the vertex in the expanding

25、subtree T that is closest to v not in T.Advanced Prims Algorithm ALGORITHM MST-PRIM(G,w,r)/w:weight;r:root,the starting vertexnfor each u VGn do keyu n u NIL/u:the parent of unkeyr 0nQ VG/Now the priority queue,Q,has been built.nwhile Q n do u Extract-Min(Q)/remove the nearest vertex from Qn for eac

26、h v Adju /update the key for each of vs adjacent nodes.n do if v Q and w(u,v)keyvn then v u1.keyv w(u,v)Time Complexity of Prims algorithmnNeed priority queue for locating the nearest vertexnUse unordered array to store the priority queue:Efficiency:(n2)nUse binary min-heap to store the priority que

27、ueEfficiency:For graph with n vertices and m edges:O(m log n)nUse Fibonacci-heap to store the priority queue:Efficiency:For graph with n vertices and m edges:O(n log n+m)Kruskals MST AlgorithmnEdges are initially sorted by increasing weightnStart with an empty forest F0n“grow”MST one edge at a time

28、through a series of expanding forests F1,F2,Fn-1nintermediate stages usually have forest of trees(not connected)nat each stage add minimum weight edge among those not yet used that does not create a cycle nneed efficient way of detecting/avoiding cyclesnalgorithm stops when all vertices are included

29、Correctness of KruskalnSimilar to the proof of PrimnProve by induction on the construction process actually generate a MSTnConsider F0,F1,Fn-1Basic Kruskals AlgorithmALGORITHM Kruscal(G)/Input:A weighted connected graph G =/Output:ET,the set of edges composing a minimum spanning tree of G.Sort E in

30、nondecreasing order of the edge weights w(ei1)=w(ei|E|)ET ;ecounter 0/initialize the set of tree edges and its sizek 0 while encounter w(e),which also indicates that the weight of e is greater than that of any edges in T.Removing e from T disconnects T into two subtrees T1 and T2,there must exist an edge f in T connecting T1 and T2,otherwise,T is not connected.T1T2 f forms a new tree T with w(T)=w(T)-w(e)+w(f)w(T),A contradiction to the fact that T is MST,thus,A MST is also a BST.

侵权处理QQ:3464097650--上传资料QQ:3464097650

【声明】本站为“文档C2C交易模式”,即用户上传的文档直接卖给(下载)用户,本站只是网络空间服务平台,本站所有原创文档下载所得归上传人所有,如您发现上传作品侵犯了您的版权,请立刻联系我们并提供证据,我们将在3个工作日内予以改正。


163文库-Www.163Wenku.Com |网站地图|