In this section we consider
*backtracking algorithms* .
As in the preceding section,
we view the problem to be solved as a sequence of decisions.
A backtracking algorithm systematically considers
all possible outcomes for each decision.
In this sense, backtracking algorithms are like the brute-force algorithms
discussed in the preceding section.
However, backtracking algorithms are distinguished by the way
in which the space of possible solutions is explored.
Sometimes a backtracking algorithm can detect that an exhaustive
search is unnecessary and, therefore,
it can perform much better.

- Example-Balancing Scales
- Representing the Solution Space
- Abstract Backtracking Solvers
- Branch-and-Bound Solvers
- Example-0/1 Knapsack Problem Again

Copyright © 1997 by Bruno R. Preiss, P.Eng. All rights reserved.