Greedy Algorithms PDF

6 Greedy Algorithms Optimization Problem A problem to find a solution with the optimal (maximum or minimum) value under a given constraint It is also called mathematical programming problem. Linear programming problem Integer programming problem Nonlinear programming problem Combinat...

6 Greedy Algorithms Optimization Problem A problem to find a solution with the optimal (maximum or minimum) value under a given constraint It is also called mathematical programming problem. Linear programming problem Integer programming problem Nonlinear programming problem Combinatorial optimization problem Network programming problem Greedy Algorithm A method to select one with the best value at that point when we select items that make up a solution among possible candidates We select one with the best value according to local information. → It may happen that the selection is not so good from the global perspective. Greedy algorithms give optimal solutions to several optimization problems. Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 1/8 General Description of Greedy Algorithms procedure greedy (C); S := φ; while not solution(S) and C ≠ φ do begin x := select(C); C := C - {x}; if feasible( S ∪ {x} ) then S := S ∪ {x} end; if solution(S) then return S else return "no solution"; C · · · candidate set S · · · solution set solution(S) · · · solution function select(C) · · · selection function feasible(S∪{x}) · · · feasibility function A function to calculate the value of a solution · · · objective function Although the objective function is not described explicitly in the procedure, it is required for the selection function. Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 2/8 6.2 Minimum Spanning Tree A Spanning Tree of a graph G A subgraph that is acyclic and connects all vertices in G A Minimum Spanning Tree of a graph G Assume that a nonnegative weight is given to each edge in G. A minimum spanning tree is a spanning tree of G such that the sum of weights is minimum. b 6 e 4 2 3 d a 2 3 g 7 8 5 7 c 6 f Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 3/8 6.2.1 Kruskal’s Algorithm Idea behind the algorithm At the beginning, each vertex itself forms a tree. Then, two trees are merged into a tree. We execute this merge operation repeatedly. procedure Kruskal(G = (V , E ), weight : E → R ∗ ); { function weight assigns a nonnegative weight to each edge } Sort E by their weight in ascending order; Make |V | sets so that each set consists of a vertex; T := ϕ; repeat (u, v ) := (an unchecked edge with the least weight); comp1 := (the set that u belongs to); comp2 := (the set that v belongs to); if comp1 ̸= comp2 then begin merge(comp1, comp2); {Merge set comp1 and set comp2 into a set} T := T ∪ {(u, v )} end until |T | = |V | − 1; return T ; Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 4/8 Example 6.2 b 6 e 4 2 3 d a 2 3 g 7 8 5 7 c 6 f Step Edge Considered Connected Component T Initial State {a}, {b}, {c}, {d}, {e}, {f }, {g } ϕ 1 (b, c) {a}, {b, c}, {d}, {e}, {f }, {g } {(b, c)} 2 (d, e) {a}, {b, c}, {d, e}, {f }, {g } {(b, c), (d, e)} 3 (e, f ) {a}, {b, c}, {d, e, f }, {g } {(b, c), (d, e), (e, f )} 4 (e, g ) {a}, {b, c}, {d, e, f , g } {(b, c), (d, e), (e, f ), (e, g )} 5 (a, b) {a, b, c}, {d, e, f , g } {(b, c), (d, e), (e, f ), (e, g ), (a, b)} 6 (d, f ) reject {a, b, c}, {d, e, f , g } {(b, c), (d, e), (e, f ), (e, g ), (a, b)} 7 (b, e) {a, b, c, d, e, f , g } {(b, c), (d, e), (e, f ), (e, g ), (a, b), (b, e)} Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 5/8 Theorem 6.1 Let G = (V , E ) be a connected graph such that a nonnegative real weight is assigned to each edge. If there exists a minimum spanning tree that includes A ⫅ E , then A is said to be a promised edge set of G. We call an edge that connects an endpoint of an edge in A and a vertex that is not an endpoint of any edge in A as a cross edge between A and E − A. Theorem 6.1 Let G = (V , E ) be a connected graph such that a nonnegative real weight is assigned to each edge. Let A be a promised edge set of G and (u, v ) be a cross edge with the least weight among the cross edges between A and E − A. Then, A ∪ {(u, v )} is also a promised edge set of G. Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 6/8 Time Complexity of Procedure Kruskal Let |V | = n and |E | = m. It is required O(m log n) time to sort E by edge weight. It is required O(n) time to make |V | sets so that each set consists of a vertex. Analysis of repeat statement ▶ It is required O(1) time to find the set that u belongs to and the set that v belongs to. Since repeat statement is executed m times in the worst case, it requires O(m) time. ▶ The number of times that the set that u belongs to is merged into the other set is at most O(log n) times. It is required O(1) time for u to update the name of the set that u belongs to. Since there are n vertices, it is required O(n log n) time for set merging operations. From these analysis, the time complexity of procedure Kruskal is O(m log n). Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 7/8 Data Structure that represents sets head head element a b c d element e f name S name T size 4 size 2 next next tail tail head element a b c d e f name S size 6 next tail Algorithms (2ME) 4th, Algorithm to construct MST 2024. 10. 15 8/8