Backtracking and Branch-and-Bound
Backtracking
Branch-and-Bound
It is considered to be an improvement over exhaustive search
They construct candidate solutions one component at a time and evaluate the partially constructed solutions: if no potential values of the remaining components can lead to a solution, the remaining components are not generated at all
Based on a construction of a state-space tree
Applicable only to optimization problems
It applies to non optimization problems, but not constrained to it
Depth-first
Best-first
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows
Examples
The n-Queens problem
Hamiltonian circuit problem
Subset-sum problem
Cut off a branch of the problem’s state-space tree as soon as we can deduce that it cannot lead to a solution
Examples
Requires two additional items
A way to provide, for every node of a state-space tree, a bound on the best value of the objective function on any solution that can be obtained by adding further components to the partially constructed solution represented by the node
The value of the best solution seen so far
Assignment problem
Knapsack problem
Traveling salesman problem