Please enable JavaScript.
Coggle requires JavaScript to display documents.
Algorithm design technique for large instance problems: - Coggle Diagram
Algorithm design technique for large instance problems:
Backtracking
construct solutions one component at a time and evaluate such partially constructed candidates
If a partially constructed solution can be developed further without violating the problem’s constraints, it is done by taking the first remaining legitimate option for the next component.
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.
General Remarks:
most backtracking algorithms fit the following description:
An output of a backtracking algorithm can be thought of as an n-tuple (x1,x2,...,xn) where each coordinate Xi is an element of some finite linearly ordered set S.
Depending on the problem, all solution tuples can be of the
same length
and of
different lengths
A backtracking algorithm generates, explicitly or implicitly, a
state-space tree
.
its
nodes
represent partially constructed tuples with the
first i coordinates defined by the earlier actions of the algorithm.
If such a tuple (x1,x2,...,Xi) is not a solution, the algorithm finds the next element in Si+1 that is consistent with the values of (x1,x2,...,Xi) and the problem's constraints, and adds it to the tuple as its(i+1)st coordinate
If such an element does not exist,
the algorithm backtracks to consider the next value of xi, and so on.
Implementation:
construct a tree of choices being made, called the
state-space tree
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.
A node in a state-space tree is saido to be
promising
if it corresponds to a aprtially constructed solution that may still lead to a complete solution, otherwise, its called
nonpromising
the
nodes of the second level
represent the choices for the
second
component
...
Leaves
represent either nonpromising dead ends or
complete solutions found by the algorithm.
In the majority of cases, a statespace tree for a backtracking algorithm is constructed in the manner of
depthfirst search
If the
current node is promising
, its child is genereted by adding the first remaining legitimate option for the next component of a solution, and the processing moves to this child.
If the
current node turns out to be nonpromising
, the algorithm backtracks to the node's parent to consider the next possible option for its last component, if there is no such option it backtracks one more level up the tree,
and so on...
Finally:
If the algorithm reaches a complete solution to the problem, it either stops or continues searching for other possible solutions
Branch-and-bound
feasible solution
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
Compared to backtracking, branch-and-bound 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 funcion 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
If this information is available, 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 and not larger for a maximization problem---the node is nonpromising and can be terminated.
No solution obtained from it can yield a better solution than the one already avaiable.
We terminate a search path at the current node in a state-space tree of a branch-and-bound algorithm for any of the following three reasons:
The value of the node's bound is not better than the value of the best solution seen so far.
The node represents no feasible solutions because the constraints of the problem are already violated.
The subset of feasible solutions represented by the node consists of a single point, in this case, we compare the value of the objective function for this feasible solution with that of the best solution seen so far and update the latter with the former if the new solution is better.