Data Structures and Algorithms with Object-Oriented Design Patterns in C#

Backtracking Algorithms

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