Branch and Bound Example:

1) Solving 15-Puzzle Problem

Steps to solve 15-Puzzle Problem

The problem consists of 15 numbered (1-15) tiles on a square box

with 16 tiles (one tile is Empty Spot (ES)). The objective of this
problem is to change the arrangement of initial node to goal node
by using series of legal moves. State Space Tree for the 15-puzzle problem

The legal moves in which a tile adjacent is moved to Empty

Spot(ES). Each move creates a new arrangement of tile called
states of the puzzle. There are 16! different arrangements of the
tiles. The initial arrangement is considered as the initial state and
the final arrangement is considered as the goal state.

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

ĉ(x) = f(x) + ĝ(x)

f(x) : length of the path from root to x.

ĝ(x) : number of non-blank tiles not in their goal position.

Each time node with smallest cost is selected for further

expansion towards goal node. This node become the e-node.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 1

Theorem: The goal state is reachable from the initial state if and
only if i=1 to 16 ∑ less(i) + x is same parity (either both odd or both even),
where x is the row number of the empty spot.

Example 1 for Theorem: Check whether the goal state is achieved

from the initial state given below.

Initial State
ĉ(2) = 1+4 = 5 less(1) = 0, less(2) = 0, less(3) = 0, less(4) = 0, less(5) = 0,
ĉ(3) = 1+2 = 3 less(6) = 0, less(7) = 0, less(8) = 0, less(9) = 0, less(10) = 0,
ĉ(4) = 1+4 = 5 less(11) = 0, less(12) = 0, less(13) = 0, less(14) = 0, less(15) = 0
ĉ(5) = 1+4 = 5
Since ĉ (3) is the lowest value, next E-node is node 3. r = 4 (row number of Empty Spot (ES))
∑ (0+0+0+0+0+0+0+0+0+0+0+0+0+0+0) + 4 = 4
ĉ(8) = 2+3 = 5
ĉ(9) = 2+1 = 3 Goal State
ĉ(10) = 2+3 = 5 less(1) = 0, less(2) = 0, less(3) = 0, less(4) = 0, less(5) = 0,
less(6) = 0, less(7) = 0, less(8) = 0, less(9) = 0, less(10) = 0,
Since ĉ (9) is the lowest value, next E-node is node 9. less(11) = 0, less(12) = 0, less(13) = 0, less(15) = 1, less(14) = 0
ĉ(19) = 3+2 = 5
ĉ(20) = 3+0 = 3 r = 4 (row number of Empty Spot (ES))
∑ (0+0+0+0+0+0+0+0+0+0+0+0+0+1+0) + 4 = 5
Next E-node is node 20, which is the answer node.
Since the initial and the goal state are of different parity the goal
state is not reachable from the initial state.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 2

Example 2 for Theorem: Check whether the goal state is achieved 2) Assignment Problem
from the initial state given below. An assignment problem seeks to minimize the total cost of
assignment of m worker to m jobs, given that the cost of worker i
performing job j is c[i,j].

Steps to solve Assignment Problem

There are m workers who need to be assigned to m jobs, one

worker per job. The problem is to find an assignment with the
Initial State minimum total cost.
less(1) = 0, less(2) = 0, less(3) = 0, less(4) = 0, less(5) = 0,
less(6) = 0, less(7) = 0, less(8) = 1, less(9) = 1, less(10) = 1, For each worker, we choose job with minimum cost from list of
less(11) = 0, less(12) = 0, less(13) = 1, less(14) = 1, less(15) = 1 unassigned jobs (take minimum entry from each row).

r = 2 (row number of Empty Spot (ES)) Branch and Bound algorithm

∑ (0+0+0+0+0+0+0+1+1+1+0+0+1+1+1) + 2 = 8 1. Recursively divide the state space into smaller spaces
and minimize “costs” on these spaces. This process is called
Goal State branching.
less(1) = 0, less(2) = 0, less(3) = 0, less(4) = 0, less(5) = 0, 2. To improve performance, bound is used to limit the
less(6) = 0, less(7) = 0, less(8) = 0, less(9) = 0, less(10) = 0, space in the state space that is generated.
less(11) = 0, less(12) = 0, less(13) = 0, less(14) = 0, less(15) = 0

r = 4 (row number of Empty Spot (ES))

∑ (0+0+0+0+0+0+0+0+0+0+0+0+0+0+0) + 4 = 4

Since the initial and the goal state are same parity (even), the goal
state is reachable from the initial state.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 3

Example: Find the optimal solution using Branch and Bound for the
following assignment problem.

Solution

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 4

3) Knapsack Problem Example 1: Solve the following instance of the knapsack problem
Given a bag with maximum weight capacity of W and a set of by the branch and bound algorithm.
items, each having a weight and a value associated with it. Decide
the number of each item to take such that the total weight is less
than the capacity and the total value is maximized.

The objective is to obtain filling of knapsack with maximum profit

earned but it should not exceed weight of the knapsack.

Steps to solve Knapsack Problem Solution:

Compute Value/Weight for each item.
 For each item, compute its value / weight ratio.
 Arrange all the items in decreasing order of their value /
weight ratio.
 Start putting the items into the knapsack beginning from
the item with the highest ratio.
 Put as many items with maximum profit earned but it
should not exceed weight of the knapsack.

How to Compute the Upper Bound?

Compute the Upper Bound

v => value of the items selected

W - w => Remaining capacity of the knapsack Computation at Node 0
No item is selected initially
vi+1/wi+1 => best payoff per weight unit i=0
w=0, v=0, W=10
vi+1/wi+1 = v1/w1=10
ub= v + (W-w) (vi+1/wi+1)
= 0 + (10-0) (10)
ub= $ 100

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 5

Computation at Node I Computation at Node II Computation at Node VII Computation at Node VIII
With item1 Without item1 With item4 Without item4
i=1 i=1 i=4 i=4
w=4, v=40, W=10 w=0, v=0, W=10 w=9+3=12, W=10 w=9, v=65, W=10
vi+1/wi+1 = v2/w2=6 vi+1/wi+1 = v2/w2=6 This exceed the capacity of vi+1/wi+1 = v5/w5=0
ub= v + (W-w) (vi+1/wi+1) ub= v + (W-w) (vi+1/wi+1) knapsack. It is not feasible. ub= v + (W-w) (vi+1/wi+1)
= 40 + (10-4) (6) = 0 + (10-0) (6) = 65 + (10-9) (0)
ub= $ 76 ub= $ 60 ub= $ 65

Computation at Node III Computation at Node IV Thus solution is pick up (item1, item3) and
With item2 Without item2 gain maximum profit = $40+$25 = $65
i=2 i=2 State Space Tree
w=4+7=11, W=10 w=4, v=40, W=10
This exceed the capacity of vi+1/wi+1 = v3/w3=5
knapsack. It is not feasible. ub= v + (W-w) (vi+1/wi+1)
= 40 + (10-4) (5)
ub= $ 70

Computation at Node V Computation at Node VI

With item3 Without item3
i=3 i=3
w=4+5=9, v=40+25=65, W=10 w=4, v=40, W=10
vi+1/wi+1 = v4/w4=4 vi+1/wi+1 = v4/w4=4
ub= v + (W-w) (vi+1/wi+1) ub= v + (W-w) (vi+1/wi+1)
= 65 + (10-9) (4) = 40 + (10-4) (4)
ub= $ 69 ub= $ 64

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 6

Example 2: Solve the following instance of the knapsack problem Solution is pick up (item1, item2, item3, item5) and
by the branch and bound algorithm. gain maximum profit = $18+$40+$35+$2= $95

State Space Tree

Note: This is the solution for knapsack because the weight of selected items
(w=15) is equal to capacity (W=15) for knapsack.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 7

Example 3: Solve the following instance of the knapsack problem Example 4: Explain how branch and bound technique is used to
by the branch and bound algorithm. solve knapsack problem. Solve it for the example n=4, m=15,
{p1….p4}={45,30,45,10}, {w1…..w4}={3,5,9,5}
Solution:
Given m=15 (Capacity W=15)
ub= p + (m-w) (pi+1/wi+1)

Solution:

Solution is pick up (item1, item3) and

gain maximum profit = $45+$45 = $90
Solution is pick up (item2, item3) and State Space Tree
gain maximum profit = $63+$56 = $119
State Space Tree

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 8

4) Travelling Salesman Problem Example 1: Apply Branch and Bound Algorithm to solve the
Given a set of cities and distance between every pair of cities, the Traveling Salesman Problem
problem is to find the shortest possible tour that visits every city
exactly once and returns to the starting point.

If salesman starting city is A, then a TSP tour in the graph is

A→B→D→C→A
Solution
Cost of the tour Calculate Lower Bound(LB)
= 10 + 25 + 30 + 15 a->ac+ab=1+3=4
= 80 units b->ba+bc=3+6=9
c->ca+ce=1+2=3
How to calculate Lower Bound (LB) d->de+dc=3+4=7
LB=∑(Sum of costs of two least cost edges adjacent to v) / 2 e->ec+ed=2+3=5
lb=(4+9+3+7+5)/2=28/2=14
Steps to solve Travelling Salesman Problem lb=14

For each city i, 1≤ i ≤ n,

 find the sum si of the distances from city i to the two
nearest cities
 compute the sums of these n numbers
 divide the result by 2
 Round up the result to the nearest integer
LB=∑(Sum of costs of two least cost edges adjacent to v) / 2
 Repeat this process until all the cities are covered.
CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 9
Node1: a-b (ab) Node2: a-c (ac) Node8: a-b-c-d (ab,bc,cd) Node9: a-b-c-e (ab,bc,ce)
a->ab+ac=3+1=4 a->ac+ab=1+3=4 a->ab+ac=3+1=4 a->ab+ac=3+1=4
b->ab+bc=3+6=9 b->9 b->ab+bc=3+6=9 b->ab+bc=3+6=9
c->3 c->ac+ce=1+2=3 c->bc+cd=6+4=10 c->bc+ce=6+2=8
d->7 d->7 d->cd+de=4+3=7 d->7
e->5 e->5 e->5 e->ce+ed=2+3=5
lb=(4+9+3+7+5)/2=28/2=14 lb=(4+9+3+7+5)/2=28/2=14 lb=(4+9+10+7+5)/2=35/2=18 lb=(4+9+8+7+5)/2=33/2=17
lb=14 lb=14 lb=18 lb=17
Node3: a-d (ad) Node4: a-e (ae)
a->ad+ac=5+1=6 a->ae+ac=9+1=10 Node10: a-b-c-e-d (ab,bc,ce,ed)
b->9 b->9 a->ab+ac=3+1=4
c->3 c->3 b->ab+bc=3+6=9
d->ad+de=5+3=8 d->7 c->bc+ce=6+2=8
e->5 e->ae+ec=9+2=11 d->ed+dc=3+4=7
lb=(6+9+3+8+5)/2=31/2=16 lb=(10+9+3+7+10)/2=40/2=20 e->ce+ed=2+3=5
lb=16 lb=20 lb=(4+9+8+7+5)/2=33/2=17
lb=17
Node5: a-b-c (ab,bc) Node6: a-b-d (ab,bd) State Space Tree
a->ab+ac=3+1=4 a->ab+ac=3+1=4
b->ab+bc=3+6=9 b->ab+bd=3+7=10
c->bc+ca=6+1=7 c->3
d->7 d->bd+de=7+3=10
e->5 e->5
lb=(4+9+7+7+5)/2=32/2=16 lb=(4+10+3+10+5)/2=32/2=16
lb=16 lb=16
Node7: a-b-e (ab,be)
a->ab+ac=3+1=4
b->ab+be=3+10=13
c->3
d->7
e->be+ec=10+2=12
lb=(4+13+3+7+12)/2=39/2=20
lb=20

Hence the optimum cost tour of TSP is a-b-c-e-d-a with cost 17.
CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 10
Example 2: Apply Branch and Bound Algorithm to solve the State Space Tree
Traveling Salesman Problem

Solution
Calculate Lower Bound(LB)
a->ab+ac=2+5=7
b->ba+bd=2+3=5
c->cd+ca=1+5=6
d->dc+db=1+3=4
lb=(7+5+6+4)/4=22/2=11
lb=11

Node4: a-b-c (ab,bc) Node5: a-b-d (ab,bd)

Node1: a-b (ab) Node2: a-c (ac) a->ab+ac=2+5=7 a->ab+ac=2+5=7
a->ab+ac=2+5=7 a->ac+ab=5+2=7
b->ab+bc=2+8=10 b->ab+bd=2+3=5
b->ab+bd=2+3=5 b->5 c->bc+cd=8+1=9 c->6
c->6 c->ac+cd=5+1=6 d->4 d->bd+dc=3+1=4
d->4 d->4 lb=(7+10+9+4)/2=30/2=15 lb=(7+5+6+4)/2=22/2=11
lb=(7+5+6+4)/2=22/2=11 lb=(7+5+6+4)/2=22/2=11 lb=15 lb=11
lb=11 lb=11
Node3: a-d (ad)
a->ad+ab=7+2=9 Node6: a-b-d-c (ab,bd,dc)
b->5 a->ab+ac=2+5=7
c->6 b->ab+bd=2+3=5
d->ad+dc=7+1=8 c->dc+ca=1+5=6
lb=(9+5+6+8)/2=28/2=14 d->bd+dc=3+1=4
lb=14 lb=(7+5+6+4)/2=22/2=11
lb=11

Hence the optimum cost tour of TSP is a-b-d-c-a with cost 11.
CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 11
1) What is Backtracking? 4) State Hamiltonian Circuit (Cycle) problem.
Backtracking is an algorithm that finds all the possible Hamiltonian Cycle or Circuit is a path in an undirected graph
solutions and selects the desired solution from the given set of that visits all the vertices in the graph exactly once and returns
solutions. to the starting vertex.
When to Use a Backtracking Algorithm?
Problem Statement: Given an undirected graph, our task is to
 There are multiple possible solutions to the problem.
 The problem can be broken down into smaller sub- determine whether the graph contains a Hamiltonian cycle or
problems. not.
 The sub-problems can be solved independently.

Applications: n-Queens problem, Hamiltonian Circuit

problem, Subset Sum problem, Graph coloring problem

2) List the applications of Backtracking.

Applications of Backtracking
n-Queens problem
Hamiltonian Circuit problem
Subset Sum problem
Graph coloring problem
5) State Subset Sum problem.
Given a set of non-negative integers and a value sum, the task
3) What is meant by n-Queens problem?
The n-queens puzzle is the problem of placing n queens on an is to check if there is a subset of the given set whose sum is
n x n chessboard such that no two queens attack each other. equal to the given sum.
A queen will attack another queen if it is placed in horizontal,
vertical or diagonal points in its way. Examples:

Example: Suppose the given chessboard is of size 4x4 and we

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
have to arrange exactly 4 queens in it. The solution
arrangement is: Output: True
Explanation: There is a subset (4, 5) with sum 9.

Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30

Output: False
Explanation: There is no subset with sum 30.

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 12

6) What is a Graph Coloring problem? 8) How do you solve a 15-Puzzle problem?
Graph coloring refers to the problem of coloring vertices of a The problem consists of 15 numbered (1-15) tiles on a square
graph in such a way that no two adjacent vertices have the box with 16 tiles (one tile is Empty Spot (ES)).
same color.
Graph coloring can be described as a process of assigning The objective of this problem is to change the arrangement of
colors to the vertices of a graph. This is also called the vertex initial node to goal node by using series of legal moves. The
coloring problem. legal moves in which a tile adjacent is moved to Empty
The minimum number of colors needed to color a graph is Spot(ES).
called its chromatic number.

7) What is Branch and Bound technique?

Branch and Bound technique works by dividing the problem 9) State the Assignment problem.
into branches (BRANCH) and then eliminate certain branches An assignment problem seeks to minimize the total cost of
based on bounds (BOUND) on the optimal solution. This assignment of m worker to m jobs, given that the cost of worker
process continues until the best solution is found or all i performing job j is c[i,j].
branches have been explored.
There are m workers who need to be assigned to m jobs, one
worker per job. The problem is to find an assignment with the
minimum total cost.

Applications: 15-Puzzle problem, Assignment problem,

Knapsack problem, Travelling Salesman problem (TSP)

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 13

10) State the Knapsack problem.
Given a bag with maximum weight capacity of W and a set of
items, each having a weight and a value associated with it.
Decide the number of each item to take such that the total
weight is less than the capacity and the total value is
maximized.

The objective is to obtain filling of knapsack with maximum

profit earned but it should not exceed weight of the knapsack.

11) State the Travelling Salesman problem (TSP)

Given a set of cities and distance between every pair of cities,
the problem is to find the shortest possible tour that visits
every city exactly once and returns to the starting point.

If salesman starting city is A, then a TSP tour in the graph is

A→B→D→C→A

Cost of the tour

= 10 + 25 + 30 + 15
= 80 units

CS3401-ALGORITHMS (Sem-IV-R2021) - UNIT-IV: 14