0% found this document useful (0 votes)
38 views24 pagesUnit 2 Backtracking
Daa
Uploaded by
Bhavani SaiCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
0% found this document useful (0 votes)
38 views24 pagesUnit 2 Backtracking
Daa
Uploaded by
Bhavani SaiCopyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF or read online on Scribd
/ 24
DAA Unit-2 UNIT-
BACKTRACKING
BACKTRACKING
* Itisone of the most general algorithm design techniques.
‘* Many problems which deal with searching for a set of solutions or for a optimal solution sat
some constraints can be solved using the backtracking formulation.
fying
© 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.
* The problem is to find a vector, which maximizes or minimizes a criterion function P(x1...xn),
+ The major advantage of this method is, once we know that a partial vector (x1,...xi) will not lead
to an optimal solution that (mi......1M) possible test vectors may be ignored entirely.
* Many problems solved using backtracking require that all the solutions satisfy a complex set of
constraints.
© These constraints are classified as:
i) Explicit constraints.
ii) Implicit constraints.
1) Explicit constraints: Explicit constraints are rules that restrict each Xi to take values only from
agiven set.
Some examples are,
Xi2 0 or Si= {all non-negative real nos.)
Xi=0 or 1 or Si=(0,1).
asUi}
+ All tupules that satisfy the explicit constraint define a possible solution space for I
2) Implicit constraints: The implicit constraint determines which of the tuples in the solution space
of I satisfy the criterion function, The implicit constrains describe the way in which the xi must
relate to each other.
Example : In 4 - queen problem, The implicit constrains are no queens can be on the same
column, same row and same diagonal. CONTROL ABSTRACTION OF BACKTRACKING:
The control abstraction is also called as general method for backtracking is as follows. Let ( X1, X2,
Xi) be the set of
+1 Jis also a path to a problem state. We assume
x3,
all possible values for xit1 such that ( X1, X2, X3, .
Xi) bea path from the root to a node in a state space tree. Let (X1, X2, X3, ..
the existence of bounding function Bi+1 such that if Bi+1( X1, X2, X3,
X2, X3,
i +1 ) is false for a path ( X1,
Xi +1) from the root node to problem state, then the path cannot be extended to reach an
answer node.
Algorithm : Backtracking (k)
{
for (each x{k] €T (x[1], ox [k- 1] do
{
if (Bk (x{1],x[2],....x[k] # 0) then
{
if (x[1], x[2],.... x{k] is a path to an answer node ) then
write (x[1:k]);
if (k
