UNIT 4
Chapter 7
BACKTRACKING (General Method)
Definition
Depth First node generation with bounding function is called backtracking.
Suppose mi is the size of set Si. Then there are m=m1,m2…..mn n-tuples that are
possible candidates for satisfying the function P.
The Backtrack algorithm has its virtue the ability to yield the answer with far
fewer than m trials. It’s basic idea is to build up the solution vector one
component at a time and to use modified criterion functions Pi(x1,……..xi) to test
whether the vector being formed has any chance of success.
If it is realized that partial vector (x1,……..xi) can in no way lead to an optimal
solution, then mi+1,….mn possible test vectors can be ignored entirely.
Problems solved through backtracking require that all the solution satisfy a
complex set of constraints. i.e, (Implicit, Explicit constraints).
No comments:
Post a Comment