Many problems which deal with searching for a set of solutions or for a optimal solution satisfying some constraints can be solved using the backtracking formulation.
To apply backtracking method, the desired solution must be expressible as an n-tuple (X1…Xn) where Xi is chosen from some finite set Si.
Often the problem to be solved calls for finding one vector that maximizes (or minimizes or satisfies) a criteria function P(X1,X2, --- Xn). Sometimes it seeks all vectors that satisfy P.
Suppose mi is the size of set Si. Then the number of n-tuples may satisfy the criteria function P(x1,x2,---,xn) are m=m1,m2,---mn. The brute force approach would be to form all these n-tuples, evaluates each one with P, and save those which yield the optimum and save those which yield optimum.
In backtracking we will get the same answer but fewer than m trials. Its basic idea is to build up the solution vector one component at a time and to use modified criteria function P(x1,x2, ---xi) (sometimes called bounding functions) to test whether the vector being formed has any chance of success.
The major advantage of this method is if it is realized that the partial vector (x1,x2,---xi) can no way lead to an optimal solution, then mi+1….mn possible test vectors can be ignored entirely.
Many problems solved using backtracking require that all the solutions satisfy a complex set of constraints. These constraints are classified as
1.Explicit constraints
2.Implicit constraints
Top comments (0)