MIT School of Computing
Department of Computer Science & Engineering
Third Year Engineering
18BTCS501-Design and Analysis of Algorithms
Class - T.Y.
PLD(SEM-I)
Unit - IV
Backtracking & Branch-n-Bound
AY 2023-2024 SEM-I
1
Dept. of Computer Science &
Engineering.
Unit IV - Syllabus
Unit IV- Backtracking & Branch-n-Bound 09 hours
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
Unit 4 - Outline
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
BACKTRACKING: PRINCIPLE
• Backtracking is a technique used to solve
problems with a large search space, by
systematically trying and eliminating possibilities.
• A standard example of backtracking would be
going through a maze.
• At some point, you might have two options of which
direction to go:
Porti
on B
Junction
Portion A
Dept. of Computer Science &
Engineering.
BACKTRACKING [CONT…]
• One strategy would be to try going through
Portion A of the maze.
• If you get stuck before you find your way out, then
you "backtrack" to the junction.
• At this point in time you know that Portion A will
NOT lead you out of the maze,
• So you then start searching in Portion B
Portio
nB
Junction
Portion A
Dept. of Computer Science &
Engineering.
BACKTRACKING [CONT…]
• Clearly, at a single junction you could have even
more than 2 choices.
• The backtracking strategy says to try each choice,
one after the other,
• if you ever get stuck, "backtrack" to the junction and
try the next choice.
• If you try all choices and never found a way out,
then there is no solution to the maze.
Dept. of Computer Science &
Engineering.
BACKTRACKING [CONT…]
dead end
dead end
dead end
?
start ? ?
dead end
dead end
success!
Dept. of Computer Science &
Engineering.
Unit 4 - Outline
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
N-QUEEN PROBLEM
• Problem surfaced in 1848 by chess player Max Bezzel as 8
queens (regulation board size)
• Premise is to place N queens on N x N board so that they are
non-attacking
• A queen is one of six different chess pieces
• It can move forward & back, side to side and to its diagonal and
anti-diagonals
• The problem: given N, find all solutions of queen sets and
return either the number of solutions and/or the patterned
boards.
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: N-QUEEN PROBLEM
• In this problem, a chessboard will be given of 4 X 4
(i.e., 16 cells)
• For 4 X 4 chessboard, we have 4 queens to place in
the chessboard.
• So, just like in the game of chess, a queen can move
in horizontal (i.e., row-wise), vertical (i.e., column-
wise) and diagonal direction.
• So, according to our problem, we have to place all the
4 queens in such a way that no two queens are under
attack.
• When two queens are in the same
row/column/diagonal, we call they are under attack.
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: N-QUEEN PROBLEM [CONT..]
• Generate a list of free cells on the next row.
• If no free cells, backtrack (step 2 of previous row)
• Place a queen on next free cell & proceed with
step 1 for next row
• If no next row, proceed to step 3
• At this point, you have filled all rows, so
count/store as a solution
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE
• Total no. of ways by which we can arrange all the
four queens in the 16 cells are 16C4 ways
1 2 3 4
4
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE
So, let us generate a state-space tree:
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE
So, let us generate a state-space tree:
Total number of nodes=
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE
So, let us generate a state-space tree:
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE
F F F F F Q
Q Q
F F F Q
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE [CONT…]
Q Q
Q Q
F Q
Q Q
Q Q
Q Q
F Q
Dept. of Computer Science &
Engineering.
BASIC ALGORITHM: EXAMPLE [CONT…]
Q Q
Q Q
Q Q
Q Q
F Q
DONE
Dept. of Computer Science &
Engineering.
Unit 4 - Outline
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
SUM OF SUBSETS
• In this problem, a set of weights will be given
• We have to take subset of those weights such
that their sum is exactly equal to a value m
• The solution set is represented as 0/1 form
Dept. of Computer Science &
Engineering.
SUM OF SUBSETS [CONT..]
Each forward and backward moves take O(1) time
Dept. of Computer Science &
Engineering.
SUM OF SUBSETS: Example
• W[1:6] = {5, 10, 12, 13, 15, 18}
• n=6, m=30; where n is the number of number of weights, m is
the target value
• So, selection of the above weights can be done in various ways.
• Hence, let us try all possible ways of their selection and find out
which of those selection is giving us the exact value of m (i.e.,
equals to 30)
• To solve the problem, we will have to draw a state-space tree
for the problem
Dept. of Computer Science &
Engineering.
SUM OF SUBSETS: Example [CONT..]
Dept. of Computer Science &
Engineering.
Unit 4 - Outline
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
BRANCH AND BOUND: PRINCIPLE
• Branch and bound builds the state-space tree
and find the optimal solution quickly by pruning
few of the tree branches which does not satisfy
the bound.
• Backtracking can be useful when some other
optimization techniques like greedy or dynamic
programming fail. Such algorithms are typically
slower than their counterparts.
• In the worst case, it may run in exponential time,
but careful selection of bounds and branches
makes an algorithm to run reasonably faster.
Dept. of Computer Science &
Engineering.
BRANCH AND BOUND: PRINCIPLE [CONT…]
• Branch and bound approach is used to solve
minimization problems and not maximization
problems
• Anyway, we can convert a maximization problem
to minimization problem and solve it.
• One example of minimization optimization
problem is Job sequencing with deadline where
we need to pay the penalty for not doing a job
instead of earning profits for doing a job.
Dept. of Computer Science &
Engineering.
Unit 4 - Outline
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
BRANCH AND BOUND STRATEGIES: FIFO
Dept. of Computer Science &
Engineering.
BRANCH AND BOUND STRATEGIES: LIFO
Dept. of Computer Science &
Engineering.
BRANCH AND BOUND STRATEGIES: LCBB
• Instead of generating entire tree, we always pick-
up the nodes with minimum cost/least cost and
try to explore that one, so that quickly we can
reach the solution.
Dept. of Computer Science &
Engineering.
Unit 4 - Outline
• Backtracking
• n-queen problem
• Sum of subsets problem
• Branch-n-Bound: Principle
• Strategies: FIFO, LIFO and LC approaches
• Travelling Salesperson Problem
• Knapsack problem
Dept. of Computer Science &
Engineering.
THE 0/1 KNAPSACK PROBLEM
• Positive integer P1, P2, …, Pn (profit)
W1, W2, …, Wn (weight)
M (capacity)
n
maximize Pi X i
i 1
n
subject to Wi X i M Xi = 0 or 1, i =1, …, n.
i 1
The problem is modified:
n
minimize Pi X i
i 1
32
Dept. of Computer Science &
Engineering.
THE 0/1 KNAPSACK PROBLEM [CONT..]
Fig. 6-27 The Branching Mechanism in the Branch-and-Bound Strategy
to Solve 0/1 Knapsack Problem.
33
Dept. of Computer Science &
Engineering.
HOW TO FIND THE UPPER BOUND?
• Ans: by quickly finding a feasible solution in a
greedy manner: starting from the smallest
available i, scanning towards the largest i’s until
M is exceeded. The upper bound can be
calculated.
34
Dept. of Computer Science &
Engineering.
THE 0/1 KNAPSACK PROBLEM
• E.g. n = 6, M = 34
i 1 2 3 4 5 6
Pi 6 10 4 5 6 4
Wi 10 19 8 10 12 8
(Pi/Wi Pi+1/Wi+1)
• A feasible solution: X1 = 1, X2 = 1, X3 = 0, X4 = 0,
X5 = 0, X6 = 0
-(P1+P2) = -16 (upper bound)
Any solution higher than -16 can not be an optimal solution.
35
Dept. of Computer Science &
Engineering.
HOW TO FIND THE LOWER BOUND?
• Ans: by relaxing our restriction from Xi = 0 or 1 to 0
Xi 1 (knapsack problem)
n
Let Pi X i be an optimal solution for 0/1
i 1
n
knapsack problem and Pi X i be an optimal
i 1
solution for fractional knapsack problem. Let
n n
Y= Pi X i , Y =
’
Pi X i .
i 1 i 1
Y’ Y
36
Dept. of Computer Science &
Engineering.
THANK YOU
Design and Analysis of Algorithm Unit 3 37
