backtracking algorithms of ada

It contains all backtacking Applications like n queens, Graph Colouring and Himaltion Cycle........

1. 1
BACKTRACKING
GENERAL METHOD
•Problems searching for a set of solutions or which
require an optimal solution can be solved using the
backtracking method .
•To apply the backtrack method, the solution must
be expressible as an n-tuple(x
1,…,x
n), where the
x
i are chosen from some finite set s
i
•The solution vector must satisfy the criterion
function P(x
1, ….. , x
n).
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

2. 2
BACKTRACKING (Contd..)
•Suppose there are m n-tupleswhich are
possible candidates for satisfying the
function P.
•Then m= m
1, m
2…..m
nwhere m
iis size of
set s
i1<=i<=n.
•The brute force approach would be to form
all of these n-tuplesand evaluate each one
with P, saving the optimum.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

3. 3
BACKTRACKING (Contd..)
•The backtracking algorithm has the ability to yield
the same answer with far fewer than m-trials.
•In backtracking, the solution is built one
component at a time.
•Modified criterion functions P
i(x
1...x
n) called
bounding functions are used to test whether the
partial vector (x
1,x
2,......,x
i) can lead to an optimal
solution.
•If (x
1,...x
i) is not leading to a solution, m
i+1,....,m
n
possible test vectors may be ignored.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

4. 4
BACKTRACKING (Contd..)
•The constraints may be of two categories.
•EXPLICIT CONSTRAINTS are rules which restrict the
values of x
i.
Examples x
i
0 or x
1
= 0 or 1 or l
i
x
i
u
i.
•All tuplesthat satisfy the explicit constraints define a
possible solution space for I.
•IMPLICIT CONSTRAINTS describe the way in which
the x
i
must relate to each other .
•Implicit constraints allow to find those tuplesin the
solution space that satisfy the criterion function.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

5. 5
Example : 8 queens problem
•The problem is to place eight queens on an 8 x 8
chess board so that no two queens attack i.e. no two
of them are on the same row, column or diagonal.
•Strategy : The rows and columns are numbered
through 1 to 8.
•The queens are also numbered through 1 to 8.
•Since each queen is to be on a different row
without loss of generality, we assume queen i is to
be placed on row i .
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

6. 6
8 queens problem(Contd..)
•The solution is an 8 tuple(x
1
,x
2
,.....,x
8
)
where xi is the column on which queen i is
placed.
•The explicit constraints are :
S
i= {1,2,3,4,5,6,7,8} 1 i n or 1 x
i
8
i = 1,.........8
•The solution space consists of 8
8
8-tuples.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

7. 7
8 queens problem(Contd..)
The implicit constraints are :
(i) no two x
iscan be the same that is, all queens
must be on different columns.
(ii) no two queens can be on the same diagonal.
(i)reduces the size of solution space from 8
8
to 8!
8 –tuples.
Two solutions are (4,6,8,2,7,1,3,5) and
(3,8,4,7,1,6,2,5)
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

8. 8
8 queens problem(Contd..)
Q8
Q7
Q6
Q5
Q4
Q3
Q2
Q1
87654321
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

9. 9
State space tree representation
Solution Space:
•Tuplesthat satisfy the explicit constraints define a solution
space.
•The solution space can be organized into a tree.
•Each node in the tree defines a problem state.
•All paths from the root to other nodes define the state-
space of the problem.
•Solution statesare those states leading to a tuplein the
solution space.
•Answer nodesare those solution states leading to an
answer-tuple( i.e. tupleswhich satisfy implicit constraints).
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

10. 10
State space tree representation contd..
•The problem may be solved by systematically
generating the problem states determining which
are solution states, and determining the answer
states.
•Let us see the following terminology
•LIVE NODEA node which has been generated
and all of whose children are not yet been
generated .
•E-NODE (Node being expanded)-The live node
whose children are currently being generated .
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

11. 11
State space tree representation contd..
•DEAD NODE-A node that is either not to
be expanded further, or for which all of its
children have been generated.
•DEPTH FIRST NODE GENERATION -In
this, as soon as a new child C of the current
E-node R is generated, C will become the
new E-node.
R will become E-node again when C has
been fully explored.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

12. 12
State space tree representation contd..
•BOUNDING FUNCTION -will be used to
kill live nodes without generating all their
children.
•BACTRACKING-is depth –first node
generation with bounding functions.
•BRANCH-and-BOUNDis a method in
which E-node remains E-node until it is
dead.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

13. 13
State space tree representation contd..
•BREADTH-FIRST-SEARCH: Branch-and
Bound with each new node placed in a
queue .
The front of the queen becomes the new E-
node.
•DEPTH-SEARCH (D-Search): New nodes
are placed in to a stack.
The last node added is the first to be
explored.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

14. 14
Example : 4 Queens problem
1
. . 2
1
2
1
2
3
. . . .
1
1 1
2
3
. . 4
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

15. 15
State space tree: 4 Queens problem
1
x
1
= 1 x
1
=2
2 18
x
2
=2 3 4 x
2
=1 x
2
=3 x
2
= 4
B3 8 1319 2429
x
3
=3 x
3
=4 2 3 B B
46 14 16 x
3
= 1
x
4
=4 3 B 30
5 7 15 x
4
= 3
B 31
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

16. 16
State space tree: 4 Queens problem contd..
•If (x
1….x
i) is the path to the current E-node
, a bounding function has the criterion that
(x
1..x
i+1) represents a chessboard
configuration, in which no queens are
attacking.
•A node that gets killed as a result of the
bounding function has a B under it.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

17. 17
State space tree: 4 Queens problem contd..
•We start with root node as the only live node. The
path is ( ); we generate a child node 2.
•The path is (1).This corresponds to placing queen
1 on column 1 .
•Node 2 becomes the E node. Node 3 is generated
and immediately killed. (because x1=1,x2=2).
•As node 3 is killed, nodes 4,5,6,7 need not be
generated.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

18. 18
State space tree: 4 Queens problem contd..
•Node 8 is generated, and the path is (1,3).
•Node 8 gets killed as all its children
represent board configurations that cannot
lead to answer. We backtrack to node 2 and
generate another child node 13.
•But the path (1,4) cannot lead to answer
nodes.
•So , we backtrack to 1 and generate the
path (2)with node 18. We observe that the
path to answer node is (2 4 1 3 )
•Other solution is (3, 1, 4, 2)
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

19. 19
GENERAL BACKTRACKING METHOD
•All answer nodes are to be found
•If (x
1…..x
i) is a path from root to a node then T
(x
1,….,x
i) be the set of all possible values for Xi
+1,
such that (x
1,x
2,…….,x
i,x
i+1) is also a path from
root to a problem state.
•B(x
1…x
i+1) or B
xi+1is false for the path (x
1,..,x
i+1)
if the path cannot reach an answer node.
•The solution vectors X (1: n) are those values
which are generated by T and satisfy B
i+1.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

20. 20
GENERAL BACKTRACKING METHOD
(Contd..)
Procedure backtrack (n) // solution vectors are X(1:n)//
// and printed as soon as generated //
// T {X(1),….X(k-1)} gives all possible values of X(k)
// given that X(1),…..,X(k-1) have already been chosen //
// The predicates B
k
(X(1),….X(k) ) determine those
elements //
// which satisfy the implicit constraints //
// Implicit constraints are “no two X
i
s can be the same”//
Integer k, n; local X (1:n)
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

21. 21
GENERAL BACKTRACKING METHOD (Contd..)
K1
whileK <> 0 do
ifthere remained an untried X(k) such that X(k) 
T ( X (1) , …..X(k-1) ) and B
k
(X (1) ,…,X(k) ) = true then
if (X (1),…, X(k) ) is a path to an answer node then
print ( X (1) ,…X (k) ) // and proceed for another//
//solution with untried value of X(k)//
KK+1 // consider next set//
endif// end of if there remained ….//
else KK-1 // backtrack to previous component as no value of X(k)
//satisfies the constraints//
endif
repeat
end Backtrack
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

22. 22
EXAMPLE OF ALGORITHM WITH
4 QUEENS PROBLEMS
k1
loop 1 X0 =1,1{1,2,3,4} and B1 (X (1)) = true
1 is not a path to answer node
K 1+1=2
repeat K2
loop 2
X(2){2,3,4}and B
2(1,2) is False but there
remains untried X(k)=3 and X(K) =4
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

23. 23
EXAMPLE OF ALGORITHM WITH
4 QUEENS PROBLEMS (Contd..)
B
2(1,3)=true , but (1,3) Is not a path to
answer node ; so KK+1=3
There is no X(3) such that
B
3(1,3,2) or B
3 (1,3,4) is true .
So backtrack KK-1=2
consider X (2) 4
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

24. 24
EXAMPLE OF ALGORITHM WITH
4 QUEENS PROBLEMS (Contd..)
(1,4) is not a path to answer
(1,4,2) is not a path to answer
B
4
(1,4,2,3)=false.
Thus X(2)=4 is false
With X(1)=1, we have seen that there is no X(2)
satisfying the constraints so KK-1=2-1=1
There remained untried X(k)=2,3,4.
Repeating with X(1)=2, we observe (2,4,1, 3) is a path to an
answer node .
Similarly the other solution is (3,1,4,2)
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

25. 25
BACKTRACKING ALGORITHM WITH
RECURSION
Procedure RBACKTRACK (k)
// on entering the first K-1 values X(1),…..,X(k-1)//
// of the solution vector X(1:n) have been assigned //
global n , X(1:n)
for each X(k) such that
X(k) T ( X (1),..X(k-1) ) Do
if B
k
(X(1)..,X(k-1), X(k) )= true then {
if ( X (1) ,….,X(k) ) is a path to an answer node
then print ( X(1),……,X(k) ) endif
if (k<n)
CALL RBACKTRACK (k+1)
endif}// end of if B
k
(X(1)…//
repeat // end of for each X(k)…//
end RBACKTRACK
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

26. 26
BACKTRACKING ALGORITHM WITH
RECURSION (Contd..)
EXAMPLE (RB –RBACKTRACK)
Initially RB(1) is called
for each X(1) X(1) {1,2,3,4} and B1 (1) is
true , but 1 is not an answer node.
RB (2) is called
X(2) {2,3,4} and B
2(1,3) = true and B
2(1,4) = true
(1,3) is not an answer node , RB(3) is called,X(3) = 2,
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

27. 27
BACKTRACKING ALGORITHM WITH
RECURSION (Contd..)
but (1,3,2) is not Answer node , so , RB(4) is
called B4 (1,3,2,4) = false.
(1,3,4,2) is not bounded so , X(2) = 4 is tried
(1,4,2,3) is not bounded . With X(1)=1 no solution
Now for X(1) = 2,3,4 repeat
(2,4,1,3) is an answer node, other paths with X(1)
= 2 are not leading to answer node.
With X (1) = 3 , (3,1,4,2) is an answer node.
X (1) = 4 -no solution.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

28. 28
EFFICIENCY OF BACKTRACKING (BT)
ALGORITHM
•The time required by a backtracking algorithm or the
efficiency depends on four factors
(i)The time to generate the next X(k);
(ii) The number of X(k) satisfying the explicit
constraints
(iii) The time for bounding functions B
i
(iv) The number of X(k) satisfying the B
ifor all i.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

29. 29
EFFICIENCY OF BACKTRACKING
ALGORITHM (Contd..)
•The first three are relatively independent of
the problem instance being solved.
•The complexity for the first three is of
polynomial complexity .
•If the number of nodes generated is 2
n
, then
the worst case complexity for a
backtracking algorithm is O(P(n)2
n
) where
P(n) is a polynomial in n .
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

30. 30
Estimation Of Nodes generated in a
BT Algorithm
•Generate a random path in the state space tree.
•Let X be a node at level i on this path.
•Let m
ibe the children of X ( at level i+1 ) that do
not get bounded. (i.e. mi are the nodes which can
be considered for getting an answer node ).
•Choose randomly one of the m
i.
•Continue this until this node is either is a leaf or
all its children are bounded.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

31. 31
Estimation of Nodes generated in a
BT Algorithm (Contd..)
•Let m be the no. of unbounded nodes to be
generated.
•Let us assume that the bounding functions
are static, i.e., the BT algorithm does not
change its bounding functions.
•The number of estimated number of
unbounded nodes
=1+m
1+m
1m
2+….. +m
1m
2m
3..mi where mi is
the estimated no. of nodes at level i+ 1.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

32. 32
Estimation of Nodes generated in a
BT Algorithm (Contd..)
•The number of unbounded nodes on level one
is 1.
•The number of unbounded nodes on level 2 is
m
1
•The total no. of nodes generated till level 2 is
1 + m1
The total number of nodes generated till level
i+1is 1+m
1+…+m
1…m
i .
–The above procedure can be written as an algorithm.
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

33. 33
Estimation of Nodes generated in a BTAlgorithm(Contd..)
Procedure Estimate
// This procedure follows a random path and estimates//
// number of unbounded nodes //
m1; r1; k1
loop
T
k
{X (k): X(k) T ( X(1) ,….X(k-1)) and B
k
(X (1), ….,
X(k)) is TRUE}
If size (T
k
) = 0 then exit endif// SIZE returns the //
r r * SIZE (Tk) // size of the set T
k
//
m m+r
X (k) CHOOSE (T
k
) // CHOOSE makes a random
choice of an element in T
k
//
kk+1
repeat
return (m)
end estimate
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)

34. 34
•In implementing the n –queens problem we
imagine the chessboard as a two -
dimensional array A (1 : n, 1 : n).
•The condition to test whether two queens, at
positions (i, j) and (k, l) are on the same row
or column is simply to check i = k or j = l
The n-queens problem and solution
Create PDF files without this message by purchasing novaPDF printer (http://www.novapdf.com)