UNIT-IV

Introduction

 Backtracking and Branch-and –bound that are often make it possible to

solve at least some large instances of difficult combination of problem.
 Both back tracking and branch-and-bound are based on the construction of a
state space tree whose node reflect specific choice made for a solution’s
component’s.
 Both techniques terminate a node as soon as it can be guaranteed that no
solution to the problem can be obtained by considering choices that
correspond to the node’s descendants.
 For backtracking, this tree usually developed depth first(DFS).
 Branch-and-bound can generate node according to several rules, the most
naturals rules is the so-called best-first rule.
 Approximation algorithm for the traveling salesman and knapsack problems.

Backtracking

 The exhaustive search technique suggests gene ratings all candidate solutions
and then identifying the one with a desires property.
 Backtracking is a more intelligent variation of this approach.
 Algorithm backtrackings the last component of the partially constructed
solution with its next option.
 It is convenient to implement this kind of processing by constructed a tree of
choice being made, called the state-space tree.
 A node in a state-space tree said to be promising if it corresponds to a
partially constructed solution may still leads to a complete solution.
 A node in a state-space tree said to be non promising if it not corresponds to
a partially constructed solution.

N-QUEEN PROBLEM:
 n-queen problem is to place a n queen on a n by n chessboard.
 Queen should not attack each other.
 Queen should not be in same row or same column or same diagonal.

Empty chessboard:
Fig: State space tree of solving the four-queen problem by back-tracking. X denotes
an unsuccessful attempt to place a queen in the indicated column. The numbers
above the nodes indicate the order in which the nodes are generated.

Algorithm:
N - Queens (k, n)
{
For i ← 1 to n
do if Place (k, i) then
{
x [k] ← i;
if (k ==n) then
write (x [1....n));
 else
N - Queens (k + 1, n);
}
}
Place (k, i)
{
For j ← 1 to k - 1
do if (x [j] = i)
or (Abs x [j]) - i) = (Abs (j - k))
then return false;
return true;
}

Analysis:

Time Complexity: O(N!)

Auxiliary Space: O(N2)

Hamiltonian circuit problem

 Vertex a root of the state–space tree.

 The first component of our future solution, if it exits, is a first intermediate
vertex of a Hamiltonian cycle to be constructed.
 Using the alphabet order to break the three-way tie among the vertices
adjacent to a, we select vertex b.
 From b, the algorithm proceeds to c, then to e, and finally to f, which proves
to be a dead end.
 From there, it goes to the vertices f,e,c,&d, from which it can legitimately
return to a, yield the Hamiltonian circuit a,b,f,e,c,d,a.
 If we wanted to find another Hamiltonian circuit, we could continue this
process by backtracking from the leaf of the solution found.
 Fig: (a) Graph. (b)State-space tree for finding a Hamilton circuit. The
numbers above the nodes of the tree indicate the order in which the nodes are
generated.
Subset Sum Problem

The subset sum problem find the subset of a given set S={s1,s2,…..sn} of n
positive integers whose sum is equal to a given positive integer d.

Example

S={1,2,5,6,8} and d=9, there are two solutions. {1,2,6} and {1,8} of course,
some instances of this problem may have no solutions.

The state-space tree can be constructed as a binary tree as that in Fig .1 for the
instance S={3,5,6,7}and d=15.
 0

Wt 3 w/o 3

0
3
wt 5 w/o 5
With 5 w/o 5
5 0
8 3
Wih 6 wt 6
w/o7 w/o 6 w/o 6 0+13<15
wt 6 1 5
14 8 9 3 1 5+7<15
3+7<15 11+7>15
X x
14+ 7>15 9+7>15
1 8
5
Solution X
8<15

Fig: Complete state-space tree of the backtracking algorithm applied to the instance
S={3,5,6,7} and d=15 of the subset-sum problem. The number inside a node is the
sum of the elements already included in subsets represented by the node. The
inequality below a leaf indicates the reason for its termination.

We record the value of s’ the sum of these numbers in the node. If s’ is equal to d,
we have a solution to the problem. We can either report this result and stop or, if all
the solutions need to be found, continue by backtracking to the node’s parent. If s’
is not equal to d, we can terminate the node as non promising if either of the two
inequalities hold:
S’+Si+1 >d(the Sum S’ is too large)
n
S’+ ∑ Sj < d (the Sum S’ is too samll)
j=i+1

Algorithm

algorithm backtrack(x[1…i])
//gives a template of generic backtracking algorithm
//i/p: x[1..i] specifies first i promising component of a solution
//o/p: all the tuples representing the problem’s solution
If x[1…i] is a solution write x[1..i]
Else
For each element x € Si+1 consistent with x1..i[ and the constraint do
X[i+1]x
Backtrack(x[1..i+1])

Graph Coloring
 We have been given a graph and we are asked to color all vertices with the
‘M’ number of given colors, in such a way that no two adjacent vertices
should have the same color.

It it is possible to color all the vertices with the given colors then we have to
output the colored result, otherwise output ‘no solution possible’.

The least possible value of ‘m’ required to color the graph successfully is known
as the chromatic number of the given graph.

Graph Coloring Solution

Using Naive Algorithm

In this approach using the brute force method, we find all permutations of color
combinations that can color the graph.

If any of the permutations is valid for the given graph and colors, we output the
result otherwise not.

This method is not efficient in terms of time complexity because it finds all colors
combinations rather than a single solution.
Using Backtracking Algorithm

The backtracking algorithm makes the process efficient by avoiding many bad
decisions made in naïve approaches.

In this approach, we color a single vertex and then move to its adjacent (connected)
vertex to color it with different color.

After coloring, we again move to another adjacent vertex that is uncolored and
repeat the process until all vertices of the given graph are colored.

In case, we find a vertex that has all adjacent vertices colored and no color is left to
make it color different, we backtrack and change the color of the last colored
vertices and again proceed further.

If by backtracking, we come back to the same vertex from where we started and all
colors were tried on it, then it means the given number of colors (i.e. ‘m’) is
insufficient to color the given graph and we require more colors (i.e. a bigger
chromatic number).

Steps To color graph using the Backtracking Algorithm:

Different colors:

Confirm whether it is valid to color the current vertex with the current color (by
checking whether any of its adjacent vertices are colored with the same color).

If yes then color it and otherwise try a different color.

Check if all vertices are colored or not.

If not then move to the next adjacent uncolored vertex.

If no other color is available then backtrack (i.e. un-color last colored vertex).

Here backtracking means to stop further recursive calls on adjacent vertices by

returning false. In this algorithm Step-1.2 (Continue) and Step-2 (backtracking) is
causing the program to try different color option.

Continue – try a different color for current vertex.

Backtrack – try a different color for last colored vertex.

plications

 Design a timetable.
 Sudoku
 Register allocation in the compiler
 Map coloring
 Mobile radio frequency assignment:
 Branch-and-bound
 This idea can be strengthened further if we deal with an optimization
problem, one that seeks to minimize or maximize an objective function,
usually subject to some constraints
note that in the standard terminology of problem, a feasible solution is a
point in the problem search space that satisfies all the problem’s constraints
 while an optimal solution is a feasible solution with the best value of the
objective functions
 Hamiltonian circuit, the most valuable subset of the items that fit the
knapsack

Compared to backtracking , Branch-and-bound requires two additional items:

1. a way to provide, for every node of a state-space tree, a bound on the

best value of the objective function1 on any solution that can be
obtained by node further components to the partial solution represented
by the node
2. the value of the best solution seen so far
In general, we terminate a search path at the current node in a state-space tree of a
branch –and –bound algorithm any one of the following reasons:
1. the value of the node’s bound is not the better than the value of the best
solution seen so far.
2. the node represents no feasible solutions because the constraints of the
problem are already violated.
3. the subset of feasible solutions represented by the node consists of a single
point –in case we compare the value of the objective function for this
feasible solution with that of best solution seen so far and update the later
with the former if the new solution is better.

Assignment problem
 Branch-and-bound approach by applying it to the problem of assignment n
people to n jobs so that the total cost of the assignment is as small as
possible,
 Recall that an instance of the assignment problem is specified by the n by n
cost matrix c so that we can state the problem as follows.
  Select each element in each row of the matrix so that no two selected
elements are in the same column and their sum is smaller possible.

Step 1:

start

Lb=2+3+1+4=10

a1 a2 a3 a4

lb=9+3+1+4=17 lb=2+3+1+4=10 lb=7+4+5+4=20

lb=8+3+1+6=16

Fig: level 0 and 1 of the state-space tree for the instance of the assignment problem
being solved with the best-first branch-and-bound algorithm. The number above a
node shows the order in which the node was generated .A node’s field indicate the
job number assigned to person a and the lower bound value, lb for this node.

 Returning to the instance of the assignment problem given earlier, we start

with the root that corresponds to no elements selected from the cost matrix.
 As we already discussed, the lower bound value for the root, denoted for lb,
is 10.
  The nodes on the first level of the tree correspond to four elements(jobs) in
the first row of the matrix since they are each a potential selection for the first
component of the solution

Step 2:

Start
lb=10

a1 a2 a3 a4

lb=17 lb=10 lb=20 lb=18
Fig: Levels 0, 1, and 2 of the state-space tree for the instance of the assignment problem
being solved with the best-first branch-and-bound algorithm.
Step 3:
b1 b3 b4
lb=13 lb=14 lb=17

Start
lb=10

a1 a2 a3 a4

lb=17 lb=10 lb=20 lb=18

b1 b3 b4

lb=13 lb=14 lb=17

c3 c4
d4 d3
Cost=13 Cost255
3 53
Fig: Complete state-space tree for the instance of the assignment problem solved
with the best-first branch-and-bound algorithm.

Knapsack problems

 This problem consist n items of known problems wi and values

vi=1,2,3…..,n, and a knapsack of capacity w, find the most valuable
subset of the items that fit it the knapsack.

 It is convenient to order the items of a given instance in descending order

their values-to-weight Ratios.

V1/w1>=v2/w2>=…vn/wn

 A simple way to compute the upper bound ub is to add to v, the total

value of the items already selected, the product of the remaining
capacity of the knapsack W-w and the best per unit pay off among the
remaining items, which is v i+1/wi+1

 Ub=v+(W-w)(vi+1/wi+1)

Item Weight Value Value/Weight

1 4 $40 10
2 7 $42 6
3 5 $25 5
4 3 $12 4

The knapsack’s capacity W is 10

Solution:

Ub=v+(W-w)(vi+1/wi+1)

Now W=10
Step 1:

W=0,v=0,i=0

Ub=(10-0)(10)
Ub=100

W=0,V=0
Ub=100

Step 2(a)
(with 1)
W=4,v =40, i=1

Ub=40+(10-4)(6)
=76
Ub=76

(b)(without 1) i=1

W=0,v =0, i=1

Ub=0+(10-0)(6)
=60
Ub=60

W=0,V=0
Ub=100
With 1 w/o 1

W=0,V=0
Ub=60

We select highest upperbound value(76)

So continue with 1
Step 3
(a)(with 2)

W=11(not feasible)

(b)(without 2)

W=4,v =40, i=2

Ub=40+(10-4)(5)
=70
Ub=70

W=0,V=0
Ub=100
With 1 w/o 1

W=4,V=40
Ub=76
With 2 w/0 2

W=11 W=4,V=40
Not feasible Ub=70

Step 4
(a)(With 3)

W=9,v =65, i=3

Ub=65+(10-9)(4)
=69
Ub=69

(b)
(Without 3)

\W=4,v =40, i=3

Ub=40+(10-4)(4)
=64
Ub=64

W=0,V=0
Ub=100
With 1 w/o 1

W=4,V=40
Ub=76
With 2 w/0 2
W=4,V=40
W=11
Ub=70
Not feasible
With 3 w/0 3

W=4,V=40
Ub=64

We select highest upperbound value.

So continue with 3

Step 5:
(a)(with 4)

W=12[Not feasible]

(b)(without 4)

W=9,v =65, i=4

Ub=65+(10-9)(0)
=65
Ub=65

W=0,V=0
Ub=100
 With 1 w/o 1

W=4,V=40
Ub=76
With 2 w/0 2
W=4,V=40
W=11
Ub=70
Not feasible

Wt 3 w/o 3
W=4,V=40
Ub=64

W=9,V=65
Ub=65
SOLUTION

Traveling Salesman Problem

 Traveling Sales person problem gives the reasonable lower bound on tour
lengths.
 The lower bound on tour l of any tour can be computed as follows. For
each city I, 1<=I<=n, find the sum Si of the distances from city I to the
nearest cities. Compute the sum s of these n numbers, divide the result by
2, and if all the distances are integer, round up the result to the nearest
integer.

Lb = S/2

Example:

3
a b
5 6

7
8 9
4
c d

e
 2
3

Solution:

Step1:

Node(a)

Lb=[(1+3)+(3+6)+(1+2)+(3+4)+(2+3)/2]
=(4+9+3+7+5)/2
=28/2
=14
Lb=14

a
Lb=14

Step 2:

(a,b),(a,c),(a,d),(a,e)

lb=[(1+3)+(3+6)+(1+2)+(4+3)+(2+3)/2]
=(4+9+3+7+5)/2
=28/2
=14
Lb=14

(a,c):- b is not before c

(a,d):-
Lb=[(1+5)+(3+6)+(1+2)+(5+3)+(2+3)/2]
=(6+9+3+8+5)/2
=31/2
=16
Lb=16
(a,e):-
Lb=[(8+1)+(3+6)+(1+2)+(4+3)+(2+8)/2]
=(9+9+3+7+10)/2
=38/2
=19
Lb=14

a
Lb=14

a,b a,c a,e

Lb=14 Lb=14 Lb=19
b is not before c

 Select minimum lb value

 According to this example the minimum lb value is lb=14, so choose
that particular path & continue with next level

Step3:
(a,b,c),(a,b,d),(a,b,e)

(a,b,c):-

Lb=[(1+3)+(3+6)+(1+6)+(4+3)+(2+3)/2]
=(4+9+7+7+5)/2
=32/2
=16
Lb=16

(a,b,d):-

Lb=[(1+3)+(3+7)+(1+2)+(3+7)+(2+3)/2]
=(4+10+3+10+5)/2
=32/2
=16
Lb=16

(a,b,e):-

Lb=[(1+3)+(3+9)+(1+2)+(4+3)+(2+9)/2]
=(4+12+3+7+11)/2
=37/2
=19
Lb=19

a
Lb=14

a,d a,e
a,b
Lb=16 Lb=19
Lb=14
b is not before c

a,b,e
Lb=19

Step 4:

(a,b,c,d,(e,a)),(a,b,c,e,(d,a)),(a,b,d,c,(e,a)),(a,b,d,e(c,a))

(i) (a,b,c,d,(e,a))

Lb=3+6+4+3+8=24[first tour]

(ii) (a,b,c,e,(d,a))

Lb=3+6+2+3+5=19[better tour]

(iii) (a,b,d,c,(e,a))

Lb=3+7+4+2+8=24[ inferior tour]

 (iv) (a,b,d,e(c,a))

Lb=3+7+3+2+1=16[optimal tour]

a
Lb=14
4

1 2 3
a,d a,e
a,b
Lb=16 Lb=19
Lb=14
b is not before c

5 6 7
a,b,e
a,b,d
Lb=19
Lb=16

8 9 10 11

a,b,d,e,c,a
Lb=16

t tour better tour inferior tour optimal tour

Fig:- State space tree of the branch-and-bound algorithm applied to this graph. The
list of vertices in a node specifies a beginning part of the Hamiltonian circuits
represented by the node.
The Shortest path is a,b,c,e,d,a from the figure.

15 Puzzle problem

The 15-puzzle is invented

by sam loyd in 1878. It
consists of 15 numbers
tiles on a square
frame with a capacity of
16 tiles. We are given an
intial arrangement of the
tiles and the
To 1 2 3 4

From 1 ∞ 3 9 7
2 3 ∞ 6 5
3 5 6 ∞ 6
 4 9 7 4 ∞
The 15 Puzzel problem is invented by Sam Loyd in 1878.

The problem cinsist of 15 numbered (0-15) tiles on a square box with 16 tiles(one
tile is blank or empty).

The objective of this problem is to change the arrangement of initial node to goal
node by using series of legal moves.

The Initial and Goal node arrangement is shown by following figure.

1 2 3 4

5 6 8
9 10 7 11
13 14 15 12

Initial Arrangement

1 2 3 4

5 6 7 8
9 10 11 12
13 14 15

Final Arrangement

In initial node four moves are possible. User can move any one of the tile like 2,or
3, or 5, or 6 to the empty tile. From this we have four possibilities to move from
initial node.

The legal moves are for adjacent tile number is left, right, up, down, ones at a time.

Each and every move creates a new arrangement, and this arrangement is called
state of puzzle problem. By using different states, a state space tree diagram is
created, in which edges are labeled according to the direction in which the empty
space moves.

The state space tree is very large because it can be 16! Different arrangements.

In state space tree, nodes are numbered as per the level. In each level we must
calculate the value or cost of each node by using given formula:

C(x)=f(x)+g(x),

f(x) is length of path from root or initial node to node x, g(x) is estimated length of
path from x downward to the goal node.

Number of non blank tile not in their correct position. C(x)< Infinity.(initially set
bound).

Each time node with smallest cost is selected for further expansion towards goal
node.

This node become the e-node. State Space tree with node cost is shown in diagram.

Procedure15-PUZZLE
// live_node_set: set to hold the live nodes at any time
// lowcost: variable to hold the cost of the best cost at any given//
//node //
Begin
lowcost = ∞;

- choose a branching node, k, such that k ∈ live_node_set; // k is a E-node //

While live_node_set ≠∞ do

- live_node_set= live_node_set - {k};

- Generate the children of node k and the corresponding lower bounds;
Sk={(i,zi ): i is child of k and zi its lower bound}

- For each element (i, zi ) in Sk do

- if zi > U //more than lower bound??//
- then - Kill child i; // i is a child node //
- else
if child i is a solution
then
U =zi ; current best = child i;
Else
add child i to live_node_set;
endfor;
Endwhile;
End

objective is to transform
it into the goal
arrangement through a
series of legal moves. For
example, in the given
below fig sometimes, for
a given initial
arrangement it may not
lead to
a goal arrangement. In
the following, we provide
a theorem for testing
whether or not a given
initial arrangement may
lead to a goal
arrangement
The 15-puzzle is invented
by sam loyd in 1878. It
consists of 15 numbers
tiles on a square
frame with a capacity of
16 tiles. We are given an
intial arrangement of the
tiles and the
To 1 2 3 4
From 1 ∞ 3 9 7
2 3 ∞ 6 5
3 5 6 ∞ 6
4 9 7 4 ∞