Bài giảng Phân tích và thiết kế giải thuật - Chương 8: Approximation algorithms

Nội dung text: Bài giảng Phân tích và thiết kế giải thuật - Chương 8: Approximation algorithms

1. Figure 6.2 An instance {X, F} of the set covering problem, where X consists of the 12 black points and F = { S1, S2, S3, S4, S5, S6}. A minimum size set cover is C = { S3, S4, S5}. The greedy algorithm produces the set C’ = {S1, S4, S5, S3} in order. 11
2. Applications of Set-covering problem ◼ Assume that X is a set of skills that are needed to solve a problem and we have a set of people available to work on it. We wish to form a team, containing as few people as possible, s.t. for every requisite skill in X, there is a member in the team having that skill. ◼ Assign emergency stations (fire stations) in a city. ◼ Allocate sale branch offices for a company. ◼ Schedule for bus drivers. 12
3. A greedy approximation algorithm Greedy-Set-Cover(X, F) 1. U = X 2. C =  3. while U !=  do 4. select an S F that maximizes | S  U| 5. U = U – S 6. C = C  {S} 7. return C The algorithm GREEDY-SET-COVER can easily be implemented to run in time complexity in |X| and |F|. Since the number of iterations of the loop on line 3-6 is at most min(|X|, |F|) and the loop body can be implemented to run in time O(|X|,|F|), there is an implementation that runs in time O(|X|,|F| min(|X|,|F|) . 13
4. Ratio bound of Greedy-set-cover ◼ Let denote the dth harmonic number d hd = i-11/i ◼ Theorem: Greedy-set-cover has a ratio bound H(max{|S|: S F}) ◼ Corollary: Greedy-set-cover has a ratio bound of (ln|X| +1) (Refer to the text book for the proofs) 14
5. 3. The Traveling Salesman Problem ◼ Since finding the shortest tour for TSP requires so much computation, we may consider to find a tour that is almost as short as the shortest. That is, it may be possible to find near-optimal solution. ◼ Example: We can use an approximation algorithm for the HCP. It's relatively easy to find a tour that is longer by at most a factor of two than the optimal tour. The method is based on ❑ the algorithm for finding the minimum spanning tree and ❑ an observation that it is always cheapest to go directly from a vertex u to a vertex w; going by way of any intermediate stop v can’t be less expensive. C(u,w) C(u,v)+ C(v,w) 15
6. APPROX-TSP-TOUR ◼ The algorithm computes a near-optimal tour of an undirected graph G. procedure APPROX-TSP-TOUR(G, c); begin select a vertex r V[G] to be the “root” vertex; grow a minimum spanning tree T for G from root r, using Prim’s algorithm; apply a preorder tree walk of T and let L be the list of vertices visited in the walk; form the halmintonian cycle H that visits the vertices in the order of L. /* H is the result to return * / end A preorder tree walk recursively visits every vertex in the tree, listing a vertex when its first encountered, before any of its children are visited. 16
7. Thí dụ minh họa giải thuật APPROX-TSP-TOUR 17
8. The preorder tree walk is not simple tour, since a node be visited many times, but it can be fixed, the tree walk visits the vertices in the order a, b, c, b, h, b, a, d, e, f, e, g, e, d, a. From this order, we can arrive to the hamiltonian cycle H: a, b, c, h, d, e ,f, g, a. 18
9. The optimal tour The total cost of H is approximately 19.074. An optimal tour H* has the total cost of approximately 14.715. The running time of APPROX-TSP-TOUR is O(E) = O(V2), since the input graph is a complete graph. 19
10. Ratio bound of APPROX-TSP-TOUR ◼ Theorem: APPROX-TSP-TOUR is an approxima- tion algorithm with a ratio bound of 2 for the TSP with triangle inequality. ◼ Proof: Let H* be an optimal tour for a given set of vertices. Since we obtain a spanning tree by deleting any edge from a tour, if T is a minimum spanning tree for the given set of vertices, then c(T) c(H*) (1) ◼ A full walk of T traverses every edge of T twice, we have: c(W) = 2c(T) (2) (1) and (2) imply that: c(W) 2c(H*) (3) 20
11. ◼ But W is not a tour, since it visits some vertices more than once. By the triangle inequality, we can delete a visit to any vertex from W. By repeatedly applying this operation, we can remove from W all but the first visit to each vertex. ◼ Let H be the cycle corresponding to this preorder walk. It is a hamiltonian cycle, since every vertex is visited exactly once. Since H is obtained by deleting vertices from W, we have c(H) c(W) (4) ◼ From (3) and (4), we conclude: c(H) 2c(H*) So, APPROX-TSP-TOUR returns a tour whose cost is not more than twice the cost of an optimal tour. 21
12. Appendix: A Taxonomy of Algorithm Design Strategies Strategy name Examples Bruce-force Sequential search, selection sort Divide-and-conquer Quicksort, mergesort, binary search Decrease-and-conquer Insertion sort, DFS, BFS Transform-and-conquer heapsort, Gauss elimination Greedy Prim’s, Dijkstra’s Dynamic Programming Floyd’s Backtracking Branch-and-Bound Approximate algorithms Heuristics Meta-heuristics 22