EECS 281: Data Structures and Algorithms

Section 18 Backtracking, Branch and Bound Algorithms

University of Michigan at Ann Arbor

Last Edit Date: 06/14/2023

Disclaimer and Term of Use:

We do not guarantee the accuracy and completeness of the summary content. Some of the course material may not be included, and some of the content in the summary may not be correct. You should use this file properly and legally. We are not responsible for any results from using this file

This personal note is adapted from Professor Marcus Darden and David Paoletti. Please contact us to delete this file if you think your rights have been violated.

This work is licensed under a Creative Commons Attribution 4.0 International License.

Types of Algorithm Problems¶

Constriant satisfaction problems
- Can rely on Backtraching algorithms
- Can we satisfy all given constraints?
- If yes, how do we satisfy them?
  - Need a specific solution
- May have more than one solution
- Go over all possible solutions
- Does a given input combination satisfy all constraints?
- Can stop when a satisfying solution is found
Optimization problems
- Cam rely on Branch and Bound algorithms
- Must satisfy all constraints
- Must minimize an objective function subjext to those constraints
- Similar, except we also need to compute the objective function every time
- Stopping early = possible non-optimal solution

BackTracking¶

i. General Form

Algorithm checknode(node v)
    if (promising(v))
        if (solution(v))
            write solution*
        else
            for each node u adjacent to v
            checknode(u)

* Can exit here if only the existence of a solution is needed

solution(v): Check "depth" of solution (constraint satisfaction)
promising(v): Different for each application
checknode(v): Called only if partial solution is both promising and not a solution

ii. Alternate Form:

Algorithm checknode(node v)
    if (solution(v))
        write solution*
    else
        for each node u adjacent to v
            if (promising(u))
                checknode(u)

* Can exit here if only the existence of a solution is needed

Backtracking Example: n Queens

$n = 1$: Can 1 queen be placed on a $1 \times 1$ board so that it does not threaten another?
$n = 2$
$n = 3$
$n = 4$
$n = 5$
...

For 4 queens

Entire search tree has 256 leaves
Backtracking enables searching of 19 branches before finding first solution
Promising
- May lead to solution
Not promising
- Will never lead to solution
- Therefore should be pruned

BackTracking Elements: n Queens

solution(v)
- Check ‘depth’ of solution (constraint satisfaction)
- Placed queen on each row
- That is, depth = N
checknode(v)
- Called only if promising and not solution
- Recursive call to all positions (columns) of queen within row
promising(row, col)
- Called for each node of the search tree
- Assume data structures that can tell you if:
  - column[col] // is column 'col' available
  - leftDiagonal[x] // is upper-left to lower-right diagonal available
  - rightDiagonal[y] // is upper-right to lower-left diagonal available
NOT promising if any of these are unavailable

8 Queens: Search Space

Brute force checks about $4.43 \times 10^9$ possibilities, including many ridiculous board configurations
Even with sensible choices (1 queen per row), the search space is still fairly large:
- 16,772,216 possibilities
- 92 solutions

Branch-and-Bound (B&B)¶

The idea of backtracking extended to optimization problems
You are minimizing a function with this useful property:
- A partial solution is pruned if its cost $\ge$ cost of best known complete solution
- Ex: the length of a path or tour
If the cost of a partial solution is too big, drop this partial solution

i. General Form

Algorithm checknode(Node v, Best currBest)
    Node u
    if (promising(v, currBest))
        if (solution(v)) then
            update(currBest)
        else
            for each child u of v
                checknode(u, currBest)
    return currBest

solution(): check "depth" of solution (constraint satisfaction)
update(): if new solution better than current solution, then update (optimization)
checknode(): called if promising and not solution
lowerbound(): Estimate of solution based upon
- Cost so far
- Under estimate of cost remaining
promising(): Different for each application, but must return true when lowerbound() < currBest
- A return of false is what causes pruning ($\ge$)

ii. The Key to B&B is the Bound

The efficiency of B&B is based on "bounding away" ("pruning") unpromising partial solutions
The earlier you know a solution is not promising, the less time you spend on it
The more accurately you can compute partial costs, the earlier you can prune
Sometimes it is worth spending extra effort to compute better bounds

iii. Minimizing with B&B

Start with an "infinity" bound
Find first complete solution - use its cost as an upper bound to prune the rest of the search
Measure each partial solution and calculate a lower bound estimate needed to complete the solution
Prune partial solutions whose lower bounds exceed the current upper bound
If another complete solution yields a lower cost - that will be the new upper bound
When search is done, the current upper bound will be a minimal solution

iv. Maximizing with B&B

Start with a "zero" bound
Find first complete solution - use its cost as a lower bound to prune the rest of the search
Measure each partial solution and calculate an upper bound estimate needed to complete the solution
Prune partial solutions whose upper bounds are less than the current lower bound
If another complete solution yields a larger value - that will be the new lower bound
When search is done, the current lower bound will be a maximal solution

Travelling Salesperson Problem (TSP)¶

i. TSP Defined

Hamiltonian Cycle
- Definition: Given a graph $G = (V, E)$, find a cycle that traverses each node exactly once
- No vertex may appear twice, except the first / last
- Constraints satisfaction problem
Travelling Salesperson Problem
- Definition: Hamiltonian cycle with least weight
- Optimization problem

ii. TSP Illustrated

Find tour of minimum length starting and ending in same city and visiting every city exactly once.

iii. TSP with Backtracking

ii. Bounding Function

Estimate must be $\le$ reality
The bounding function must have complexity better than just continuing TSP for the k vertices not yet visited
- For instance, $O(k^2)$ is the better than $O(k!)$ for most values of k
Sometimes vertices are connected so far, some vertices are not
For ONLY the unvisited vertices, connect them together with lowest possible cost
Then connect the visited vertices to the unvisited

Partial TSP Example

Current path: A - B - C. We need to find the best way to connect D, E, F, and G to each other.

Optimal TSP with Backtracking, Branch and Bound¶

i. Generating Permutations

 1     template <class T>
 2     void genPerms(vector<T> &path, size_t permLength) {
 3          if (permLength == path.size()) {
 4               // Do something with the path
 5               return;
 6          } // if
 7          if (!promising(path, permLength))
 8               return;
 9          for (size_t i = permLength; i < path.size(); ++i) {
10               swap(path[permLength], path[i]);
11               genPerms(path, permLength + 1);
12               swap(path[permLength], path[i]);
13          } // for
14     } // genPerms()

Given n vertices, need to find best path out of $(n - 1)!$ options, use genPerms()
Start with upper boudn that is "infinity", or better yet a fast calculation of a path that is guaranteed not shorter than optimal
Use the upper bound to prune the rest of the search, lowering it every time a shorter, complete path is found
Measure each partial solution, the path length of the first $1 \le k$ points and estimate the cheapest cost to connect the remaining $n - k$ points, this is the lower bound
Prune a partial solution if its lower bound exceeds the current upper bound
If another complete path is shorter than the upper bound, save the path and replace the upper bound
When the search is done, the current upper bound will be a shorest path