Dr.

Mahalingam College of Engineering and Technology

(An Autonomous Institution)
Handout
Subject: 23CST301-Design and Analysis of Algorithms

Module2 Advanced Algorithm Design Techniques

Limitations of Algorithm Power: P, NP and NP Complete problems

Greedy Technique: Container Loading - Knapsack Problem - Job Sequencing with
Deadlines - Huffman Tree
Dynamic Programming Technique: Binomial Coefficient - Warshall’s algorithm -
Multistage Graph – String Edit Distance
Backtracking Technique: n-Queens problem - Hamiltonian Circuit - Subset-sum problem -
Graph colouring
Branch and Bound Technique: Assignment problem - Knapsack problem – Travelling
salesman problem.

Limitations of Algorithm Power

Some problems cannot be solved by any [Link] problems can be solved
algorithmically but not in polynomial time
Tractable Problems
• An algorithm solves a problem in polynomial time if its worst-case time efficiency
belongs to O(p(n)) where p(n) is a polynomial of the problem’s input size n
• Problems that can be solved in polynomial time are called tractable
• Problems that cannot be solved in polynomial time are called intractable
Class P
• Several problems can be solved in polynomial time
• Searching
• Sorting
• String Matching
• GCD Computation
• Minimum Spanning Tree construction
Class P is a class of decision problems that can be solved in polynomial time by
(deterministic) algorithms. This class of problems is called polynomial
• Decision problems have an Yes / No answer
• Many non-decision problems involve generating all subsets (exponential)
or all permutations (factorial) – definitely not polynomial
• Many non-decision problems can be reduced to decision problems
Decision Problems
• Graph Coloring
• Optimization problem: find the minimum number of colors needed to color
the graph
• Decision problem: Can the graph be colored using 3 colors?
Problem Optimization Problem Decision Problem
Traveling Given a complete weighted graph, Given a complete weighted graph and
Salesperson find a minimum weight Hamiltonian an integer k, is there a Hamiltonian
cycle? cycle with total weight at most k?
Job Scheduling Determine a schedule incurring For the given problem and integer k, is
minimum possible penalty there a schedule with penalty <= k?
Bin Packing Determine the smallest number of Do the objects fit into k bins?
Application: bins into which the objects can be
Memory Storage, packed.
Filling orders
Undecidable problems
• Not all decision problems can be solved in polynomial time
• Some Decision problems cannot be solved by any algorithm – Undecidable
problems
• Halting Problem
• Identified by Alan Turing
• Given a computer program and its input determine whether the program
will halt on that input or continue working indefinitely on it
Halting Problem
• Assume A is an algorithm that solves the halting problem for any program P and
input I

• Consider program P as an input to itself and use the output of algorithm A for pair
(P, P) to construct a program Q

• When Q is given as input to Q

• Substituting P by Q

• Results in a Contradiction
• Halting problem is undecidable
• Other un-decidable problems
• Wang tiling, Mortal matrix multiplication
Decision problems
• Solving may be difficult
• Checking whether a proposed solution solves the problem is easy
• Can be done in polynomial time
• Ex: Hamiltonian circuit
• a – b – c –e – d – h – g – f
• a–b–c–h–g–f–d–e
 • Ex: Graph Coloring
• R, R, G, G, R

Class NP
• Non-deterministic Polynomial
• Class of Decision problems that can be solved by non-deterministic polynomial
algorithms.
• Most decision problems are in NP
• P  NP
• P = NP? – Open problem

Greedy Technique
Greedy algorithms work in phases. In each phase, a decision is made that appears to be
good, without regard for future consequences. Generally, this means that some local
optimum is chosen. It can be used for approximate problem solving.
It constructs a solution through a sequence of steps, each expanding a partially
constructed solution obtained so far, until a complete solution to the problem is reached.
In each step, the choice made must be:
• Feasible- it has to satisfy the problem’s constraints
• Locally optimal-it has to be the best local choice among all the feasible choices
available in that particular step
• Irrevocable-once made - it cannot be changed on the subsequent steps of the
algorithm

Container Loading Problem

• A large ship is to be loaded with cargo. The cargo is containerized and all
containers are the same size. Different containers may have different weights. Let
wi be the weight of the ith container,1<=i<=n. The cargo capacity of the ship is c.
Load the ship with the maximum number of containers.
Greedy Solution
• The ship is loaded in stages
• One container per stage
• At each stage decide which container to load
• Use greedy criterion
• From the remaining containers select the one with least weight
• This order of selection will keep the total weight of the selected containers
minimum and leave maximum capacity for loading more containers.
• First select the container that has least weight ,then the one with the next
smallest weight and so on until either all containers have been loaded or
there isn’t enough capacity for the next one

Containers 1 2 3 4 5 6 7 8

weight 100 200 50 90 150 50 20 80

Capacity:400

The containers are considered loading in the order 7,3,6,8,4,1,5,[Link] 7,3,6,8,4 and
1 weigh 390 units and are [Link] available capacity is now 10 units which is
inadequate for any of the remaining containers.
• Solution
• [x1,x2……x8]=[1,0,1,1,0,1,1,1]
•

Knapsack Problem
Pack knapsack with a capacity of c. From a list of n items, select the items that are to be
packed in to the knapsack. Each object i has a weight wi and a profit pi. In a feasible
knapsack packing, the sum of the weights of the packed objects does not exceed the
knapsack capacity. An optimal packing is a feasible one with maximum profit.
The problem formulation is

Maximize
Subject to the constraints

Item 1 Item2 Item3 Item4

Weight 2 4 6 7
Profit 6 10 12 13
p/w 3 2.5 2 1.8

When k=0 the knapsack is filled in decreasing order of profit density

p/w=[6/2,10/4,12/6,13/7]=[3,2.5,2,1.8]
 X=[1,1,0,0]
Profit=16

When K=1
Subsets {1},{2},{3} and {4}
Solution
• Begin with Subset{3} remaining capacity [Link] remaining objects in
order of profit [Link] object 1 is considered.3 units of capacity
remain.
• The solution obtained when begin with the subset {3} in the knapsack is
• X=[1,0,1,0]
• Profit=18
• Begin with subset {4}
• Solution x=[1,0,0,1]
• Profit=19
• The best solution obtained considering subsets of size 0 and 1 is [1,0,0,1]
When K=2
Subsets {1,2},{1,3},{1,4},{2,3},{2,4}, and {3,4}
• Solution
• [1,1,0,0],[1,0,1,0],[1,0,0,1],[0,1,1,0],[0,1,0,1]
• The last of these solutions has the profit value 23, which is higher than that
obtained from the subsets of size 0 and 1

Job Sequencing with Deadlines

Given n number of jobs with a starting time and ending time,they need to be scheduled in
such a way that maximum profit is received within the maximum deadline
Algorithm
Step1:Find the maximum deadline value from the input set of jobs
Step2:Once the deadline is decided, arrange the jobs in descending order of their
profits
Step3:Select the job with highest profits,their time periods not exceeding the
maximum deadline
Step4:The selected set of jobs are the output.

Jobs J1 J2 J3 J4 J5
Deadlines 2 2 1 3 4
Profits 20 60 40 100 80

Step1:Find the maximum deadline value dm from the deadlines given Dm=4
Step2:Arrange the jobs in descending order of their profits
The maximum deadline dm is [Link] all the tasks must end before 4
Choose the job with highest profit [Link] takes up 3 parts of the maximum deadline.
Therefore the next job must have the time period 1
Total profit=100

Jobs J4 J5 J2 J3 J1
Deadlines 3 4 2 1 2
Profits 100 80 60 40 20
Step3:The next job with highest profit is [Link] the time taken by J5 is 4,which exceeds
the deadline by 3
Step4:The next job with higher profit is [Link] time taken by J2 is 2,which also exceeds
the deadline by 1
Step 5: The next job with higher profit is [Link] time taken by J3 is,which does not exceed
the given deadline. Therefore J3 is added to the output set
Step6:Since the maximum deadline is met, the algorithm comes to an end. The output set
of jobs scheduled within the deadline are {J4,J3} with the maximum profit of 140

Huffman Tree
Coding: Assignment of bit strings to alphabet characters
Code words: Bit strings assigned for characters of alphabet
• Example: We can code {a,b,c,d} as {00,01,10,11} or {0,10,110,111} or
{0,01,10,101}.
Two types of codes:
• fixed-length encoding (e.g., ASCII)
• variable-length encoding (e,g., Morse code)

Prefix-free codes (or prefix-codes): no code word is a prefix of another code word
• It allows for efficient (online) decoding
• {a,b,c,d} – Prefix free code {0,10,110,111}
• {a,b,c,d} – Non-Prefix free code {0,01,10,101}
• Decoding the message 10010110 - BABC

If frequencies of the character occurrences are known, what is the best / optimal binary
prefix-free code?
• Shortest average code length. The average code length represents on the
average how many bits are required to transmit or store a character.
• E.g. if P(a) = 0.4, P(b) = 0.3, P(c) = 0.2, P(d) = 0.1, given the code {a,b,c,d} –
{0,10,110,111} then the average length of code is 0.4 + 2*0.3 + 3*0.2 +
3*0.1 = 1.9 bits
Huffman codes
• Any binary tree with edges labeled with 0s and 1s yields a prefix-free code of
characters assigned to its leaves
• Optimal binary tree minimizing the average length of a codeword can be
constructed using Huffman’s algorithm

0 1

0 1

Tree represents {00, 011, 1}

 Huffman’s algorithm

• Step 1: Initialize n one-node trees with alphabet characters and the tree weights
with their frequencies.
• Step 2: Repeat the following step n-1 times: join two binary trees with smallest
weights into one (as left and right sub-trees) and make its weight equal the sum
of the weights of the two trees.
• Step 3: Mark edges leading to left and right sub-trees with 0s and 1s, respectively.

A tree constructed by the this algorithm is called a Huffman tree.

Example
Character A B C D _
Frequency 0.35 0.1 0.2 0.2 0.15

• Create 5 single nodes for the characters and arrange them by ascending order of
frequency

0.15
0.1
0.2
0.15
0.2
0.2
0.35
0.2 0.35

_ BC D_ AC D A

• Combine the two nodes with lowest frequency – ‘B’ and ‘_’

0.2 0.2 0.2 0.35 0.35

0.25 0.25
D C D A A

0.1
0.1 0.15
0.15 0.2
0.1 0.2
0.15 0.35
B
B __
BC _D A
0.2 0.2 0.35
C D • Now there
A are 4 nodes – arrange them in ascending order

.25 0.35 0.4

0.2 0.2 0.35 0.35
A0.25 0.25 0.4
C 0.35 D A A
0.25
0.15 A 0.2 0.2
_ 0.1 0.15 C 0.1 D 0.15 0.2 0.2
0.1 0.15
B _ B _ C D
B _

0.4 • Combine the two

0.6nodes with lowest frequency – ‘C’ and ‘D’

0.4 0.6
0.35 0.25 0.4 0.35 0.4
A0.2 0.35
0.25 A
D
0.2 0.2 0.2 0.2 A
0.25 0.35
0.1C 0.15
D 0.2 0.2
0.1 C 0.15 D A
B _ C D
B _
0.1 0.15
0.6
B _
1.0 0.6
 0.2 0.35 B _
0.25
D A
• Arrange the 3 available nodes in ascending order
0.1 0.15
0.1
B 0.15
_ 0.2 0.2 0.35
0.25 0.35 0.4
B _ C D A
A

25 0.10.35 0.15 0.4 0.2 0.2

A
0.2
B 0.2
_ C 0.35 D
0.25
0.15 C D 0.2 0.2 A
_
• Combine the two C
nodes with
D
lowest frequency:
Sub-tree ‘B’ & ‘_’ and ‘A’
0.1 0.15 0.6
0.4
0.2 0.35 B _
0.4 0.6
D A
0.2 0.2
0.25 0.35
0.2
C 0.25
0.25 D 0.35
0.35 0.4 A
D
A
A
0.35
0.25
0.1 A 0.15 0.1 0.15
0.1 0.15 0.2 0.2
B _ B _
B _ C D
0.15 • There are only two nodes available
_ 1.0
1.0
0 1
0.4 0.6
0 1
0.4 0.6
1
0.35
0 1 0.2 0.4 0.2 0
0.4 0.6 0.35
0.25
A
0.2 0.2 C 0 D 1 0 1
0.25 0.35 A
C D A
0 1
0.2 0.2 0.2 0.2 0.1 0.15
0.25 0.35
C C
0.1 D D
0.15
B _
0 1 A
B _
• Combine the two nodes to build a single tree
0.1 0.15
1.0
0.6 B _
0 1

0.4 0.6
0.25 0.35
0 1 0 1
A
0.2 0.2 0.35
0.25
.1 0.15 C D
0 1 A
B _
0.1 0.15
B _
1.0
1
 B _

1.0
0 1

0.4 0.6
0 1 0 1

0.2 0.2 0.35

0.25
C D A
0 1

0.1 0.15
B _

Character Frequency Code

A 0.35 11
B 0.1 100
C 0.2 00
D 0.2 01
_ 0.15 101

• Average bits per character: (frequency*code_length)=2.25

• For fixed-length encoding: 3
• Compression ratio: (3-2.25)/3 * 100% = 25%
Encoding: DAD – 011101
Decoding: 0011100 – CAB

Dynamic Programming Technique

Binomial Coefficient
C(n,k) = n! / k! (n-k)!
Dynamic Programming Recurrence
C(n,k) = C(n-1,k-1) + C(n-1,k) for n > k > 0
C(n,0) = C(n, n) = 1
0 1 2 3 4 5 6

0 1

1 1 1
1 2
2 1
1 3 3
3 1
6 4
4 1 4 1

5 1 5 10 10 5 1

6 1 6 15 20 15 6 1
ALGORITHM Binomial(n,k)
// Computes C(n,k) by dynamic programming
// Input: A pair of non-negative integers n > k > 0
// Output: Value of C(n, k)

-1, j-1] + C[i-1,j]

return C[n,k]

Finding all pair shortest path using Warshall’s algorithm

Floyds Algorithm
Input: Weighted Connected Graph
Output: All Pairs Shortest Path
Distance Matrix – length of shortest path from vertex i to vertex j
Suitable for directed and undirected graphs
Graph must not contain cycle of negative length

Distance matrix computed through a series of n x n

matrices
D(k) – length of shortest path from i to j with
intermediate vertices up to k
D(0) – length of direct path from i to j - Weight matrix
D(1) – length of shortest path from i to j via vertex 1
D(2) – length of shortest path from i to j via vertex 1, 2
D(n) – length of shortest path from i to j using all vertices
1..n

a b c d

a 0 ∞ 3 ∞

b 2 0 ∞ ∞

c ∞ 7 0 1

d 6 ∞ ∞ 0
 a b c d

a 0 ∞ 3 ∞

b 2 0 5 ∞

c ∞ 7 0 1

d 6 ∞ 9 0

a b c d

a 0 ∞ 3 ∞

b 2 0 5 ∞

c 9 7 0 1

d 6 ∞ 9 0

a b c d

a 0 10 3 4

b 2 0 5 6

c 9 7 0 1

d 6 16 9 0

a b c d

a 0 10 3 4

b 2 0 5 6

c 7 7 0 1

d 6 16 9 0
Multistage Graph problem

Multistage graph G(V,E)

A directed graph in which the vertices are partitioned into k≥2 disjoint sets Vi, 1≤i≤k
If <u,v> Є E, then u Є Vi and v Є Vi+1 for some i, 1≤i<k
|V1|= |Vk|=1, and s(source) Є V1 and t(sink) Є Vk

4
A D
1 18
11 9

2 5 13
S B E T
16 2

5
C 2
F

Dynamic Programming formulation

Every s to t path is the result of a sequence of k-2 decisions
ith decision involves determining which vertex in Vi+1 is to be on the path (for i
between 1 and k-2)
p(i,j) = a minimum-cost path from vertex j in Vi to vertex t
cost(i,j) = cost of path from stage i, vertex j to destination
w(i,j)=cost of edge <i,j>
cost (i, j )  min {w ( j , l )  cost (i  1, l )}
l Vi 1
 j ,l   E
Stage 5
cost(5,12) = 0.0
Stage 4
cost(4,9) = min {4+cost(5,12)} = 4
cost(4,10) = min {2+cost(5,12)} = 2
cost(4,11) = min {5+cost(5,12)} = 5
Stage 3
cost(3,6) = min {6+cost(4,9), 5+cost(4,10)} = 7
cost(3,7) = min {4+cost(4,9), 3+cost(4,10)} = 5
cost(3,8) = min {5+cost(4,10), 6+cost(4,11)} = 7

Stage 2
cost(2,2) = min {4+cost(3,6), 2+cost(3,7), 1+cost(3,8)} = 7
cost(2,3) = min {2+cost(3,6), 7+cost(3,7)} = 9
cost(2,4) = min {11+cost(3,8)} = 18
cost(2,5) = min {11+cost(3,7), 8+cost(3,8)} = 15
Stage 1
cost(1,1) = min {9+cost(2,2), 7+cost(2,3), 3+cost(2,4), 2+cost(2,5)} = 16
 2 4
9 2 2 6 6 9
1 5 4
7 3 4
7 3 2
1 3 7 10 12
4 11 5 5
2 6
11 8 8 11
5

String Edit Distance

We are given two strings ‘S1’ and ‘S2’. We need to convert S1 to S2. The following three
operations are allowed:

 Insertion of a character.
 Deletion of a character.
 Replacement of a character with another one.
the minimum number of operations required to convert S1 to S2 as our answer.

Given two strings (sequences) return the “distance” between the two strings as measured
by the minimum number of “character edit operations” needed to turn one sequence into
the other.

Dynamic Programming approach: Now let's see how we can optimize the time
complexity of this algorithm. The partial recursion tree of call sequence for function
findDistance(String str1, String str2, int m, int n) would look like following -

As highlighted above, there are function calls with same arguments which are being
computed again and again. To avoid these redundant computations, we use dynamic
programming based approach.
In this method, we use bottom up approach to compute the edit distance between str1
and str2. We start by computing edit distance for smaller sub-problems and use the
results of these smaller sub-problems to compute results for sub-sequent larger
problems. The results are stored in a two dimensional array as shown below.

Each cell (m,n) of this array represents distance first 'm' characters of str1 and first 'n'
characrers of str2. For example, when 'm' is 0, distance between str1 which is of 0 length
and str2 of 'n' length is 'n'. Please observe 0th row of above matrix. Same is the case for
values in 0th column where str2 is of 0 length.

Now in this matrix, for cell (m,n) which represents distance between str1 of length 'm'
characters and str2 of length 'n' characters, if 'm'th character of str1 and 'n'th character
of str2 are same, then we simply need to fill cell(m,n) using value of cell (m-1, n-1) which
represents edit distance between first 'm-1' characters if str1 and first 'n-1' characters of
str2. Notice the red arrows in the above array.

If 'm'th character of str1 is not equal to 'n'th character of str2, then we choose minimum
value from following three cases-

1. Delete 'm'th character of str1 and compute edit distance between 'm-1' characters of
str1 and 'n' characters of str2. For this computation, we simply have to do - (1 + array[m-
1][n]) where 1 is the cost of delete operation and array[m-1][n] is edit distance between
'm-1' characters of str1 and 'n' characters of str2.
2. Similarly, for the second case of inserting last character of str2 into str1, we have to do
- (1 + array[m][n-1]).
3. And for the third case of substituting last character of str1 by last character of str2 we
use - (1 + array[m-1][n-1]).

Please checkout function 'findDistance(String str1, String str2)' in code snippet for
implementation details. The time and space complexity of this method is O(mn) where
'm' is the length of str1 and 'n' is the length of str2.
 Backtracking Technique
n-Queens problem
Problem Statement:
N - Queens problem is to place n - queens in such a manner on an
n x n chessboard that no queens attack each other by being in the
same row, column or diagonal.

It can be seen that for n =1, the problem has a trivial solution, and
no solution exists for n =2 and n =3. So first we will consider the 4
queens problem and then generate it to n - queens problem.

Given a 4 x 4 chessboard and number the rows and column of the

chessboard 1 through 4.

Since, we have to place 4 queens such as q1 q2 q3 and q4 on the

chessboard, such that no two queens attack each other. In such a conditional each queen
must be placed on a different row, i.e., we put queen "i" on row "i."

Now, we place queen q1 in the very first acceptable position (1, 1). Next, we put queen q2
so that both these queens do not attack each other. 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 in
column 3, i.e. (2, 3) but then no position is left for placing queen 'q3' safely. So we
backtrack one step and place the queen 'q2' in (2, 4), the next best possible solution. Then
we obtain the position for placing 'q3' which is (3, 2). But later this position also leads to
a dead end, and no place is found where 'q4' can be placed safely. Then we have to
backtrack till 'q1' and place it to (1, 2) and then all other queens are placed safely by
moving q2 to (2, 4), q3 to (3, 1) and q4 to (4, 3). That is, we get the solution (2, 4, 1, 3).
This is one possible solution for the 4-queens problem. For another possible solution, the
whole method is repeated for all partial solutions. The other solutions for 4 - queens
problems is (3, 1, 4, 2) i.e.
 One possible solution for 8 queens problem is shown in fig:

1. Thus, the solution for 8 -queen problem for (4, 6, 8, 2, 7, 1, 3, 5).

2. If two queens are placed at position (i, j) and (k, l).
3. Then they are on same diagonal only if (i - j) = k - l or i + j = k + l.
4. The first equation implies that j - l = i - k.
5. The second equation implies that j - l = k - i.
6. Therefore, two queens lie on the duplicate diagonal if and only if |j-l|=|i-k|

Pseudocode:

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;
}
Hamiltonian Circuit
Problem Statement:
A Hamiltonian circuit is a specific type of cycle in a graph, defined as a closed path that
visits every vertex exactly once and returns to the starting vertex.

Applications:
 Traveling Salesman Problem (TSP)
 Integrated Circuit Design
 Network Routing
 Genomics

a b

1 D
2 c ea f
d
D So a
e
ea lu
d n e
d ti
d
G e o
n n
d
0
a

1
b
f
2
9
c
f
3 6 1
d e 0
e
4 G 7 8 1
e r d f 1c
a
5 a p
f h
State space tree
Dead end
Subset-sum problem
Problem Statement:
Given a set of positive integers S = {s1, s2, .. sn}
Objective: Identify subset which will sum to a given integer d
Example:
S = {1, 2, 5, 6, 8} and d= 9 Subsets: {1, 8} and {1, 2, 6}
S = {1, 4, 5} and d=3; No Solution
Example:
S = { 3, 5, 6, 7} ; d = 15
0
With 6 W/o 3
With 3

0
3
With 5 W/o 5
With 5 W/o 5

5 0
8 3
W/o 6
With 6 W/o6 With 6 X
With 6 W/o6
0+ 13 < 15
14 8 9 3 11 5
X
X With 7 9 + 7 > 15 X X X
W/o7
14 + 7 > 15 3+ 7 < 15 11+ 7 >15 5+ 7 < 15
15 8
Solution X
8 < 15
Complete State Space tree
ALGORITHM Bound (X[1:n], r, d)
S0
for i  1 to r
if(X[i] = 1) S  S + A[i] // Compute the sum of all included elements
if (S = d) // Solution node
print X[1:n]
return true // algorithm and process stopped
else if (S + A[r+1] > d)
return (false) // Sum is too large
else
for i  r+1 to n S  S + A[i]
if (S < d) return (false) // Sum is too small
return true // Valid - If none of the constraints are violated

Graph coloring
Problem Statement:
Graph Coloring is the process of assigning colors to the vertices of a graph in such a way
that no two adjacent vertices have the same color, while minimizing the total number of
colors used.

Chromatic Number:

Minimum number of colors required to properly color any

graph. In other words, the chromatic number can be described
as a minimum number of colors that are needed to color any
graph in such a way that no two adjacent vertices of a graph will
be assigned the same color.
The minimum number of colors of this graph is 3
chromatic number = 3
 Branch and Bound
The Branch and Bound Algorithm is a method used in combinatorial optimization
problems to systematically search for the best solution. It works by dividing the problem
into smaller subproblems, or branches, and then eliminating certain branches based on
bounds on the optimal solution. This process continues until the best solution is found or
all branches have been explored. Branch and Bound is commonly used in problems like
the traveling salesman and job scheduling.

Parameter Backtracking Branch and Bound

Backtracking is used to find all

Branch-and-Bound is used to solve
possible solutions available to a
optimisation problems. When it
problem. When it realises that it
realises that it already has a better
has made a bad choice, it undoes
Approach optimal solution that the pre-solution
the last choice by backing it up. It
leads to, it abandons that pre-solution.
searches the state space tree until
It completely searches the state space
it has found a solution for the
tree to get optimal solution.
problem.

Backtracking traverses the state

Branch-and-Bound traverse the tree
Traversal space tree by DFS(Depth First
in any manner, DFS or BFS.
Search) manner.

 For each node - associated bound, which gives the best value of the objective function on
any solution that can be obtained from this node
 Value of the best solution seen so far - best solution is usually initialized to +α
(minimization problems) or -α (maximization problems)
 Working principle
 If node’s bound is poorer than value of best solution – discard node
 Best First Search – chooses most promising node – node with best bound value

Algorithm Branch_and_Bound
E  new(node) // Root acts as dummy start node
H – Heap // can be min heap or max heap
Soln  -/ + // Value of best solution
while (true) do
if (E is a final leaf) then
Update Soln value (if better)
Print path from E to root
else Expand(E)
if (H is empty) then
if (soln = -/ +)
report ‘no solution’; return
E  delete (H) // Identifies best node among live nodes
If E’s cost is not better than Soln then return // Non-promising node
return
Algorithm Expand(E)
// Generates all children of E and adds them to the heap
Generate all children of E
Discard infeasible nodes
Compute approximate cost value of each child
Insert child into heap H

Assignment Problem using Branch and Bound

Let there be N workers and N jobs. Any worker can be assigned to perform any
job, incurring some cost that may vary depending on the work-job assignment. It is
required to perform all jobs by assigning exactly one worker to each job and exactly one
job to each agent in such a way that the total cost of the assignment is minimized.

Finding Optimal Solution using Branch and Bound

The selection rule for the next node in BFS and DFS is “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 optimal solution can often be speeded by
using an “intelligent” ranking function, also called an approximate cost function to avoid
searching in sub-trees that do not contain an optimal solution. It is similar to BFS-like
search but with one major optimization. Instead of following FIFO order, we choose a live
node with least cost. We may not get optimal solution by following node with least
promising cost, but it will provide very good chance of getting the search to an answer
node quickly.

There are two approaches to calculate the cost function:

For each worker, we choose job with minimum cost from list of unassigned jobs (take
minimum entry from each row).
For each job, we choose a worker with lowest cost for that job from list of unassigned
workers (take minimum entry from each column).

J1 J2 J3 J4
9 2 7 8 Person a
C= 6 4 3 7 Person b
5 8 1 8 Person c
7 6 9 4 Person d
The time complexity of a branch and bound algorithm for an assignment problem is often
measured as (O(bd)), where (b) is the branching factor and (d) is the solution's depth

Traveling Salesman Problem using Branch and Bound

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.

For example, consider the above graph. A TSP tour in the graph is 0-1-3-2-0. The cost of
the tour is 10+25+30+15 which is 80.

Example:
Given: Distance matrix for n cities
Aim: To find minimum cost tour involving all cities
Technique: Branch and Bound technique with a reasonable lower bound
For each city i find the sum of the distances from city i to the nearest two cities
Digraphs - one least cost incoming edge and a least cost outgoing edge are identified.
Sum this for all n cities and divide the result by 2. lb =[s/2].
City Lowest cost edges Cost
a ac, ab 1, 3
b ba, bc 3, 6
c ca, ce 1, 2
d dc, de 4, 3
e ec, ed 2, 3

lb = ((1+3) + (3+6) + (1+2) + (4+3) + (2+3))/2 = 14

Assumptions given:
City a is the starting city
A solution tour must visit city b first and then city c
Time Complexity: The worst case complexity of Branch and Bound remains same as that
of the Brute Force clearly because in worst case, we may never get a chance to prune a
node. Whereas, in practice it performs very well depending on the different instance of
the TSP. The complexity also depends on the choice of the bounding function as they are
the ones deciding how many nodes to be pruned.
0/1 Knapsack using Branch and Bound
Given two arrays v[] and w[] that represent values and weights associated with n
items respectively. Find out the maximum value subset(Maximum Profit) of v[] such that
the sum of the weights of this subset is smaller than or equal to Knapsack capacity W.

Note: The constraint here is we can either put an item completely into the bag or cannot
put it at all [It is not possible to put a part of an item into the bag.

Input: N = 3, W = 4, v[] = {1, 2, 3}, w[] = {4, 5, 1}

Output: 3
Explanation: There are two items which have weight less than or equal to 4. If we select
the item with weight 4, the possible profit is 1. And if we select the item with weight 1,
the possible profit is 3. So the maximum possible profit is 3. Note that we cannot put both
the items with weight 4 and 1 together as the capacity of the bag is 4.

Let us now discuss how we can apply the branch-and-bound technique to solving
the knapsack problem. Given n items of known weights wi and values vi, i = 1, 2, . . . , n,
and a knapsack of capacity W, find the most valuable subset of the items that fit in the
knapsack. It is convenient to order the items of a given instance in descending order by
their value-to-weight ratios.

Then the first item gives the best payoff per weight unit and the last one gives the
worst payoff per weight unit, with ties resolved arbitrarily:

v1/w1 ≥ v2/w2 ≥ ... ≥ vn/wn — (1)

Each node on the ith level of this tree, 0 ≤ i ≤ n, represents all the subsets of n
items that include a particular selection made from the first i ordered items.

This particular selection is uniquely determined by the path from the root to the node.
A branch going to the left indicates the inclusion of the next item, and a branch going to
the right indicates its exclusion.
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 payoff among the remaining items, which is vi+1/wi+1:
ub = v + (W − w)(vi+1/wi+1) — (2)

As a specific example, let us apply the branch-and-bound algorithm to the same instance
of the knapsack problem we solved above by exhaustive search.
At the root of the state-space tree no items have been selected as yet. Hence, both the
total weight of the items already selected w and their total value v are equal to 0. The
value of the upper bound computed by formula (2) is $100.

The above picture displays the State-space tree of the best-first branch-and-bound
algorithm for the instance of the knapsack problem.

Node 1, the left child of the root, represents the subsets that include item 1.
The total weight and value of the items already included are 4 and $40, respectively; the
value of the upper bound is 40 + (10 − 4) ∗ 6 = $76.
Node 2 represents the subsets that do not include item 1.
Accordingly, w = 0, v = $0, and ub =0+ (10 − 0) ∗ 6 = $60. Since node 1 has a larger upper
bound than the upper bound of node 2, it is more promising for this maximization
problem, and we branch from node 1 first.
Its children – nodes 3 and 4, represent subsets with item 1 and with and without item 2,
respectively.
Since the total weight w of every subset represented by node 3 exceeds the knapsack’s
capacity, node 3 can be terminated immediately.

Time Complexity: O(2N)

Auxiliary Space: O(N)

Branch and bound is very useful technique for searching a solution but in worst case, we
need to fully calculate the entire tree. At best, we only need to fully calculate one path
through the tree and prune the rest of it.