DAA-backtracking and branch and bound.ppt

DAA-backtracking and branch and bound.ppt

1. BACK TRACKING
&
BRANCH AND BOUND
ALGORITHM

2. BACK TRACKING ALGORITHM
•Finds all(or some) solutions to some computational problems, notably
constraint satisfaction problem.
•Incrementally builds candidates to the solutions, and abandons a
candidate (“backtracks”) as soon as it determines the candidate will not
lead to a valid solution.
•Can be applied only for problems which admit the concept of a “partial
candidate solution” and a relatively quick test for completeness to a
valid solution.
•Based on Depth First Recursive Search.

3. PICTORIAL EXPLANATION :
Invalid
solution
(Backtrack)
Invalid
solution
(Backtrack)
Invalid
solution
(Backtrack)
Sol 1
Optimal
value1
Sol 2
Optimal
value2
Sol 3
Optimal
value3
A
B
1
B
2
C1 C2 C3 C1 C2

4. PSEUDO CODE:
boolean pathFound(Position p){
if(p is finish) return true; for each option O from p
{
Boolean isThereAPath= pathFound(O);
if(isThereAPath)
return true;
}
return false;
}

5. EXAMPLE : N QUEEN PUZZLE
•PROBLEM DESCRIPTION: In a N X N square Board , place N
queens so that no two queens threaten each other(Non Attacking
Position).
•Let N=4
So, on 4X4 board we have to place 4 queens
Q3
Q1
Q4
Q2

6. SOLUTIONBY BACKTRACKING :
Q1 X X X
Q1 X
Q1 X
Q1 X
Q1 X X X
Q1 X X
Q1 Q2 X X
Q1 Q2 X X
Q1 X X X
Q1 X X
Q1 Q2 X
Q1 Q2 X X
Step 1for
Q1
Step 2 for
Q2
No Place for
Q3 hence
backtrack to
other
positon of
Q2
Q1 X X X
Q1 X Q3 X
Q1 Q2 X X
Q1 Q2 X X
No Place for Q4
hence
backtrack to
other positon of
Q3->Q2->Q1
Step 4 for
Q3
Step 3 for next position
of Q2

7. CONTINUE..
Q1 X
Q1 X X X
Q1 X
Q1 X
Q1 X X
Q1 X X X
Q1 X X
Q1 Q2 X X
Q1 X Q3 X
Q1 X X X
Q1 X X
Q1 Q2 X X
Q1 X Q3 X
Q1 X X X
Q1 X X Q4
Q1 Q2 X X
Reache
d
Solutio
n

Step 5 for another position
of Q1
Step 6 for
Q2
Step 7 for
Q3
Step 8 for
Q4

8. WHY BACKTRACKING :
•Whenever applicable, Backtracking is often much faster than
brute force enumeration of all complete candidates, since it
eliminates a large no of candidates with a single test.
•Simple and easy to code
•Different states are stored into stack so that data can be
useful anytime.

9. BRANCH AND BOUND ALGORITHM
•Algorithm consist of a systematic enumeration of candidate
solutions by means of state space search (in which successive
states are considered with the intention of finding goal state
with desired property).
•Before enumerating the candidate solution of a branch, the branch
is checked against upper(lower) bounds on the optimal
solution, and discard if it cannot produce a better solution than the
best one found so far.
•Based on Breadth First Search

10. PSEUDO CODE:
//maximizing an arbitrary objective function f
//requires bounding function g
1.Let B be the best possible value achieved. Initialize B <- 0;
2.Initialize a priority queue to hold a partial solution with none
of variables of the problem assigned
3.Loop until the queue is empty:
1.take a node N (with highest bound value) from the queue.
2.if N represent a single candidate solution x and f(x)>B
then x is the best solution. Set B=f(x).
3.else branch on N to produce new nodes N
i . For each of
these:
1.if g(N
i) < B . Discard it.
2.else store N
ion the queue.

11. PICTORIALEXPLANATION:
b=0
U=5
5
b=16
U=3
5
b=40
U=5
5
b=40
U=4
0
b=40
U=4
0
b=16
U=5
5
b=0
U=3
0
1
2
3
Not
feasible
Not
feasible
4 Killed as
U<B
Killed as
U<B
6
5
Solution with optimal
value 40
B= 016 40

12. EXAMPLE : TRAVELLING SALESMAN
PROBLEM
1
34
2
10
9
6
10
•PROBLEM DISCRIPTION : Given a set of cities and distance
between every pair of cities, the problem is to find the shortest
possible tour that the salesman must take to visit every city
exactly once and return to the starting point.
solution

13. SOLUTION BY BRANCH AND BOUND :
Compute weight
matrix :
Lets compute the reduced matrix which provide the
shortest
distance from the matrix
Let Start with City 1 . Calculation of Reduced Cost
for node 1
1 234
min
1 ∞1015
2010
2 5∞9
105
3 613∞
126
4 889
∞
8
29
1 23
4
1 ∞0
5
10
2 0
∞ 45
3 07
∞6
4 00
1
∞
min 00
15
29+6
2
3
4
1
∞
0
4
5
2
0
∞
3
0
3
0
7
∞
1
4
0
0
0
∞
1
Reduced cost
=35
1 23
4
1 ∞
10 15
20
2 5∞
9
10
3 6
13 ∞
12
4 88
9∞

14. CONTINUE..
4
C=40
6
C=35
7
C=35
2
C=35
4
3
3
C=
40
2
3
5
C
=3
9
4
3
2
3
4
1
∞
0
4
5
2
0
∞
3
0
3
0
7
∞
1
4
0
0
0
∞
1 1
mi
n-
0
4
12
3
1
2
3
4
mi
n
234
∞∞∞
∞
∞∞3
0
0
0∞∞
10
0∞0
∞0
000
0
C(node 2)= W[1][2]+ C(Node 1) + Reduce cost
= 35
mi
n
1
1
2
∞
∞
∞
∞
∞
∞
∞
∞
-
-
1
2
∞
∞
∞
∞
∞
∞
∞
∞
3
4
∞
0
∞
∞
∞
∞
1
∞
1
0
3
4
∞
0
∞
∞
∞
∞
0
∞
4
12
3
Similarly we calculate C for
node 3,
4 and put them in priority
queue
C(node 5)= W[2][3]+ C(Node 2) + Reduce cost = 3+35+1=39
Similarly we calculate C for node 6 and put them in queue
After node 7, we found out the nodes in queue are having C > MinCost so we kill
them.
MinCost
=35
1
1
C=3
5

15. WHY BRANCH AND BOUND ?
•Anenhancement of backtracking
•Determine the bound as tight as possible
•Doesn’t try all possible combinations and hence reach the
solution fast.
•Solve some problems which are not solvable by Dynamic
programming.

16. 0/1 KNAPSACK PROBLEM
PROBLEM DESCRIPTION: Given weight and values of N items, put
these items in a Knapsack of capacity C to get the maximum total
value in the Knapsack. You cannot break an item, either pick the
complete or don’t pick it (0-1 property)
Complexity : Brute Force O(2
N)
Dynamic Programming O(NC)
Note: Dynamic can solve the problem with integer weights only.

17. EXAMPLE :
Item no. Weight (in
Kg)
Value (in Rs)
1 1 40
2 3 100
3 4 60
4 2 20
Capacity=
5kg

18. NAÏVE METHOD :
•Trying out all the possible combination (2
4) and compute the profit over feasible solution and return
the solution with max
profit.
•Psuedo Code :
for i = 1 to 2
n do j=n
tempWeight =0
tempValue =0
while ( A[j] != 0 and j > 0)
A[j]=0
j=j – 1
A[j] =1
for k =1 to n do
if (A[k] = 1) then tempWeight =tempWeight + Weights[k] tempValue =tempValue + Values[k]
if ((tempValue > bestValue) AND (tempWeight <=Capacity)) then bestValue =tempValue
bestWeight =tempWeight bestChoice =A
return bestChoice

19. BACKTRACKING
V=0
W=0
V=20
W=2
V=60
W=4
kille
d
W=6
V=40
W=1
V=60
W=3
V=100
W=5
kille
d
W=7
V=140
W=4
kille
d
W=6
V=40
W=1
V=60
W=4
V=100
W=3
V=40
W=1
V=100
W=5
kille
d
W=9
V=0
W=0
V=140
W=4
V=40
W=1
V=0
W=0
V=0
W=0
V=100
W=3
X
4=1X
4=0X
4=1
V=140
W=4
X
4=0X
4=1
X
3=0X
3=1
X
2=1
1X =1
X
3=0
X
3=1X
3=0X
3=1 X
3=0X
3=1
V=0
W=0
X
4=0
X
4=1X
4=0X
4=1
X
4=0
V=100
W=3
killed
W=7
X
4=1
V=120
W=5
2X =0
X
2=1
X
1=0
2X =0
X
4=0
Item
no.
Weig
ht (in
Kg)
Value
(in
Rs)
1 1 40
2 3 100
3 4 60
4 2 20
Capacity=
5kg

20. PSEUDO CODE:
void knapsack(level,value,weight){
if(level<n){
l=level; level=level+1; if(weight+w[l]<=c){
v2= value+v[l]; w2=weight+w[l]; if(v2>maxValue){
maxValue=v2; maxWeight=w2;
}
knapsack(level,v2,w2);
}
else{
//"next level node killed"
}
knapsack(level,value,weight);
}
}

21. BRANCH AND BOUND :
V=0
W=0
B=15
5
V=140
W=4
B=150
kille
d
W=8
V=40
W=1
B=15
5
Item
no.
Weig
ht (in
Kg)
Value
(in
Rs)
1 1 40
2 3 100
3 4 60
4 2 20
Capacity=
5kg
MaxValue=
140
V=0 W=0
B=130
B<MaxVa
lue
killed
X
4=0
V=140
W=4
B=140
X
4=1
kille
d
W=
6
3X =0
3X =1
X
2=1
V=1
40
W=
4
B=1
55
X
1=1 X
1=0
X
2=0
V=40 W=1
B=100
B<MaxValue
killed

22. PSEUDO CODE:
//assumption: items are arranged in non increasing order of their profit by weight ratio priority_queue<Node> Q;
Node N1,N2; N1.level=0; N1.value=0; N1.weight=0;
N1.bound=boundCal(N1.level,N1.value,N1.weight); Q.push(N1);
while(!Q.empty())
N1=Q.top();
Q.pop(); if(N1.level<=n)
l=N1.level; if(N1.weight+w[l]<=c)
N2.level=N1.level+1;
N2.weight=N1.weight+w[l]; N2.value=N1.value+v[l]; N2.bound=boundCal(N2.level,N2.value,N2.weight);
if(N2.value>maxValue)
maxValue=N2.value; maxWeight=N2.weight;
Q.push(N2);

23. PSEUDO CODE: CONTINUE..
N2.level=N1.level+1; N2.weight=N1.weight;
N2.value=N1.value;
N2.bound=boundCal(N2.level,N2.value,N2.weight);
if(N2.bound>=maxValue)
Q.push(N2);
boundCal(level,value,weight)
upperbound= value;
for(i=level;i<n;i++)
if(weight+w[level]<=c)
weight+=w[level]; upperbound+=v[level];
else
w2=c-weight;
upperbound+=w2*v[level]/w[level]; break;
return upperbound;