Please enable JavaScript.
Coggle requires JavaScript to display documents.
Backtracking and Branch and Bound - Coggle Diagram
Backtracking and Branch and Bound
two algorithm design techniques that often make it possible to solve at least some large instances of difficult combinatorial problems
This approach makes it possible to solve some large instances of difficult combinatorial problems though, in the worst case, we still face the same
curse of exponential explosion encountered in exhaustive search.
Branch-and-bound is applicable only to optimization problems because it is based on computing a bound on possible values of the problem’s objective function.
Note that in the standard terminology of optimization problems, a feasible solution is a point in the problem’s search space that satisfies all the problem’s constraints
requires two additional items:
:one: a way to provide, for every node of a state-space tree, a bound on the best
value of the objective function1 on any solution that can be obtained by adding further components to the partially constructed solution represented by the node
:two: the value of the best solution seen so far
In general, we terminate a search path at the current node in a state-space
tree of a branch-and-bound algorithm for any one of the following three reasons:
:check: The value of the node’s bound is not better than the value of the best solution seen so far.
:check: The node represents no feasible solutions because the constraints of the problem are already violated.
:check: The subset of feasible solutions represented by the node consists of a single point
a feasible solution
is a point
in the problem’s search space that satisfies all the problem’s constraints
optimal solution
is a feasible solution with the best value of the objective function
we can compare a node’s bound value with
the value of the best solution seen so far. If the bound value is not better than the value of the best solution seen so far the node is nonpromising and can be terminated
Backtracking
is not constrained by this demand, but more often than not, it applies to nonoptimization problems.
The principal idea is to construct solutions one component at a time and evaluate such partially constructed candidates as follows.
It is convenient to implement this kind of processing by constructing a tree of choices being made, called the
state-space tree
(or a backtracking algorithm is constructed in the manner of depth-first search)
Its root represents an initial
state before the search for a solution begins. The nodes of the first level in the tree represent the choices made for the first component of a solution and so on.
A node in a state-space tree is said to be
promising
if it corresponds to a partially constructed solution that may still lead to a complete solution; otherwise, it is called
nonpromising
.
Leaves represent either nonpromising dead ends or complete solutions found by the algorithm.
If there is no legitimate option for the next component, no alternatives for any remaining component need to be considered.
the algorithm backtracks to replace the last component of the partially constructed solution with its next option.
An output of a backtracking algorithm can be thought of as an
n-tuple
where each coordinate xi is an element of some finite linearly ordered set
Si.
backtracking isn't a
very efficient technique. In the worst case, it may have to generate all possible candidates in an exponentially (or faster) growing state space of the problem at hand.
The success of this strategy is known to vary widely, not only from problem
to problem but also from one instance to another of the same problem.
Both backtracking and branch-and-bound
are based on the construction of a state-space tree whose nodes reflect specific choices made for a solution’s components
other
distinction
between backtracking and branch-and-bound lies in the order in which nodes of the state-space tree are generated.
For backtracking, this tree is usually developed
depth-first
:one: it is typically applied to difficult combinatorial problems for which no efficient algorithms for finding exact solutions possibly exist.
:two: backtracking at least holds a hope for solving some instances of nontriv-
ial sizes in an acceptable amount of time(unlike the the exhaustive- search approach)
:three: 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.
Both technique
s terminate a node as soon as it can be guaranteed that no solution to the problem can be obtained by considering choices that correspond to the node’s descendants.