MODULE III

1. DYNAMIC PROGRAMMING

1.1 The Traveling Salesperson Problem (TSP)

1.1.1 Hamiltonian Cycles

1.2 Single Source Shortest Paths

1.2.1 Bellman-Ford Algorithm

1.3 All Pairs Shortest Paths

1.3.1 Floyd-Warshall algorithm

2. BACKTRACKING

2.1 8 Queen’s Problem

2.2 4 Queen’s Problem

2.3 n Queen’s Problem

3. BRANCH & BOUND

3.1 Least Cost (LC) Search

3.1.1 8 puzzle Problem

PraveenKumar P K, UIT Kollam

1. DYNAMIC PROGRAMMING
Dynamic Programming (DP) is an algorithm design method that can be used when the solution
to a problem may be viewed as the result of a sequence of decisions. It is used for
Optimization Problems was invented by Richard Bellman. The DP is closely related to Divide
and Conquer method, where the problem breaks down into smaller subproblems and each
subproblem is solved recursively. The DP differ from Divide and Conquer in a way that
instead of solving subproblem recursively (again and again), it solves each of the
subproblems only once and stores the solution to the subproblems in a table. Later on the
solution to the main problem is obtained by these subproblems solutions.
The steps for achieving Dynamic Programming are:
 Divide, Subproblems: The main problem is divided into several smaller subproblems. In
this the solution of the main problem is expressed in terms of the solution for the
smaller subproblems.
 Table, Storage: The solution for each subproblem is stored in a table. So that it can
be used many times whenever required.
 Combine, Bottom-up Computation: The solution to the main problem is obtained by
combining the solutions of smaller problems.
The word programming in dynamic programming does not refer to coding but refers to
building tables of intermediate results
For problem to be solved through DP it must follow the following conditions:
 Principle of Optimality: The Principle of Optimality states that for solving the
problem optimally, its subproblem should be solved optimally. It should be noted that
not all the times each subproblems is solved optimally, so in that case we should go
for the optimal majority
 Polynomial breakup: For solving the main problem, the problem is divided into several
smaller problems and for efficient performance of DP the total number of
subproblems to be solved should be at most a polynomial number.
1.1 The Traveling Salesperson Problem (TSP)
Given a set of cities and distance between every pair of cities, TSP problem is to find the
shortest possible route that visits every city exactly once and returns to the starting point.
Let G = ( V, E) be a directed graph with edge costs Cij. Cij is defined such that Cij > 0 for all
i and j and Cij = ∞ if <i, j> not in E. Let |V| = n and assume n > 1. A tour of G is a directed
cycle that includes every vertex in V and no vertex occurs more than once except for the
starting vertex. The cost of a tour is the sum of the cost of the edges on the tour. The
traveling salesperson problem is to find a tour of minimum cost.
The traveling salesperson problem finds application in a variety of situations. Suppose we
have to route a postal van to pick up mail from mail boxes located at n different sites. An

PraveenKumar P K, UIT Kollam

(n+1) vertex graph may be used to represent the situation. One vertex represents the post
office from which the postal van starts and to which it must return. Edge < i, j > is assigned
a cost equal to the distance from site i to site j. The route taken by the postal van is a tour
and we are interested in finding a tour of minimum length.
Naive Solution
1) Consider city 1 as the starting and ending point.
2) Generate all (n-1)! Permutations of cities.
3) Calculate cost of every permutation and keep track of minimum cost permutation.
4) Return the permutation with minimum cost.
Time Complexity: (n!)
Dynamic Programming
Here a tour to be a simple path that starts and ends at vertex 1. Every tour consists of an
edge <1, k> for some k∈ V − {1} and a path from vertex k to vertex 1. The path from vertex k
to vertex 1 goes through each vertex in V − {1, k} exactly once. It is easy to see that if the
tour is optimal then the path from k to 1 must be a shortest k to 1 path going through all
vertices in V - { 1, k }. Hence, the principle of optimality holds.
 g(i, S) be the length of a shortest path starting at vertex i, going through all vertices
in S and terminating at vertex 1.
 g ( 1, V - { 1 } ) is the length of an optimal salesperson tour.
From the principal of optimality it follows that:
g(1, V − {1}) = min(2 ≤ k ≤ n) { C1k + g ( k, V − { 1, k } ) } (1)
Generalizing (for i not in S)
g(i, S) = minj∈ S{ cij + g ( j, S − { j } ) } (2)
Equation 1 may be solved for g(1, V − {1}) if we know g(k, V − {1, k}) for all values of k. The g
values may be obtained by using Equation 2. Clearly
 g(i, Ø) = Ci,1, 1 ≤ i ≤ n
 We can use Equation 2 to obtain g(i, S) for all S of size 1
 Then we can obtain g(i, S) for S with |S| = 2 etc
 When |S| < n − 1, the values of i and S for which g(i, S) is needed are such that i ≠ 1, 1
not in S, and i not in S
Example Consider the directed graph of Figure (a). The edge lengths are given by the
matrix of Figure (b)
Solving for 2, 3, 4
g(2, Ø) = C21 = 5
g(3, Ø) = C31 = 6
g(4, Ø) = C41 = 8
Using Equation 2, we get
Directed graph and edge length matrix
PraveenKumar P K, UIT Kollam
 g(2, {3}) = C23 + g(3, Ø) = 9 + 6 = 15
g(3, {2}) = C32 + g(2, Ø) = 13 + 5 = 18
g(4, {2}) = C42 + g(2, Ø) = 8 + 5 = 13
g(2, {4}) = C24 + g(4, Ø) = 10 + 8 = 18
g(3, {4}) = C34 + g(4, Ø) = 12 + 8 = 20
g(4, {3}) = C43 + g(3, Ø) = 9 + 6 = 15
Next, we compute g(i, S) with |S| = 2 i ≠ 1, 1 not in S, and i not in S
g(2, {3, 4}) = min { C23 + g(3, {4}), C24 + g(4, {3}) }
= min { 9 + 20 , 10 + 15 } = 25
g(3, {2, 4}) = min { C32 + g(2, {4}), C34 + g(4, {2}) }
= min { 13 + 18, 12 + 13 } = 25
g(4, {2, 3}) = min {C42 + g(2, {3}), C43 + g(3, {2}) }
= min { 8 + 15, 9 + 18 } = 23
Finally, from Equation 1, we obtain
g(1, {2, 3, 4})= min { C12 + g(2, {3, 4}), C13 + g(3, {2, 4}), C14 + g(4, {2, 3}) }
= min { 10 + 25, 15 + 25, 20 + 23 } = { 35, 40, 43 }
= 35
An optimal tour of the graph of Figure (a) has length 35.
A tour of this length may be constructed if we retain with each g (i, S) the value of j that
minimizes the right hand side of Equation 2. Let this value be called J(i, S).
Then, J(1, {2, 3, 4}) = 2
Thus the tour starts from 1 and goes to 2
The remaining tour may be obtained from g (2, {3, 4}) Now, J(2, {3, 4}) = 4
Thus the next edge is <2, 4>
The remaining tour is for g(4, {3}) Now, J(4, {3}) = 3
The optimal tour is 1, 2, 4, 3, 1
Analysis of traveling salesperson
An algorithm that finds an optimal tour using Equations 1 and 2 will require O(n22n) time as
the computation of g(i, S) with |S| = k requires k − 1 comparisons when solving Equation 2.
This is better than enumerating all n! different tours (Naive Solution) to find the best one.
The most serious drawback of this dynamic programming solution is the space needed. The
space needed is O(n2n). This is too large even for modest values of n.
Q) Find the optimal tour of following matrix using TSP; Starting vertex is 0
0 1 2 3
0 0 1 15 6 Ans:
1 2 0 7 3 The optimal tour is: 0, 1, 3, 2, 0
2 9 6 0 12 Optimal tour has length: 21
3 10 4 8 0

PraveenKumar P K, UIT Kollam

1.1.1 Hamiltonian Cycles
Let G = ( V, E) be a connected graph with n vertices. A Hamiltonian cycle (suggested by Sir
William Hamilton) is a round trip path along n edges of G which visits every vertex once and
returns to its starting position. In other words if a Hamiltonian cycle begins at some vertex
V1 ∈ G and the vertices of G are visited in the order V 1, V2, ••• , Vn+1 then the edges (Vi, Vi+1)
are in E, 1 <= i <= n and the Vi are distinct except for V1 and Vn+1 which are equal.
\
The graph G1 of following Figure contains
the Hamiltonian cycle 1, 2, 8, 7, 6, 5, 4, 3, 1.
The graph G2 of Figure contains no
Hamiltonian cycle. There seems to be no
easy way to determine if a given graph
contains a Hamiltonian cycle. There seems
to be no easy way to determine if a given
graph contains a Hamiltonian cycle. We shall
now look at a backtracking algorithm which
finds all the Hamiltonian cycles in a graph.
Two graphs, one containing a Hamiltonian
The graph may either be directed or
cycle
undirected.

1.2 Single Source Shortest Paths

Graphs may be used to represent the highway structure of a state or country with vertices
representing cities and edges representing sections of highway. The edges may then be
assigned weights which might be either the distance between the two cities connected by
the edge or the average time to drive along that section of highway. A motorist wishing to
drive from city A to city B would be interested in answers to the following questions:
(i) Is there a path from A to B?
(ii) If there is more than one path from A to B, which is the shortest path?
The problems defined by (i) and (ii) above are special cases of the path problem. The length
of a path is now defined to be the sum of the weights of the edges on that path. The
starting vertex of the path will be referred to as the source and the last vertex the
destination. The graphs will be digraphs to allow for one way streets. In the problem we
shall consider, we are given a directed graph G = ( V, E ), a weighting function c(e) for the
edges of G and a source vertex V0. The problem is to determine the shortest paths from V 0
to all the remaining vertices of G.
Two algorithms used to solve single source shortest paths problem they are
 Dijkstra’s algorithm
 Bellman-Ford algorithm

PraveenKumar P K, UIT Kollam

Dijksra’s algorithm is a Greedy algorithm and time complexity is O(VLogV). Dijkstra doesn’t
work for Graphs with negative weight edges, Bellman-Ford works for such graphs. Bellman-
Ford is also simpler than Dijkstra’s and suites well for distributed systems. But time
complexity of Bellman-Ford is O(VE), which is more than Dijkstra.
1.2.1 Bellman-Ford Algorithm
Let distk[u] be the length of a shortest path from the source vertex ‘v’ to vertex ‘u’ under
the constraint that the shortest path contains at most ‘k’ edges. Then dist 1[u] = cost [v, u],
1<=u<=n. To compute distn-1[u] for all u. This can be done using the dynamic programming
methodology. First we make the following observation
1. If the shortest path from v to u with at most k, k > 1, edges has no more than k-1
edges, then distk[u] = distk-1[u].
2. If the shortest path from v to u with at most k, k > 1, edges has exactly k edges, then
it is made up of a shortest path from v to some vertex j followed by the edge <j, u>.
the path from v to j has k – 1 edges, and its length is dist k-1[j]. All vertices i such that
the edge <i, u> is in the graph are candidate for j. Since we are interested in a
shortest path, the i that minimizes distk-1[i] + cost[i, u] is the correct value for j.
These observation result in the following recurrence for dist
dist k[u] = min { dist k-1[u], mini { dist k-1[i] + cost[i, u] } }
This recurrence can be used to compute distk from dist k-1, for k = 2, 3, …, n-1
Example: Following figure gives a seven vertex graph
-1
2 5
3
6
-2
5 1
1 3 7

-2
5 6
4 6
-1

For instance, dist [1] = 0 for all k since 1 is the source node.
k

Also dist1[2] = 6, dist1[3] = 5, and dist1[4] = 5, since there are edges from 1 to these nodes.
The distance dist1[] is ∞ for the nodes 5, 6 and 7 since there are no edges to these from 1
dist2[2] = min { dist1[2], mini { dist1[i] + cost[i, 2] } } [i = 1, 3, 4, 5, 6, 7]
= min { 6, { dist1[1] + cost[1, 2], dist1[3] + cost[3, 2] ,dist1[4] + cost[4, 2],
dist1[5] + cost[5, 2] , dist1[6] + cost[6, 2] , dist1[7] + cost[7, 2] }}
= min {6, 0 + 6, 5 – 2, 5 + ∞, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 3
Here the term 0 + 6, 5 – 2, 5 + ∞, ∞ + ∞, ∞ + ∞ and ∞ + ∞ correspond to a choice of i = 1, 3,
4, 5, 6 and 7 respectively.
dist2[3] = min { dist1[3], mini { dist1[i] + cost[i, 3] } } [i = 1, 2, 4, 5, 6, 7]

PraveenKumar P K, UIT Kollam

 = min { 5, { dist1[1] + cost[1, 3], dist1[2] + cost[2, 3] ,dist1[4] + cost[4, 3],
dist1[5] + cost[5, 3] , dist1[6] + cost[6, 3] , dist1[7] + cost[7, 3] }}
= min {5, 0 + 5, 6 + ∞, 5 -2, ∞ + ∞, ∞ + ∞, ∞ + ∞} = 3
///ly dist2[4] = 5, dist2[5] = 5, dist2[6] = 4
dist2[7] = min { dist1[7], mini { dist1[i] + cost[i, 7] } }
= min { ∞, { dist1[1] + cost[1, 7], dist1[2] + cost[2, 7], dist1[3] + cost[3, 7],
dist1[4] + cost[4, 7], dist1[5] + cost[5, 7] , dist1[6] + cost[6, 7] }}
= min { ∞, 0 + ∞, 6 + ∞, 5 + ∞, ∞ + 3, ∞ + 6} = ∞
Dist3[2] = min { dist2[2], mini { dist2[i] + cost[i, 2] } }
= min { 3, { dist2[1] + cost[1, 2], dist2[3] + cost[3, 2] ,dist2[4] + cost[4, 2],
dist2[5] + cost[5, 2] , dist2[6] + cost[6, 2] , dist2[7] + cost[7, 2] }}
= min { 3, 0 + 6, 3 – 2, 5 + ∞, 5 + ∞, 4 + ∞, ∞ + ∞} = 1
…………… ……………… …………… ………………
The rest of the entries are computed and the arrays dist k, k = 1, 2, …. 6 is
distk[1..7]
k 1 2 3 4 5 6 7
1 0 6 5 5 ∞ ∞ ∞
2 0 3 3 5 5 4 ∞
3 0 1 3 5 2 4 7
4 0 1 3 5 0 4 5
5 0 1 3 5 0 4 3
6 0 1 3 5 0 4 3
Algorithm
BellmanFord(v, cost, dist, n)
{
for i = 1 to n do // initialize dist
dist[i] = cost[v, i]
for k = 2 to n-1 do
for each u such that u != v and u has at least one incoming edge do
for each <i, u> in the graph do
if dist[u] > dist[i] + cost[i, u] then
dist[u] = dist[i] + cost[i, u]
} 1
2 4
Q) Find shortest paths from node 1 to every other 2 8
5
node in the graph of following figure using Bellman 1 -3
4 6
Ford algorithm -4
4 6
3 5
-2
PraveenKumar P K, UIT Kollam
1.3 All Pairs Shortest Paths

All Pair Shortest Path problem computes the shortest path between each pair of vertices in

a weighted directed graph. The problem is efficiently solved by Floyd-Warshall algorithm.

Let G = (V, E) be a directed graph with n vertices. Let C be a cost adjacency matrix for G

such that C(i, i) = 0, 1 <= i <= n, C(i, j) is the length (or cost) of edge (i,j) if (i,j) ∈ E(G) and

C(i,j) = ∞ if (i != j) and (i,j) not in E(G). The cost(weight) of i th row and jth column is denoted

by Cij

0 if i = j

Cij = C(i, j) if i != j and (i, j) ∈ E

∞ if i != j and (i, j) !∈ E

The all pairs shortest path problem is to determine a matrix A such that A (i, j) is the

length of a shortest path from i to j.

1.3.1 Floyd-Warshall algorithm

The Floyd-Warshall algorithm is based up on Dynamic Programming technique. This algorithm

computes the distance matrix of a weighted graph with n vertices through a series of n by n

matrices

D(0),…, D(k-1), D(k),…., D(n)

Each of these matrices contains the lengths of shortest paths. Specifically, the element d ijk

in the ith row and jth column of matrix D(k) (k = 0,1,…,n) is equal to the length of the shortest

path among all paths from the ith vertex to jth vertex with each intermediate vertex, if any

numbered not higher than k. The series starts with D (0), which does not allow any

intermediate vertices in its paths, hence D(0) is nothing but the weight matrix of the graph.

The last matrix in the series D(n), contains the length of the shortest paths among all paths

that can use all n vertices as intermediate.

Let dij(k) be the element in the ith row and jth column of matrix D(k). this means that dij(k) is

equal to the length of the shortest path among all paths from the ith vertex vi to the jth

vertex vj with their intermediate vertices numbered not higher than k.

vi, a list of intermediate vertices each numbered not higher than k, v j

We can partition all such path into two subset, All such paths have the following form
PraveenKumar P K, UIT Kollam
 vi, vertices numbered <= k-1, vk, vertices numbered <= k-1, vj

In other words, each of the paths is made up of a path dij(k-1)

from vi to vk with each intermediate vertex numbered vi vj
not higher than k – 1 and a path from vk to vj with each
intermediate vertex numbered not higher than k – 1.
This situation is depicted symbolically in following figure dik(k-1) dkj(k-1)

Since the length of the shortest path from vi to vk vk

among the paths that use intermediate vertices

numbered not higher than k – 1 is equal to d ik(k-1) and the length of the shortest path from v k

to vj among the paths that use intermediate vertices numbered not higher than k – 1 is equal

to dkj(k-1), the lengt of the shortest path among the paths that use the k th vertex is equal to

dik(k-1) + dkj(k-1). Taking into account the length of the shortest paths in both subsets leads to

the following recurrence.

dij(k) = min { dij(k-1), dik(k-1) + dkj(k-1)} for k >= 1

dij(0) = Cij for k = 0

To put in another way, the element in the ith row and jth column of the current distance
matrix D(k-1) is replaced by the sum of the elements in the same row i and the k th column and
in the same column j and the kth column if and only if the latter sum is smaller than its
current value.
Example Find all pair shortest path using Floyd Warshell algorithm, see graph shown below
Solution: 6

Initially D(0) = 1 2 3 1 4 2

1 0 4 11 11
2
3
2 6 0 2
3
3 3 ∞ 0

Applying this recurrence dij(k) = min { dij(k-1), dik(k-1) + dkj(k-1)} for k >= 1

d12(1) = min { d12(0), d11(0) + d12(0) }

= min { 4, 0 + 4 } = 4 D(1) = 1 2 3

………….. ……………. ……………… 1 0 4 11

d32 (1)
= min { d32(0), d31(0) + d12 (0)
} 2 6 0 2

= min { ∞, 3 + 4 } = 7 3 3 7 0

………….. ……………. ………………

PraveenKumar P K, UIT Kollam

d13(2) = min { d13(1), d12(1) + d23(1) } D(2) = 1 2 3

= min { 11, 4 + 2 } = 6 1 0 4 6

………….. ……………. ……………… 2 6 0 2

d21(3) = min { d21(2), d23(2) + d31(2) } 3 3 7 0

= min { 6, 2 + 3 } = 5

………….. ……………. ……………… D(3) = 1 2 3

d31(3) = min { d31(2), d33(2) + d31(2) } 1 0 4 6

= min { 3, 0 + 3 } = 3 2 5 0 2

3 3 7 0

Updated elements are shown in shaded. D(3) give the All pair shortest path.

If there exists ‘n’ vertices in graph G, then All pair shortest path complexity will be O(n 3)

The algorithm for the Floyd-Warshall all pair shortest path is given below

Function FloydWarshall(W) //W- weight matrix

Step 1: Initialization

D[i, j] = W[i, j]

Step 2: Intermediate vertices, loop

for k = 1 to n do

for i = 1 to n do

for j = 1 to n do

if ( D[i, k] + D[k, j] < d[i, j] then

D[i, j] = D[i, k] + D[k, j]

Return D

Q) Find all pair shortest path using Floyd Warshell algorithm

2
Ans: D(4) = a b c d a b

a 0 10 3 4 3
7 6
b 2 0 5 6
c d
c 7 7 0 1
1

d 6 19 9 0

PraveenKumar P K, UIT Kollam

Q) What is Transitive Closure of a digraph?

The is Transitive Closure of a digraph with n vertices can be defined as the n by n

Boolean matrix T = {tij}, in which the element in the ith row and the jth column is 1 if there

exists a nontrivial directed path from the ith vertex to the jth vertex otherwise tij is 0

An example of a digraph, its adjacency matrix, and its Transitive Closure is given below

a b c d a b c d
a b
a 0 1 0 0 a 1 1 1 1

b 0 0 0 1 b 1 1 1 1

A= c 0 0 0 0 T= c 0 0 0 0
c d
d 1 0 1 0 d 1 1 1 1
Digraph Adjacency Matrix Transitive Closure

Q) Define shortest path problem

Q) What is meant by spanning tree?

Q) State Dynamic Programming Method

Q) How will you find out cost of spanning tree using Prim’s method?

Q) Write and explain Prim’s algorithm

Q) Discuss Single source shortest path problem and all pair shortest path problem.

Q) Compare and contrast Greedy method of algorithm design and Dynamic Programming

Q) Define the principle of optimality

Q) Write and explain Krusksl’s algorithm

Q) Solve Knapsack problem by Greedy method

Q) Explain travelling salesperson problem with the help of example

Q) Explain Bellman Ford algorithm for for the single source shortest path problem

Q) Explain search algorithm with the help of an example

Q) What is Hamiltonian cycle? Give example

Q) Define spanning tree. Give an example for a minimum spanning tree

Q) Explain in detail the backtracking algorithm for 8 queen’s problem

Q) Differentiate Deterministic and Nondeterministic algorithm.

PraveenKumar P K, UIT Kollam
2. BACKTRACKING
In the search for fundamental principles of algorithm design, backtracking represents one
of the most general techniques. Many problems which deal with searching for a set of
solutions or which ask for an optimal solution satisfying some constraints can be solved using
the backtracking formulation. The name backtrack was first coined by D. H. Lehmer in the
1950's.
In order to apply the backtrack method
 Express the desired solution as an n-tuple (x1, …, xn) where each xi are chosen from
some finite set Si
 The solution is based on finding one or more vectors that maximize, minimize, or
satisfy a criterion function P(x1, …, xn)
Eg: Sorting an array a[n] (sorting is not usually one of the problems solved by backtracking)
 Find an n-tuple where the element xi is the index of ith smallest element in ‘a’
 Criterion function is given by a[xi] <= a[xi+1] for 1 <= i < n
 Set Si is a finite set of integers in the range [1,n]
Many of the problems we shall solve using backtracking require that all the solutions satisfy
a complex set of constraints. For any problem these constraints may be divided into two
categories: explicit and implicit.
Explicit constraints are rules that restrict each xi to take on values only from a given set.
 Explicit constraints depend on the particular instance I of problem being solved
 All tuples that satisfy the explicit constraints define a possible solution space for I
 Examples of explicit constraints
xi >= 0, or Si = { all nonnegative real numbers }
xi = 0 or 1 or Si = { 0, 1}
li <= xi <= ui
Implicit constraints are rules that determine which of the tuples in the solution space of I
satisfy the criterion function. Thus implicit constraints describe the way in which the x is
must relate to each other.
2.1 Example (8-queens problem)
A classic combinatorial problem is to place eight queens on an 8 X 8 chessboard so that no
two "attack", that is so that no two of them are on the same row, column or diagonal. Let us
number the rows and columns of the chessboard 1 through 8. The queens may also be
numbered 1 through 8. All solutions to the 8 queens problem can therefore be represented
as 8-tuples (x1, …. , x8) where xi is the column on which queen i is placed.
Explicit constraints
 Explicit constraints using 8-tuple formulation are S i = {1, 2, 3, 4, 5, 6, 7, 8}, 1 <= i <= 8
 Solution space of 88 8-tuples

PraveenKumar P K, UIT Kollam

Implicit constraints
 No two xi can be the same, or all the queens must be in different columns
 All solutions are permutations of the 8-tuple (1; 2; 3; 4; 5; 6; 7; 8)
 Reduces the size of solution space from 8 8 to 8! Tuples
 No two queens can be on the same diagonal
1 2 3 4 5 6 7 8
1 Q
2 Q
3 Q
4 Q
5 Q
6 Q
7 Q
8 Q
 The solution above is expressed as an 8-tuple as { 4, 6, 8, 2, 7, 1, 3, 5 }
2.2 Example (4-queens problem)
It can be seen that for n=1, the problem has a trivial solution, and no so solution exist for

n=2 and n=3. So we will consider the 4 queens problem.

Given a 4 X 4chess board, now let us number the row and column of the chess board 1

through 4 as follow

Since we have to place 4 queens on a chessboard, such that

no two queens attack each other, we number these as q1,
q2, q3, q4. It can be observed that for such a condition
each queen must be placed on a different row
Now, we have to assign a column for each queen on the 4 X
4 chessboard. Initially, we have an empty chess board, now
first we place queen q1 in the very first acceptable position
which is row 1 and column 1. Next we place queen q2 and
4 X 4 chessboard
search search for its best position so that both these
queens do not attack each other. Thus we find that if we place q2 in column 1 and 2 then the

dead end is encountered. Thus the first acceptable position for q2 is (2, 3). But later this

position prove to be dead end; as no position is left for placing q3 safely. So we backtrack

one step and place the queen q2 in (2, 4), the next best position location. Thus we obtain the

position for placing q3 which is (3, 2). But later this position also leads to dead end as no

PraveenKumar P K, UIT Kollam

place is found where q4 can be placed safely. Then we have to backtrack till q1 and palce it

to (1, 2), the next possible position for it. After this all other queens are placed safely by

moving q2 to (2, 4), q3 t0 (3, 1) and q4 to (4, 3) in such a manner that no two queens can

attack each other by being placed in the same row, column, diagonal. The whole process is

shown below. Finally we get the solution (2, 4, 1, 3) that means, the one possible solution for

4 queens problem is to place q1 in column 2, q2 in column 4, q3 in column 1 and q4 in column 3.

Other solution for 4 queens problem

solution (3, 1, 4, 2)

Implicit tree for 4 queen problem solution (2, 4, 1, 3)

All the solutions to the 4 queen problem can be represented as 4 tuples (x 1, x2, x3, x4),

Where xi represents columns on which queen qi is placed.

Explicit Constrains: Si = (1, 2, 3, 4), where 1 <= i <= 4.

Implicit Constrains: No queen can be placed in same column, thus no two x i’s can be same and

no two queens can be placed on the same diagonal.

The permutation tree so obtained by considering the constrains which signifies 4! leaf nodes

PraveenKumar P K, UIT Kollam

2.3 Example (n-queens problem)

The n-queens problem is a generalization of the 8-queens problem of Example 2.1. n queens

are to be placed on an n x n chessboard so that no two attack, i.e., no two queens are on the

same row, column or diagonal. Generalizing earlier example discussion, the solution space

consists of all n! permutations of the n-tuple (1, 2, ... , n). Following figure shows a possible

tree organization for the case n = 4. A tree such as this is called a permutation tree.

The edges are labeled by possible values of xi. Edges from level 1 to level 2 nodes specify

the values for x1. Thus, the leftmost subtree contains all solutions with x1 = 1; its leftmost

subtree contains all solutions with x1 = 1 and x2 = 2, etc. Edges from level i to level i + 1 are

labeled with the values of xi. The solution space is defined by all paths from the root node

to a leaf node. There are 4! = 24 leaf nodes in the tree.

Backtracking is an implementation of Artificial Intelligence. Backtracking is a fascinating

way of software engineering which can be used for optimizations, solving puzzles (jigsaw and

other) and creating computer opponents in mind games like chess

PraveenKumar P K, UIT Kollam

3. BRANCH & BOUND
Branch & Bound (B & B) is general algorithm (or Systematic method) for finding optimal
solution of various optimization problems, especially in discrete and combinatorial
optimization. The B&B strategy is very similar to backtracking in that a state space tree is
used to solve a problem. The differences are that the B&B method
 Does not limit us to any particular way of traversing the tree.
 It is used only for optimization problem
 It is applicable to a wide variety of discrete combinatorial problem.
B&B is rather general optimization technique that applies where the greedy method &
dynamic programming fail. It is much slower, indeed (truly), it often (rapidly) leads to
exponential time complexities in the worst case.
There are basically three types of nodes involved in Branch and Bound
1. Live node is a node that has been generated but whose children have not yet been
generated.
2. E-node is a live node whose children are currently being explored. In other words, an
E-node is a node currently being expanded.
3. Dead node is a generated node that is not to be expanded or explored any further. All
children of a dead node have already been expanded.
We will use 3-types of search strategies in branch and bound
1. FIFO (First In First Out) search
2. LIFO (Last In First Out) search
3. LC (Least Count) search
Both BFS & D-search (DFS) generalized to B&B strategies.
 BFS: Like state space search will be called FIFO (First In First Out) search as the
list of live nodes is “First-in-first-out” list (or queue).
 D-search (DFS): Like state space search will be called LIFO (Last In First Out)
search as the list of live nodes is a “last-in-first-out” list (or stack).
3.1 Least Cost (LC) Search
The selection rule for the next E-node in FIFO or LIFO branch and bound is sometimes
“blind”. i.e., the selection rule does not give any preference to a node that has a very good
chance of getting the search to an answer node quickly.
The search for an answer node can often be speeded by using an “intelligent” ranking
function. It is also called an approximate cost function
Cost function
Each node X in the search tree is associated with a cost. The cost function is useful for
determining the next E-node. The next E-node is the one with least cost. The cost function
is defined as

PraveenKumar P K, UIT Kollam

 C(X) = g(X) + h(X) where
g(X) = cost of reaching the current node from the root
h(X) = cost of reaching an answer node from X.
3.1.1 Example: 8 puzzle Problem
Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty space.
The objective is to place the numbers on tiles to match final configuration using the empty
space. We can slide four adjacent (left, right, above and below) tiles into the empty space.
Cost function for 8-puzzle Algorithm
We assume that moving one tile in any direction will have 1 unit cost. Keeping that in mind,
we define cost function for 8-puzzle algorithm as below
c(x) = f(x) + h(x) where
f(x) is the length of the path from root to x (the number of moves so far) and
h(x) is the number of non-blank tiles not in their goal position (the number of mis-
-placed tiles). There are at least h(x) moves to transform state x to a goal state
For example

PraveenKumar P K, UIT Kollam

PraveenKumar P K, UIT Kollam