KHADAR SIR 9966648277
BACKTRACKING: A backtracking algorithm is a problem-solving algorithm.
Backtracking says that if the step you take is not the right one, go back and try
another way. Therefore, recursion is used in this approach. This approach is used
to solve problems that have multiple solutions.
General algorithm:
Backtracking(Current_depth)
{
if(current_depth:n)\
print "X"
else
for each A[1]toA[n]
{X[current_depth+1]-A[i):
if(promising(X,current_depth+1)
Backtracking(current_depth+1):
the method promising() is used to determine whether the next element ispromising or not.
Backtracking Algorithm Applications:
To find all Hamiltonian Paths present ina graph.
Tosolve the N Queen problem.
Maze solving problem.
The Knight's tour problem.
V Sum of subsets problem.
Iterative Backtracking algorithm
Algorithm:
Backtracking(n)
k=1;
while (k<n)
for each A[1] to A[n(
X[k]-=A[i);:
if(promising(X))X
k++;
remove A[0:
break:
print X[];:
KHADAR SIR 9966648
loop will be terminat.
nere X IS asolution vector, if kreaches to n then outer
and print function prints the solution.
represents all possibl
STate space Tree: The State space Tree is atree that
solutions (solution or non-solution) of a problem. backtracking
state-space tree follows the depth-first search method for the
The
algorithm. the current node is promising, its
child will be
We can make any node as root. If
generated. The same process continues for all possibilities.
8 QUEEN PROBLEM two
queens in 8*8 chessboard such that no
The 8 queen problem is to place 8
attack each other. twoqueens are said to be attacking each other if they
queens
diagonal, the backtracking strategy
are in the same row or same column or same
queeninthe top left corner
tosolve thisproblem finds solution by starting with a
the second row and moves it until
of the chess board. it then places aqueen in
the first row. it then places
it finds a place where it cannot be hit by the queen in
cannot be hit by the first two
a third queen in the third row and moves it until it
rows. if there is no place
queen then it continue this process with the remaining
preceding row and
for the queen in the current row then program goes to the
moves the queen in that row.
been found for the last
if the current row is the last row and a safe place has
found.
queen, then asolution for the problem has been
one of the possible solution is as follow.
Algorithm:
_8Queens(row)
{
if(row==8)
printsolution():
exit():
for(col =0 to 7)
if(! attacked(row, col))
SIR 9966648)
erminata PutQueen(row, col):
_8Queen(row*1):
KHADAR SIR 9966648277
sible RemoveQueen(row,col):
Example: 4 queen problem: Placing 4 queens in a 4*4 chessboard such that no
two queens attack each other. This means that two queens cannot be placed in
the same column, same row and same diagonals.
If ( )is the position of Q1 and (p.g) is the position of Q2 then
If i=p, it means that two queens are in the same row
If j-g, it means that two queens are in the same column
" If i-j=p-q or i+j=ptq it means that two queens are in the same diagonals
State
space tree for 4 queen problem:
Root
1,1) 1,2 1,3 1,4 Positions for Queen 1
R2)(2.3 2,4
Positions for Queen 2
Node (2,1) s dead node because Q1and Q2 both in same column.
Node (2,2) is dead node because Q1and Q2 both in same diagonal.
Solution-1= [(1,2),(2,4),(3,1),(4,3)]
Solution-2 = [(1,3).(2,1),(3,4).(4,2)]
HAMILTONIAN CYCLES: Given a connected, undirected graph, a Hamiltonian
cycle is the path that starts from a given vertex, visit each vertex in the graph
exactly once and ends at the starting vertex. A graph may or may not contain a
Hamiltonian cycle.
For the above araph the Hamiltonian cycle would be
[V1, v2, v5, v6, V7, V8, v4, v3, vl]
KHADARSIR 9966641 igorithm
procedure to Find the Hamiltonian Cycle using Backtracking: two
Using the backtracking method, we can easily find all the Hamiltonian Cycit
a
1 Sa n e
present in the given graph.
The idea is to use the Depth-First 5earch algorithm to traverse the graph unt
outp
HAA
allthe vertices have been visited.
We traverse the graph starting from a vertex (arbitrary vertex chosen as
starting vertex)and
At any point during the traversal we get stuck (i.e., allthe neighbor vertices have
been visited), we backtrack to find other paths (.e., to visit another unvisited
vertex).
Ifwe successfully reach back to the starting vertex after visiting all the nodes,
it means the graph has a Hamiltonian cycle otherwise not.
We mark each vertex as visited so that we don't traverse them more than once.
Example: Example: Consider agraph G= (V,E) shown in fig. we have to find a
Hamiltonian circuit using Backtracking method.
Solution: You can start with any node. If we start with 'a' then state space tree is:
State space tree for Hamiltonian cycle:
Root
Ce)
Dead end
(a) Solution
In the atbove tree 'f' is adead node because all the nodes from root to 'f' haye
beenvisited but there is no path togo from 'f' back to the starting node.
Ifound one solution. If you want all possible solutions Alllive nodes should ko
expanded using DFS technique.
964827n KHADAR SIR 9966648277
Algorithm: an undirected graph containing n vertices. the graph is represented
w[ÜJis true if there
by atwo dimensional array w, with index from 1 to n, where
otherwise.
is an edge between the ith vertex and jth vertex, and false
output: vindex[] - array of vertices;
HAMILTONIAN(index)
{
if(promising(index))
if(index==n-1)
print vindex[]:
else
for(j=2: je=n:j++)
vindex[index+1]-j:
HAMILTONIAN(index+1):
Promising()
if(iz=n-1&& !W[vindex[n-1][vindex[1])
return false;
if(i»18& !W[vindex[i-1][vindex[i)
return false:
for(j=1 to i-1)
{ if! W[vindex[i][==vindex[j])
return false;
return true;
KNAPSACK PROBLEM USING BACKTRACKING
Dlem: let there be ninputs with each item having a weight and a profit. let
there be an integer Wthat represent the maximum capacity of the bag. then the
KHADAR SIR 99666482)
total profit such that sum
maximum
with
problem is to determine a set of items
exceed W. also
an item must be
should not
of the weight of selected item fraction part of an item should not be
that is
not at all,
selected Completely or
selected.
Algorithm:
capacity and number of items
input: Wand n represents
w[i] contains weight and pi] contains
indexed from 1 to n.
Two arrays wandp
corresponding profit.
KNAPSACK(i, profit, weight)
if(i==n)
maxprofit=profit:
print sol[]
return,
if(Promising(i)
sol[i+1]-1;
KNAPSACK(i+1,profit+p[i+1], weight+w[i*1)
backtrack
Sol[i+1]=0: //do not include the item &
Knapsack(i+1, profit, weight):
Promising(index)
if(weight>W)
return false:
else
jzindex+1;
bound=profit:
totalweight=weight:
while(jc=n &£ totalweight*w[indexk=W)
{
totalweight=totalweight+wjl:
AR SIR 99666482
hthat sun KHADAR SIR 9966648277
bound=bound+pjl
musnot t be be jt;
return(bound >maxprofit)
}
}
Example:
N=4, C= 15,P[J= (1010 12 18), w[]= {2 4 6 9}
Let the first node be the root node of state space tree:
1. Visit node (0,0)
" Set its profit and weight to 0;
included. Visit node (1, 0)
2. Let us consider that item 1 is
compute its profit and wieght:
profit =profit (profitof parent) +p[1] -10
=2
profit =weight (profit of parent) +w[1]
included. Visit node (1,1)
3. Let us consider that item 1 is not
Compute its profit and weight:
profit = profit (profit of parent) =0
profit weight (profit of parent) =0
because backtrackingfollows
4. Since level_1 is complete,Now expand node (2,0)depth should be visited. Now
DFS. If one depth is complete then another
Visit (2,0).
consider that items 1 and 2 both are included.
less than the qiven
Note: The weight of the node to be expanded should be
capacity.
compute its profit and wieght:
profit =profit (profit of parent) + p[2] =10+10=20
profit =weight (profitof parent) + w[2] =2+4-6
Visit (2.1)
5. Nowconsider that item 1is included and 2 is not included,
Compute its profit and weight:
profit =profit (profit of parent) =10
profit =weight (profit of parent) =12
less than the
6. According to DFS the next node to visit is (3,0). Its weight is
given capacity so visit.
KHADAR SIR 9966648277
10
2
20
6 10
Node (4,0) is adead node because its weight
2
exceeds the given capacity. Delete it. Come back
32
20 and go to the next depth. Each leaf node gives a
12 solution. We use backtracking to find all possible
6
solutions.
50
21 32 Node (4,1) is aleaf node because there are no
12 further items to ddd. The solution given by this
leaf node is [1,1,1,0].
