Module 13 Coping with Algorithm Limitations (Saudi Electronic University)

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Design and Analysis of Algorithms Design and Analysis of Algorithms Module 13 Coping with the Limitations of Algorithm Power Week Learning Ou...

‫الجامعة السعودية االلكترونية‬ ‫الجامعة السعودية االلكترونية‬ ‫‪26/12/2021‬‬ College of Computing and Informatics Design and Analysis of Algorithms Design and Analysis of Algorithms Module 13 Coping with the Limitations of Algorithm Power Week Learning Outcomes Recognize Backtracking algorithms Express Branch-and-Bound concept Demonstrate Approximation Algorithms for NP-Hard Problems 4 Topic Outline  Backtracking  Branch-and-Bound  Approximation Algorithms for NP-Hard Problems 5 Tackling Difficult Combinatorial Problems There are two principal approaches to tackling difficult combinatorial problems :(NP-hard problems) Use a strategy that guarantees solving the problem exactly but doesn’t guarantee to find a solution in polynomial time Use an approximation algorithm that can find an approximate (sub-optimal) solution in polynomial time 6 Exact Solution Strategies exhaustive search (brute force) useful only for small instances dynamic programming applicable to some problems (e.g., the knapsack problem) backtracking eliminates some unnecessary cases from consideration yields solutions in reasonable time for many instances but worst case is still exponential branch-and-bound further refines the backtracking idea for optimization problems 7 Backtracking Construct the state-space tree o nodes: partial solutions o edges: choices in extending partial solutions o Explore the state space tree using depth-first search “Prune” nonpromising nodes o dfs stops exploring subtrees rooted at nodes that cannot lead to a solution and backtracks to such a node’s parent to continue the search 8 Example: n-Queens Problem Place n queens on an n-by-n chess board so that no two of them are in the same row, column, or diagonal Board for the four-queens problem 9  State-Space Tree of the 4-Queens Problem State-space tree of solving the four-queens problem by backtracking. × denotes an unsuccessful attempt to place a queen in the indicated column. The numbers above the nodes indicate the order in which the nodes are generated. 1 0 Example: Hamiltonian Circuit Problem It starts at vertex a. Make vertex a the root of the state-space if it exists, is a first intermediate vertex of a Hamiltonian circuit to be constructed. Using the alphabet order to break the three-way tie among the vertices adjacent to a, we select vertex b. From b, the algorithm proceeds to c, then to d, then to e, and finally to f, which proves to be a dead end. So the algorithm backtracks from f to e, then to d, and Find Hamiltonian Circuit then to c, which provides the first alternative for the for this graph algorithm to pursue. 1 1 Example: Hamiltonian Circuit Problem Going from c to e eventually proves useless, and the algorithm has to backtrack from e to c and then to b. From there, it goes to the vertices f , e, c, and d, from which it can legitimately return to a, yielding the Hamiltonian circuit a, b, f , e, c, d, a. If we wanted to find another Hamiltonian circuit, we could continue this process by backtracking from the leaf of the solution found. Find Hamiltonian Circuit for this graph 1 2 Example: Hamiltonian Circuit Problem State-space tree for finding a Hamiltonian circuit. The numbers above the nodes of the tree indicate the order in which the nodes are generated 1 3 Branch-and-Bound Branch-and-Bound An enhancement of backtracking Applicable to optimization problems For each node (partial solution) of a state-space tree, computes a bound on the value of the objective function for all descendants of the node (extensions of the partial solution) Uses the bound for: ruling out certain nodes as “nonpromising” to prune the tree – if a node’s bound is not better than the best solution seen so far guiding the search through state-space 1 5 Branch-and-Bound Select one element in each row of the cost matrix C so that: no two selected elements are in the same column the sum is minimized Example Job 1 Job 2 Job 3 Job 4 Person a 9 2 7 8 Person b 6 4 3 7 Person c 5 8 1 8 Person d 7 6 9 4 Lower bound: Any solution to this problem will have total cost at least: 2 + 3 + 1 + 4 (or 5 + 2 + 1 + 4) 1 6 Example -Assignment Problem Levels 0 and 1 of the state-space tree for the instance of the assignment problem being solved with the best-first branch-and-bound algorithm. The number above a node shows the order in which the node was generated. A node’s fields indicate the job number assigned to person a and the lower bound value, lb, for this node. 1 7 Example -Assignment Problem Levels 0, 1, and 2 of the state-space tree for the instance of the assignment problem being solved with the best-first branch-and-bound algorithm. 1 8 Example -Assignment Problem Complete state-space tree for the instance of the assignment problem solved with the best-first branch-and-bound algorithm 1 9 Activity !!! In groups: Apply Branch-and- Bound to solve Travel Sale Man problem for this graph? 2 0 Approximation Approach Approximation Approach Apply a fast (i.e., a polynomial-time) approximation algorithm to get a solution that is not necessarily optimal but hopefully close to it Accuracy measures: accuracy ratio of an approximate solution sa r(sa) = f(sa) / f(s*) for minimization problems r(sa) = f(s*) / f(sa) for maximization problems where f(sa) and f(s*) are values of the objective function f for the approximate solution sa and actual optimal solution s* performance ratio of the algorithm A the lowest upper bound of r(sa) on all instances 2 2 Nearest-Neighbor Algorithm for TSP Starting at some city, always go to the nearest unvisited city, and, after visiting all the cities, return to the starting one Note: Nearest-neighbor tour may depend on the starting city Accuracy: RA = ∞ (unbounded above) – make the length of AD arbitrarily large in the above example sa : A – B – C – D – A of length 10 s* : A – B – D – C – A of length 8 2 3 Multifragment-Heuristic Algorithm :Stage 1 Sort the edges in nondecreasing order of weights. Initialize the set of tour edges to be constructed to empty set :Stage 2 Add next edge on the sorted list to the tour, skipping those whose addition would’ve created a vertex of degree 3 or a cycle of length less than n. Repeat this step until a tour of length n is obtained Note: RA = ∞, but this algorithm tends to produce better tours than the nearest-neighbor algorithm 2 4 Twice-Around-the-Tree Algorithm Stage 1: Construct a minimum spanning tree of the graph (e.g., by Prim’s or Kruskal’s algorithm) Stage 2: Starting at an arbitrary vertex, create a path that goes twice around the tree and returns to the same vertex Stage 3: Create a tour from the circuit constructed in Stage 2 by making shortcuts to avoid visiting intermediate vertices more than once Note: RA = ∞ for general instances, but this algorithm tends to produce better tours than the nearest-neighbor algorithm 2 5 Example of twice-around-the-tree algorithm Walk: a – b – c – b – d – e – d – b – a Tour: a – b – c – d – e – a 2 6 Greedy Algorithm for Knapsack Problem Step 1: Compute the value-to-weight ratios (relative values) v1/w1,…, vn/wn Step 2: Order the items in decreasing order of relative values Step 3: Select the items in this order skipping those that don’t fit into the knapsack Example: The knapsack’s capacity is 16 item weight value v/w 1 2 $40 20 2 5 $30 6 3 10 $50 5 4 5 $10 2 Accuracy RA is unbounded (e.g., n = 2, C = m, w1=1, v1=2, w2=m, v2=m) yields exact solutions for the continuous version 2 7 Bin Packing Problem: First-Fit Algorithm Step 1: Order the items in decreasing order of relative values: v1/w1,… ,vn/wn Step 2: For a given integer parameter k, 0 ≤ k ≤ n, generate all subsets of k items or less and for each of those that fit the knapsack, add the remaining items in decreasing order of their value to weight ratios Step 3: Find the most valuable subset among the subsets generated in Step 2 and return it as the algorithm’s output Accuracy: f(s*) / f(sa) ≤ 1 + 1/k for any instance of size n Time efficiency: O(knk+1) There are fully polynomial schemes: algorithms with polynomial running time as functions of both n and k 2 8 Activity !!! In groups: Think of examples of Knapsack problem can be solved by First -Fit? 2 9 Summary Backtracking and branch-and-bound are two algorithm design techniques for solving problems in which the number of choices grows at least exponentially with their instance size. Both techniques construct a solution one component at a time, trying to terminate the process as soon as one can ascertain that no solution can be obtained as a result of the choices already made. This approach makes it possible to solve many large instances of NP-hard problems in an acceptable amount of time. Approximation algorithms are often used to find approximate solutions to difficult problems of combinatorial optimization. The performance ratio is the principal metric for measuring the accuracy of such approximation algorithms. The multifragment heuristic is a simple greedy algorithms for approximating a solution to the traveling salesman problem. The performance ratios of these algorithms are unbounded above, even for the important subset of Euclidean graphs. 3 0 Summary A sensible greedy algorithm for the knapsack problem is based on processing an input’s items in descending order of their value-to-weight ratios. For the continuous version of the problem, this algorithm always gives an exact optimal solution. 3 1 List of Readings  Required Reading : Chapter 12 from Anany Levitin (2012). Introduction to the Design and Analysis of Algorithms. Pearson, 2012, 3rd edition  Recommending Reading : Chapter 18 from Michael T.Goodrich, Roberto Tamassia (2014). Algorithm Design and Applications. First Edition Wiley. 3 2 Thank You