KLS, Gogte Institute of Technology
Department of Computer Science and Engineering
Design & Analysis of Algorithms – Unit 5
By, Veena V Kangralkar
CSE@GIT
Asst. Prof. Dept of CSE
KLS GIT, Belagavi-08
Department of Computer Science and Engineering, GIT
Contents
• Branch and Bound
Assignment Problem
Travelling Sales Person Problem
Knapsack Problem
• String Matching Algorithm
Rabin – Karp Algorithm
Department of Computer Science and Engineering, GIT 1
Branch and Bound-(B & B)
Standard Terminologies of optimization problems
• Feasible Solution
• Optimal Solution
Compared to Backtracking B & B requires 2 items:
• A bound on the best value of the objective function.(lower bound
for Min, Upper bound-Max problems)
• The value of the best solution seen so far
Terminating Conditions in a State space tree of B & B
Algorithm
• Value of node’s bound is not better than the value of best solution seen so far
• Node represents no feasible solution because constraints are already violated
• Subset of feasible solutions represented by the node consists of single point-we
compare value of objective function for feasible solution with that of best
solution seen so far and update latter with former if new solution is better
Department of Computer Science and Engineering, GIT 2
Assignment Problem
Concept: Illustrating the branch and bound approach by applying it to the
problem of assigning n people to n jobs so that the total cost of the
assignment is as small as possible.
Consider a NXN matrix C
Job 1 Job 2 Job 3 Job 4
C= 9 2 7 8 Person a
6 4 3 7 Person b
5 8 1 8 Person c
7 6 9 4 Person d
Lower bound here will be calculated by taking the sum of smallest elements from
each matrix’s row : lb = 2+3+1+4=10
Department of Computer Science and Engineering, GIT 3
J1 J2 J3 J4 a->1=lb= 9+3+1+4=17
9 2 7 8
J1 J2 J3 J4
6 4 3 7
a->2=lb=2+3+1+4=10
5 8 1 8 9 2 7 8
7 6 9 4 6 4 3 7 person a has been given job 2
5 8 1 8
7 6 9 4
J1 J2 J3 J4 a->3=lb=7+4+5+4=20
9 2 7 8 J1 J2 J3 J4
6 4 3 7 a->4=lb=8+3+1+6=18
9 2 7 8
5 8 1 8
6 4 3 7
7 6 9 4
5 8 1 8
7 6 9 4
Department of Computer Science and Engineering, GIT 4
J1 J2 J3 J4
b->1=lb=2+6+1+4=13
9 2 7 8 person b has been given job 1
6 4 3 7
J1 J2 J3 J4
5 8 1 8
7 6 9 4 9 2 7 8 b->3=lb=2+3+5+4=14
6 4 3 7
5 8 1 8
7 6 9 4
J1 J2 J3 J4
9 2 7 8 b->4=lb=2+7+1+7=17
6 4 3 7
5 8 1 8
7 6 9 4
Department of Computer Science and Engineering, GIT 5
J1 J2 J3 J4 c->3=lb=2+6+1+4=13
9 2 7 8
d->4=lb=2+6+1+4=13 Cost =13
6 4 3 7 person c has been given job 3
5 8 1 8
7 6 9 4
J1 J2 J3 J4 c->4=lb=2+6+8+9=25
d->3=lb=2+6+8+9=25
9 2 7 8
6 4 3 7 Cost = 25
5 8 1 8 person d has been given job 4
7 6 9 4
Department of Computer Science and
6
Engineering, GIT
Live Leaves: Promising nodes that may produce optimal solution
Best-first-branch and bound : selecting the best fit (option)
Solution: start
lb=10
1 3 4
2
a->1 a->2 a->3 a->4
lb=17 lb=10 lb=20 lb=18
X X X
5 6 7
b->1 b->3 b->4
lb=13 lb=14 lb=17
8 9 X X
c->3 c->4
d->4 d->3
Cost=13 Cost=25
Solution Inferior Sol 7
Department of Computer Science and Engineering, GIT
Knapsack Problem
Maximization Problem : so calculate upper bound (ub)
ub= v+(W-w)(vi+1/wi+1) = 0+(10-0)(10)=100
Where v=Total value of the item already selected
W=maximum capacity
w=Total weight of the item selected so far
vi+1 & wi+1 = Individual item value & weight
Consider the problem Item Weight Value Value/
W=10 Weight
Note : 1 4 $40 10
Items have been rearranged 2 7 $42 6
w.r.t Value/weight ratios 3 5 $25 5
4 3 $12 4
WDepartment of Computer Science and Engineering, GIT 8
0
W=0, v=0
ub=100
1
2
W=4, v=40
W=0, v=0
ub=76
ub=60
3 4 X inferior node to 8
W=11 W=4, v=40
X - NF ub=70
5 6
W=9, v=65 W=4, v=40
ub=69 ub=64
7 8
W=12 W=9, v=65
X - NF ub=65
Optimal Solution
X not feasible Department of Computer Science and Engineering, GIT 9
Exercise
Item Weight Profit
1 5 $40
2 7 $35
W=15
3 2 $18
4 4 $4
5 5 $10
6 1 $2
Department of Computer Science and Engineering, GIT 10
Travelling Salesperson problem
Consider the graph below
3
a b
8 5 6 9
1 7
4
c d
V Min Edge
2 3
a 1+3=4
lb= s/2 e
b 3+6=9
lb= [ (1+3)+(3+6)+(1+2)+(3+4)+(2+3)]/2 = 14 c 1+2=3
Here we consider 2 minimum cost edges from every vertice d 3+4=7
e 2+3=5
Department of Computer Science and Engineering, GIT 11
0
a
lb=14
1 2 3 4
a, b a,c a, d a, e
lb=14 X lb=16 lb=19
X X
5 6 7
a, b, c a, b, d a, b, e
lb=16 lb=16 lb=19
X
8 9 10 11
a, b, c, d a, b, c, e a, b, d, c a, b, d, e
(e, a) (d, a) (e, a) (c, a)
l=24 l=19 l=24 l=16
1st Tour Better Tour Inferior Tour Optimal Tour
Department of Computer Science and Engineering, GIT 12
Contd…
1- (a, b)=[(1+3)+(3+6)+(1+2)+(3+4)+(2+3)]/2 =14
2-(a,c)= since b is not before c we do not explore this path
3- (a, d)= [(1+5)+(3+6)+(1+2)+(5+3)+(2+3)]/2 =16
4-(a, e) = [(1+8)+(3+6)+(1+2)+(3+4)+(8+2)]/2 =19
5- (a, b, c)= [(1+3)+(3+6)+(6+1)+(3+4)+(2+3)]/2 =16
6-(a, b, d) = [(1+3)+(3+7)+(1+2)+(7+3)+(2+3)]/2 =16
7-(a, b, e) = [(1+3)+(3+9)+(1+2)+(3+4)+(9+3)]/2 =19
Complete path calculation:
8-(a, b, c, d, (e, a))= 3+6+4+3+8 = 24
9- (a, b, c, e, (d, a))= 3+6+2+3+5= 19
10- (a, b, d, c, (e, a))= 3+7+4+2+8=24
11- (a, b, d, e, (c, a))= 3+7+3+2+1= 16-optimal tour…
Department of Computer Science and Engineering, GIT 13
Exercise
Consider the graph below
2
10 a b
A B
2
10 5 3
5
17 8 7
D C c d
11 1
Department of Computer Science and Engineering, GIT 14
Rabin Karp String Matching Algorithm
Definition:
A string search algorithm which compares a
string's hash values, rather than the strings
themselves. For efficiency, the hash value of
the next position in the text is easily
computed from the hash value of the current
position.
Department of Computer Science and
16
Engineering, GIT
Working
Let characters in both arrays T and P be digits in
radix-Σ notation. (Σ = (0,1,...,9)
Let p be the value of the characters in P
Choose a prime number q such that fits within a
computer word to speed computations.
Compute (p mod q)
The value of p mod q is what we will be using to find all
matches of the pattern P in T.(solved example refer notes)
Department of Computer Science and
17
Engineering, GIT
THANK YOU
Department of Computer Science and Engineering, GIT 14