Design Ch.13

Course Information

• Course: Design and Analysis of Algorithms
• Module: 13 Coping with the Limitations of Algorithm Power
• University: Saudi Electronic University

Learning Outcomes

• Recognize Backtracking algorithms
• Express Branch-and-Bound concept
• Demonstrate Approximation Algorithms for NP-Hard Problems

Topic Outline

• Backtracking
• Branch-and-Bound
• Approximation Algorithms for NP-Hard Problems

Tackling Difficult Combinatorial Problems

• Two main approaches to tackle NP-hard problems:
  • Use a strategy to solve the problem exactly but not necessarily in polynomial time.
  • Use an approximation algorithm to find a sub-optimal solution in polynomial time.

Exact Solution Strategies

• Exhaustive search (brute force): useful only for small instances
• Dynamic programming: applicable to some problems (e.g., knapsack problem)
• Backtracking: eliminates some unnecessary cases, 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

Backtracking

• Construct the state-space tree:
  • Nodes represent partial solutions
  • Edges represent choices in extending partial solutions
• Explore the state space tree using depth-first search
• "Prune" non-promising nodes: Stop exploring subtrees that cannot lead to a solution, backtrack to the parent node.

Example: n-Queens Problem

• Place n queens on an n-by-n chessboard such that no two queens share the same row, column, or diagonal.
• A visual representation of the four-queens problem is included to display the arrangement.

Example: Hamiltonian Circuit Problem

• Starts at a vertex (e.g., a).
• Selects next vertex based on alphabetization to break ties.
• Traces possible paths until a dead end is reached, which leads to backtracking.
• Finds a Hamiltonian circuit (if one exists) by tracing paths and backtracking until a solution is found.
• Displays a state-space tree for illustrating the process for finding a Hamiltonian circuit for a given graph.

Example: Hamiltonian Circuit Problem -Useless Case

• Demonstrates a scenario where a path proves useless, leading to backtracking.
• Explains how the algorithm might backtrack and explore alternative paths to find a Hamiltonian circuit (if one exists) by tracing paths and backtracking until a solution is found.

Branch-and-Bound

• An enhancement of backtracking, applicable to optimization problems.
• For each node (partial solution) in a state-space tree, computes bounds on the value of the objective function for all descendants of the node (each possible extension of the partial solution).
• Uses the bounds to:
  • "Prune" nodes that cannot lead to a better solution
  • Guide the search by prioritizing more promising extensions.
• Illustrates the concept with an assignment problem example.

Example: Assignment Problem

• Examples of the level of state space trees for an assignment problem
• Illustrates the use of lower bounds to prune the search space

Approximation Approach

• Apply a fast (polynomial-time) approximation algorithm to find a near-optimal solution
• Accuracy measures:
  • Accuracy ratio (for minimization problems): approximate solution value / optimal solution value
  • Accuracy ratio (for maximization problems): optimal solution value / approximate solution value
• Performance ratio: the lowest upper bound of the accuracy ratio for all instances of the problem

Nearest-Neighbor Algorithm for TSP

• Starts at a city, travels to the nearest unvisited city, repeating until all cities are visited and returns to the starting city.
• Accuracy is potentially unbounded, as the optimal tour may not be found.

Multifragment Heuristic Algorithm

• Sorts edges by weight in non-decreasing order.
• Adds edges to the tour, avoiding cycles of length less than the number of vertices.
• Repeats this process until a complete tour is formed
• This algorithm shows improvements in accuracy compared to some others

Twice-Around-the-Tree Algorithm

• Constructs a Minimum Spanning Tree (MST).
• Creates a path that traverses the MST twice, returning to the starting vertex.
• Makes shortcuts to create a tour visiting each vertex only once, to reduce redundancy.
• This algorithm usually generates better tours than nearest neighbor but accuracy is unbounded.

Greedy Algorithm for Knapsack Problem

• Sorts items by value-to-weight ratio in descending order.
• Selects items in this order, skipping those that exceed the knapsack capacity.
• The algorithm provides an exact solution in the continuous version.

Bin Packing Problem: First-Fit Algorithm

• Sorts items in decreasing order of their value-to-weight ratio.
• Generates all subsets of items that fit the knapsack,
• Finds the most valuable subset among these subsets and return it.
• Time efficiency is O(kn^k + 1)
• Accuracy is f(s*) / f(s₂) ≤ 1 + 1/ k

Activities

• Activities encourage group work to apply the introduced concepts to particular problems (like Travel Salesman Problem, Knapsack Problem).

Summary

• Backtracking and branch-and-bound are techniques for solving problems with exponentially growing choices.
• Approximation algorithms are used for difficult optimization problems, providing near-optimal but not necessarily perfect solutions.
• Examples of approximation algorithms for the traveling Salesman Problem and knapsack problem are illustrated.

List of Readings

• Required reading: Chapter 12 from Anany Levitin (2012)
• Recommended reading: Chapter 18 from Michael T. Goodrich, Roberto Tamassia (2014)

Test your knowledge on coping with the limitations of algorithm power in this quiz focused on Backtracking algorithms, Branch-and-Bound concepts, and Approximation Algorithms for NP-Hard problems. Understand various strategies to tackle combinatorial problems and their efficiencies. Perfect for students in the Design and Analysis of Algorithms course.