BASIC SEARCH AND TRAVERSAL TECHNIQUES
AND/OR Graphs
Breaking down a problem into several subproblems such that the solu on of all or some of
these subproblems results in a solu on of the original problem is called problem reduc on.
If a subproblem is found to be s ll complex, it may be broken down further into sub-
subproblems and so on un l the only problems remaining are trivially solvable. Problem
reduc on is used in theorem proving, analysis of industrial schedule. Problem reduc on can
be represented by an AND/OR graph. It is a directed graph in which nodes represent
problems and descendants of a node represent the subproblems associated with it.
Some de ni ons:
OR node: A node that can be solved by solving one of its descendants.
BACKTRACKING
Backtracking is used for nding a set of solu ons or an op mal solu on sa sfying some
constraints.
The desired solu on must be expressible as an n-tuple (x1, x2,….,xn) where xi is chosen from
some nite set Si.
O en, we come across problems for which we have to nd a solu on vector which
maximizes (or minimizes) a criterion func on P(x1, x2,….,xn).
Backtracking is mainly used to nd solu ons that sa sfy a complex set of constraints:
i) Explicit constraints: These constraints restrict each xi to take on values only from a given
set. E.g., in 0/1 Knapsack problem, xi= 0 or 1, i.e., Si={0,1}.
All tuples that sa sfy the explicit constraints de ne a possible solu on space for the problem
instance, I.
ii) Implicit constraints: These constraints determine which of the tuples in the solu on space
of I actually sa sfy the criterion func on.
E.g., for O/1 Knapsack, the tuple with maximum pro t.
The 8-queens problem
Place eight (8) queens on an 8x8 chessboard so that no two queens a ack, i.e., no two
queens are on the same row, column or diagonal. So the solu on vector is (x1, x2,….,xn)
where n=8. Here, xi denotes the column posi on in which queen i is placed. We assume that
queen i is placed on row i.
Q
Q
Q
Q
Q
Q
ft
ti
fi
fi
ti
ti
ti
ti
fi
ti
fi
ti
ti
ti
ti
ti
ti
ti
fi
ti
fi
ti
fi
ti
ti
ti
ti
ti
tt
ti
ti
ti
ti
Q
Q
i) Explicit constraints: So, xi ϵ Si, where Si={1,2,3,4,5,6,7,8}.
Thus, the solu on space consists of 88 tuples.
(x1,x2,x3,x4,x5,x6,x7,x8)
1,1,1,1,1,1,1,1
1,1,1,1,1,1,1,2
1,1,1,1,1,1,1,3
…………..
………..
8,8,8,8,8,8,8,8
8x8x8x8x8x8x8x8= 88 tuples in the solu on space.
ii) Implicit constraints: a) No two xi‘s are the same (i.e., no two queens on the same column).
b) No two queens are on the same diagonal.
The n-queens problem is a generaliza on the of the 8-queens problem.
To reduce the solu on space, we can move some constraint from the implicit constraints to
the explicit constraints. For instance for the 8-queens problem:
i) Explicit constraints: So, xi ϵ Si, where Si={1,2,3,4,5,6,7,8} and xi ≠ xj if i ≠ j, i.e., no two xi‘s
are on the same (i.e., no two queens on the same column).
Thus, the solu on space consists of 8! tuples.
(x1,x2,x3,x4,x5,x6,x7,x8)
1,2,3,4,5,6,7,8
1,2,3,4,5,6,8,7
……
…..
8x7x6x5x……x1 = 8! tuples in the solu on space.
ii) Implicit constraints: No two queens are on the same diagonal. O
0/1 Knapsack problem:
i) Explicit constraints.= xi ϵ Si, Si={0,1}.
What is the size of the solu on space when n=4?
(x1,x2,x3,x4)
2X2x2x2 = 24 tuples in the solu on space
ii) Implicit constraints= the tuple that gives maximum pro t.
The solu on space can be represented graphically by the state space tree.
Generate the problem states (nodes) in the tree. Determine which are solu on states
(nodes) and nally determine which solu on states are answer states (nodes).
ti
fi
ti
ti
ti
ti
ti
ti
ti
ti
fi
ti
A solu on node represents a tuple in the solu on space.
Live node: A node which has been generated and all of whose children are not yet
generated.
E-node (node being expanded): The live node whose children are currently being generated.
Dead node: A generated node which is not to be expanded further or one for which all of its
children have been generated.
Bounding func ons will be used to kill nodes without genera ng all their children.
Backtracking involves genera ng the tree to get to the answer node(s).
Depth rst genera on of the state space tree with bounding func ons is called Backtracking.
Why is backtracking called ‘method of last resort’?
- A backtracking algorithm on one problem instance might generate only O(n) nodes while
on a di erent instance it might generate almost all the nodes in the state space tree. If the
number of nodes in the solu on space is 2n or n!, the worst case me for a backtracking
algorithm will generally be O(p(n)2n) or O(q(n)n!) respec vely, where, p(n) and q(n) are
polynomials in n. The advantage of backtracking is the ability to solve some instances with
large n in a very small amount of me. The only di culty is in predic ng the behaviour of
the algorithm for the problem instance we wish to solve. Thus, when we use backtracking, if
we are unlucky, we could end up taking me, of the order of O(p(n)2n) or O(q(n)n!),
depending on the size of the state space tree.
This is the reason why backtracking is called a method of last resort. We try not to use it
unless there are other op ons.
Nqueens(i,n) //Ini al call is Nqueens(1,n)
begin
for j:=1 to n do //n columns
if Place(i,j)==true then //Can I place a queen in ith row at column j.
x[i] = j;
if (i==n) then //an answer found, all queens are placed
print(x[1:n]);
else
Nqueens(i+1,n)
endif
endif
endfor
end
Place(i,j)
//returns true if x[i] can be assigned with j. Can ith queen be placed on column j?
//Otherwise false. x is a global array whose rst i-1 values have been set.
begin
for l = 1 to i-1 do
if (x[l]==j) or abs(l-i)==abs(x[l]-j) then
ti
fi
ff
ti
ti
ti
ti
ti
ti
ti
ti
fi
ti
ffi
ti
ti
ti
ti
ti
//on same col or same diagonal
return false;
endif
endfor
return true;
end
Applica ons of N-queens problem:
It has found several real-world applica ons, including prac cal task scheduling and
assignment, computer resource management, and VLSI tes ng
Reference: P, S.S., 2011. New decision rules for exact search in n-queens. J. Global Op m.
497–514.
Sums of Subsets
Given n+1 numbers, wi, 1<=i<=n and M, nd all subsets of wi, whose sum is M.
E.g., n =4, (11,13,24,7), M=31.
Solu on subsets are (11,13,7) and (24,7).
Variable-size tuple formula on: A solu on is represented by a tuple, (x1, x2,.., xk), where
1<=k<=n and , xi= {j|j is an integer, 1<=j<=n}.
Thus, the solu ons for the above problem instance is denoted by (x1, x2, x3) = (1,2,4), and
(x1, x2)=(3,4).
i) Explicit constraints: xi= {j|j is an integer, 1<=j<=n}. No two subsets should be the same. So,
xi < xi+1, 1<=i<n.
NOTE: The corresponding state space tree consists of 2n nodes. Each node, except the root
node represents a solu on node, or in other words, a tuple that sa s es the explicit
constraints.
ii) Implicit constraints: Sum of the subset is equal to M.
Fixed-size tuple formula on: A solu on is represented by a tuple, (x1, x2,.., xn) and xi= {0,1},
1<=i<=n.
Thus, the solu ons for the above problem instance is denoted by (x1, x2, x3, x4) = (1,1,0,1),
and (x1, x2, x3, x4)=(0,0,1,1).
i) Explicit constraints: xi= {0,1}.
NOTE: The corresponding state space tree consists of 2n leaf nodes. Each leaf node
represents a solu on node, or in other words, a tuple that sa s es the explicit constraints.
ii) Implicit constraints: Sum of the subset is equal to M.
A bounding func on is used to decide whether a par cular assignment, xk will lead to a
solu on. Otherwise, the node that represents it in the state space tree is killed. Using the
xed-size tuple formula on, the bounding func on is given by:
fi
ti
ti
ti
ti
ti
ti
ti
ti
ti
ti
ti
ti
ti
ti
fi
ti
ti
ti
ti
ti
fi
ti
fi
ti
k n
∑(
wi xi) +
∑ ( i)
w >= M
i=1 i=k+1
Only if the above is true, then the assignment so far, i.e., x1…… xk can lead to a solu on.
Otherwise it will not, since adding all the remaining weights to the solu on found so far will
yield a sum which is less than M.
sumofSubs(k,n) //Ini al call is sumofSubs (1,n)
begin
for i:=0 to 1 do //only two choices: 0 or 1
if Admissible(k,i)==true then
x[k] = i;
if (k==n) then //check whether the sum == M
sum = 0;
for j = 1 to n do
sum = sum + x[j].w[j];
endfor
if sum==M then //answer found
print(x[1:n]);
endif
else sumofSubs(k+1,n)
endif
endif
endfor
end
Admissible (k,i)
//returns true if x[k] can be assigned with i.
//Otherwise false. x is a global array whose rst k-1 values have been set.
begin
sum=0;
for j = 1 to k-1 do
sum = sum + x[j].w[j];
endfor
sum = sum + i.w[k];
for j = k+1 to n do
sum = sum + w[j];
endfor
ti
fi
ti
ti
if sum < M then
return false;
else
return true;
endif
end
Graph Coloring
Let G be a graph and m be a posi ve integer. Can nodes of G be colored in such a way that
no two adjacent nodes have the same color yet only m colors are used? This is called the m-
colorability decision problem? It is known that if the degree of the given graph is d, then it
can be colored with d+1 colors.
The m-colorability op miza on problem seeks for the smallest integer m for which a graph
G can be colored. This number is called the chroma c number of the graph.
A graph is planar i it can be drawn on a plane such that no two edges cross each other.
Assume an m-colorability decision problem where the number of nodes in the graph is n.
Fixed-size tuple formula on: A solu on is represented by an n-tuple, (x1, x2,.., xn)
i) Explicit constraints: xi= {j|j is a posi ve integer, 1<=j<=m}.
The size of the solu on space is mn. That is, there are mn leaf nodes in the state space tree.
ii) Implicit constraints: xi ≠ xj if there exists an edge (i,j). That is, no two adjacent nodes are
given the same color.
mColoring(k,n,m) //Ini al call is mColoring(1,n,m)
begin
for i:= 1 to m // m colors numbered 1 to m.
if Colorable(k,i)==true then
x[k] = i;
if (k==n) then //all the nodes are colored
print(x[1:n]);
else
mColoring(k+1,n,m);
endif
ff
ti
ti
ti
ti
ti
ti
ti
ti
ti
endif
endfor
end
Colorable(k,i)
//returns true if x[k] can be assigned with i, i.e., node k can be assigned color i.
//Otherwise false. x is a global array whose rst k-1 values have been assigned already.
begin
sum=0;
for j = 1 to k-1 do //check whether i clashes with any other assigned colors
if adjacent(j,k)==true and x[j]==i then
//node k is adjacent to j and same color
return false;
endif
endfor
return true;
end
4-color problem for planar graphs:
Given any map, can the regions be colored in such a way that no 2 adjacent regions have the
same color, yet only four colors are used? For several years, 5 colors were thought to be
su cient. But a er several hundred years, a group of mathema cians solved it with the help
of a computer. Yes, 4 is su cient.
Hamiltonian Cycle
Let G=(V,E) be a connected graph with n ver ces. A Hamiltonian cycle (suggested by Sir
William Hamilton) is a round–trip path along n edges of G that visits every vertex once and
returns to its star ng vertex.
A TSP tour is a Hamiltonian cycle with the least cost.
A Hamiltonian path is a path that visits every vertex exactly once.
Use backtracking to nd all Hamiltonian cycles in a graph. Only dis nct cycles are output.
Fixed-size tuple formula on: A solu on is represented by an n-tuple, (x1, x2,.., xn), where xi is
the ith visited vertex of the cycle. Let x1=1 to avoid prin ng a cycle many mes.
i) Explicit constraints: xi= {j|j is a posi ve integer, 1<=j<=n} and x1 = 1. xi ≠ xj if i ≠ j.
The size of the solu on space is 1.(n-1).(n-2)….1 = (n-1)!. That is, there are (n-1)! leaf nodes
in the state space tree.
ii) Implicit constraints: xi is adjacent to xi-1 and xn is adjacent to 1, for 1<=i<=n.
Hamiltonian(k,n) //Ini al call is Hamiltonian(2,n)
//x[1] has been assigned 1 already in the main module before calling Hamiltonian(2,n)
ffi
ft
ti
ti
fi
ti
ti
ffi
ti
ti
fi
ti
ti
ti
ti
ti
Begin
for i:= 2 to n // vertex 2 to vertex n
if Assign(k,i)==true then
x[k] = i;
if (k==n) then //all the nodes are visited once, go back to 1
print(x[1:n]);
else
Hamiltonian (k+1,n);
endif
endif
endfor
end
Assign(k,i)
//returns true if x[k] can be assigned with i.
//Otherwise false. x is a global array whose rst k-1 values have been assigned already.
Begin
for j = 1 to k-1 do //Check if i has been assigned earlier; if so, it cannot be assigned to x[k]
if x[j] == i then
return False
endif
endfor
if adjacent(x[k-1],i)==true then
if k==n then
if adjacent(i,1)==true then
return true;
endif
else
return true;
endif
endif
return false;
end
We have used recursive algorithms for backtracking thus far. However, itera ve backtracking
algorithm is also an op on.
Algorithm BackTrack(n)//Itera ve general backtrack
begin
k=1;
while k≠0 do
ti
ti
fi
ti
if there remains an untried x[k] ϵT && B(x[1],x[2],….x[k]) is true then
if (x[1],x[2],….x[k]) is a path to an answer node, then
print (x[1],x[2],….x[k]);
k = k +1; //consider the next set
else
k=k-1;
endif
dowhile
end
B(x[1],x[2],….x[k]) is the bounding func on which returns either true or false. It is used to kill
nodes. Only if it returns true, we proceed. Otherwise, backtrack.
-----------
ti
