《算法课件全121301ADA16贪心法》由会员分享，可在线阅读，更多相关《算法课件全121301ADA16贪心法（32页珍藏版）》请在金锄头文库上搜索。
1、Greedy Technique,Chapter 9,Basic Idea and General Process Application to Graph Problem MST Problem Single source shortest path problem,2019/6/22,3,2012-2013-01 Design and Analysis of Algorithm SCUN,Goals of This Lecture,At the end of this lecture, you should Understand the basic idea and general sol
2、ving process of greedy approach Master the properties and greedy selection strategies of MST problem Master Dijkstra algorithm and its application,2019/6/22,4,2012-2013-01 Design and Analysis of Algorithm SCUN,Example: Change-Making Problem,The solution is optimal for any amount and “normal set of d
3、enominations may not be optimal for arbitrary money denominations,Given unlimited amounts of paper moneys of denominations d1, , dm , give change for amount n with the least number of paper moneys,Example: d1 = 100, d2 =50, d3 =20, d4 =10, d5 =5, d6 = 2, d7 = 1 and n = 66,The solution: 4 (d2 + d4+ d
4、5+ d7=66),2019/6/22,5,2012-2013-01 Design and Analysis of Algorithm SCUN,Greedy Technique,For some problems, yields an optimal solution for every instance. For most, does not but can be useful for fast approximations.,The greedy approach suggests constructing a solution to an problem through a seque
5、nce of steps, each expanding a partially constructed solution obtained so far, until a complete solution to the problem is reached. On each step, the choice made must be: feasible, i.e., it has to satisfy the problems constraints locally optimal, i.e., it has to be the best local choice among all fe
6、asible choices available on that step irrevocable, i.e. once made, it cannot be changed on subsequent steps of the algorithm,2019/6/22,6,2012-2013-01 Design and Analysis of Algorithm SCUN,Greedy Technique (cont.),Given a positive answer is very hard, but generally speaking, the problem has two impor
7、tant properties: Optimal substructure property: the optimal solution of the problem contains the optimal solution of its subproblem Greedy selection property: the global optimal solution of the problem can be achieved through a series of local optimal choice,So for a specific problem, how to know wh
8、ether we can use greedy approach to solve the problem and whether we can get the optimal solution to the problem?,2019/6/22,7,2012-2013-01 Design and Analysis of Algorithm SCUN,Greedy(C) /C is the input set, i.e., candidate set S = ; /S is the solution set, initially empty while (not solution(S) /so
9、lution() is a function to check whether S is a complete solution of the problem x = select(C); /select() is a function to do greedy selection in C if feasible(S, x) /feasible is a function to check whether the extended solution satisfy the constraints S = S + x; C = C - x; return S; ,Solving Process
10、 of Greedy Approach,2019/6/22,8,2012-2013-01 Design and Analysis of Algorithm SCUN,MST Problem (Concept),Minimum spanning tree of a weighted, connected graph G: a spanning tree of G of minimum total weight,Spanning tree of a connected graph G: a connected acyclic subgraph of G that includes all of G
11、s vertices,The spanning tree of a connected graph G has the following properties: Any two vertices of T are connected by a unique path T has exactly n-1 edges The addition of one more edge to T creates a cycle,2019/6/22,9,2012-2013-01 Design and Analysis of Algorithm SCUN,Discussion,Is the minimum s
12、panning tree of graph always unique? yes, provide examples no, why? try to find out what kind of graphs has a unique mst,Is it possible for a connected undirected graph to have many different spanning trees? yes, provide examples no, why?,2019/6/22,10,2012-2013-01 Design and Analysis of Algorithm SC
13、UN,Optimal substructure property,MSTs satisfy the optimal substructure property: an optimal tree is composed of optimal subtrees Let T be an MST of G with an edge (u,v) in the middle Removing (u,v) partitions T into two trees T1 and T2 Claim: T1 is an MST of G1 = (V1,E1), and T2 is an MST of G2 = (V
14、2,E2) (Do V1 and V2 share vertices? Why?) Proof: w(T) = w(u,v) + w(T1) + w(T2),2019/6/22,11,2012-2013-01 Design and Analysis of Algorithm SCUN,Greedy selection strategy,The shortest edge strategy (kruskal algorithm): in each greedy selection step, choose the shortest edge, if not generate cycle when
15、 add it to the edge set of the spanning tree, then add it to the edge set of the spanning tree.,Two greedy selection strategy in MST,The closest vertex strategy (Prim algorithm): choose a vertex arbitrarily to create a spanning tree, then in each greedy selection step, simply add the closest vertex
16、which not in the spanning tree into the spanning tree.,2019/6/22,12,2012-2013-01 Design and Analysis of Algorithm SCUN,Single-Source Shortest Path,E.g., a road map: what is the shortest path from Wuhan to other cities?,Problem: given a weighted directed graph G, find the minimum-weight path from a given source vertex s to any other vertices.,2019/6/22,13,2012-2013-01 Design and Analysis of Algorithm SCUN,Properties of Shortest Paths t
