Please enable JavaScript.
Coggle requires JavaScript to display documents.
-Backtracking- and -Branch and Bound- - Coggle Diagram
-Backtracking- and -Branch and Bound-
Backtracking
Construct solutions one component at a time and evaluate such partially constructed candidates
State-Space Tree
Promising
Nonpromising
In the majority of cases, it's constructed in the manner of DFS
Examples
Hamiltonian Circuit problem
Subset-Sum problem
N-queens
problem
The hope is that a backtracking algorithm will be able to prune enough branches of its state-space tree before running out of time or memory or both.
Tricks that might help reduce the size of a state-space tree
Preassign values to one or more components of a solution
Rearrange
data of an instance given
Exploit the symmetry often present in combinatorial problems
Typically applied to difficult combinatorial problems for which no efficient algorithms for finding exact solutions possibly exist
Holds a hope for solving some instances of nontrivial sizes in an acceptable amount of time
Even if backtracking does not eliminate any elements
of a problem’s state space and ends up generating all its elements, it provides a specific technique for doing so, which can be of value in its own right
Branch and Bound
It 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
Examples
Knapsack Problem
Traveling Salesman Problem
Assignment Problem
It enable us to solve
many large instances of difficult combinatorial problems. As a rule, however, it is virtually impossible to predict which instances will be solvable in a realistic amount
of time and which will not.
A Branch and Bound algorithm can be sometimes accelerated by a knowledge of the objective function’s value of some nontrivial feasible solution.
In contrast to backtracking, solving a problem by branch-and-bound has both the challenge and opportunity of choosing the order of node generation and finding a good bounding function.