Design And Analysis of Algorithms – Study Material - B.Sheik Md Abdullah ,MIIT

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).