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