Backtracking: Backtracking is one of
the most general techniques for searching a set of solutions or for searching
an optimal solution. It is used to find all possible solutions available to the
problem. It involves feasibility function. Application of backtracking are
knapsack, sum of subset.
There
are four factors for efficiency of the backtracking algorithm:
(i)
Time
to generate the next Xk.
(ii)
Number
of Xk satisfying the explicit constraints.
(iii)
Time
for the bounding function Bk.
(iv)
Number
of Xk satisfying Bk.
The
first three relatively independent of the problem instance and last is
dependent.
No comments:
Post a Comment