《算法设计与分析算法设计与分析 (6).ppt》由会员分享，可在线阅读，更多相关《算法设计与分析算法设计与分析 (6).ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1Chapter 4Greedy AlgorithmsSlides by Kevin Wayne.Copyright 2005 Pearson-Addison Wesley.All rights reserved.4.5 Minimum Spanning Tree3Minimum Spanning TreeMinimum spanning tree.Given a connected graph G=(V,E)with real-valued edge weights ce,an MST is a subset of the edges T E such that T is a spannin
2、g tree whose sum of edge weights is minimized.52310 21 1424 16 6 4189711 8 5 6 49711 8G=(V,E)T,eT ce=504ApplicationsMST is fundamental problem with diverse applications.nNetwork design.telephone,electrical,hydraulic,TV cable,computer,roadnApproximation algorithms for NP-hard problems.traveling sales
3、person problem,Steiner treenCluster analysis.5Greedy AlgorithmsKruskals algorithm.Start with T=.Consider edges in ascending order of cost.Insert edge e in T unless doing so would create a cycle.Prims algorithm.Start with some root node s and greedily grow a tree T from s outward.At each step,add the
4、 cheapest edge e to T that has exactly one endpoint in T.Remark.All these algorithms produce an MST.6Cycles and CutsCycle.Set of edges the form a-b,b-c,c-d,y-z,z-a.Cutset.A cut is a subset of nodes S.The corresponding cutset D is the subset of edges with exactly one endpoint in S.Cycle C =1-2,2-3,3-
5、4,4-5,5-6,6-113826745Cut S =4,5,8 Cutset D=5-6,5-7,3-4,3-5,7-813826745Claim.A cycle and a cutset intersect in an even number of edges.Pf.(by picture)7Cycle-Cut IntersectionSV-SC8Greedy AlgorithmsSimplifying assumption.All edge costs ce are distinct.Cut property.Let S be any subset of nodes,and let e
6、 be the min cost edge with exactly one endpoint in S.Then the MST contains e.Cycle property.Let C be any cycle,and let f be the max cost edge belonging to C.Then the MST does not contain f.f CSe is in the MSTef is not in the MST9Greedy AlgorithmsSimplifying assumption.All edge costs ce are distinct.
7、Cut property.Let S be any subset of nodes,and let e be the min cost edge with exactly one endpoint in S.Then the MST T*contains e.Pf.(exchange argument)nSuppose e does not belong to T*,and lets see what happens.nAdding e to T*creates a cycle C in T*.nEdge e is both in the cycle C and in the cutset D
8、 corresponding to S there exists another edge,say f,that is in both C and D.nT=T*e -f is also a spanning tree.nSince ce cf,cost(T)cost(T*).nThis is a contradiction.f T*eS10Greedy AlgorithmsSimplifying assumption.All edge costs ce are distinct.Cycle property.Let C be any cycle in G,and let f be the m
9、ax cost edge belonging to C.Then the MST T*does not contain f.Pf.(exchange argument)nSuppose f belongs to T*,and lets see what happens.nDeleting f from T*creates a cut S in T*.nEdge f is both in the cycle C and in the cutset D corresponding to S there exists another edge,say e,that is in both C and
10、D.nT=T*e -f is also a spanning tree.nSince ce cf,cost(T)cost(T*).nThis is a contradiction.f T*eS11Prims Algorithm:Proof of CorrectnessPrims algorithm.Jarnk 1930,Dijkstra 1957,Prim 1959nInitialize S=any node.nApply cut property to S.nAdd min cost edge in cutset corresponding to S to T,and add one new
11、 explored node u to S.S12Kruskals Algorithm:Proof of CorrectnessKruskals algorithm.Kruskal,1956nConsider edges in ascending order of weight.nCase 1:If adding e to T creates a cycle,discard e according to cycle property.nCase 2:Otherwise,insert e=(u,v)into T according to cut property where S=set of n
12、odes in us connected component.Case 1vuCase 2eeS13Lexicographic TiebreakingTo remove the assumption that all edge costs are distinct:perturb all edge costs by tiny amounts to break any ties.e.g.,if all edge costs are integers,perturbing cost of edge ei by i/n2.Implementation.Prims and(Kruskals)algor
13、ithm can find MST in O(mlog n)time.4.7 ClusteringOutbreak of cholera deaths in London in 1850s.Reference:Nina Mishra,HP Labs15ClusteringClustering.Given a set U of n objects labeled p1,pn,classify into coherent groups.Distance function.Numeric value specifying closeness of two objects.Fundamental pr
14、oblem.Divide into clusters so that points in different clusters are far apart.nRouting in mobile ad hoc networks.nIdentify patterns in gene expression.nDocument categorization for web search.nSimilarity searching in medical image databasesnSkycat:cluster 109 sky objects into stars,quasars,galaxies.p
15、hotos,documents.micro-organismsnumber of corresponding pixels whoseintensities differ by some threshold16Clustering of Maximum Spacingk-clustering.Divide objects into k non-empty groups.Distance function.Assume it satisfies several natural properties.nd(pi,pj)=0 iff pi=pj(identity of indiscernibles)
16、nd(pi,pj)0(nonnegativity)nd(pi,pj)=d(pj,pi)(symmetry)Spacing.Min distance between any pair of points in different clusters.Clustering of maximum spacing.Given an integer k,find a k-clustering of maximum spacing.spacingk=417Greedy Clustering AlgorithmSingle-link k-clustering algorithm.nForm a graph o
17、n the vertex set U,corresponding to n clusters.nFind the closest pair of objects such that each object is in a different cluster,and add an edge between them.nRepeat n-k times until there are exactly k clusters.Key observation.This procedure is precisely Kruskals algorithm(except we stop when there
18、are k connected components).Remark.Equivalent to finding an MST and deleting the k-1 most expensive edges.18Greedy Clustering Algorithm:AnalysisTheorem.Let C*denote the clustering C*1,C*k formed by deleting thek-1 most expensive edges of a MST.C*is a k-clustering of max spacing.Pf.Let C denote some
19、other clustering C1,Ck.nThe spacing of C*is the length d*of the(k-1)st most expensive edge.nLet pi,pj be in the same cluster in C*,say C*r,but different clusters in C,say Cs and Ct.nSome edge(p,q)on pi-pj path in C*r spans two different clusters in C.nAll edges on pi-pj path have length d*since Kruskal chose them.nSpacing of C is d*since p and qare in different clusters.pqpipjCsCtC*rHomeworkRead Chapter 4 of the textbook.Exercises 5&18 in Chapter 4.19