Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking and Branch-and-Bound - Coggle Diagram
Backtracking and Branch-and-Bound
Backtracking
It applies to non optimization problems, but not constrained to it
Depth-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
Branch-and-Bound
Applicable only to optimization problems
Best-first
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
Assignment problem
Knapsack problem
Traveling salesman problem
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
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