Backtracking & branch and bound

Algorithms

1. BACK TRACKING
&
BRANCH AND BOUND
ALGORITHM
SUBMITTED BY: SUBMITTED TO:
VIPUL CHAUHAN DR. SUMITKALRA
M18CSE005 ASSISTANT PROFESSOR
IIT JODHPUR

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
B1 B2
C1 C2 C3 C1 C2

4. PSEUDO CODE:
booleanpathFound(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. SOLUTION BY 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 Q3Step 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
Reached
Solution

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
i on the queue.

11. PICTORIAL EXPLANATION:
b=0
U=55
b=16
U=35
b=40
U=55
b=40
U=40
b=40
U=40
b=16
U=55
b=0
U=30
1
2
3
Not feasible
Not feasible
4 Killed as U<B
Killed as U<B
6
5
Solution with optimal value 40
B=01640

12. EXAMPLE : TRAVELLING SALESMAN
PROBLEM
•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.
1
34
2
10
9
6
10
solution

13. SOLUTION BY BRANCH AND BOUND :
Compute weight matrix :
∞101520
5∞910
613∞12
889∞
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
∞101520
5∞910
613∞12
889∞
min
8
6
5
10
4321
4
3
2
1
∞0510
0∞45
07∞6
001∞
29
min0 510
4
3
2
1
4321
29+6
=35
∞045
0∞30
07∞1
000∞4
3
2
1
4321
Reduced cost
4321
4
3
2
1

14. CONTINUE.. 1
C=35
3
C=40
4
C=40
6
C=35
5
C=39
7
C=35
2
C=35
4
32
3 4
3
∞045
0∞30
07∞1
000∞4
3
2
1
4321
∞∞∞∞
∞∞30
0∞∞1
0∞0∞4
3
2
1
4321
min
0
0
0
-
0
∞∞∞∞
∞∞∞∞
∞∞∞1
0∞∞∞4
3
2
1
4321
min0 000
C(node 2)= W[1][2]+ C(Node 1) + Reduce cost = 35
min
0
1
-
-
1
∞∞∞∞
∞∞∞∞
∞∞∞0
0∞∞∞4
3
2
1
4321
C(node 5)= W[2][3]+ C(Node 2) + Reduce cost = 3+35+1=39
Similarly we calculate C for node 3,
4 and put them in priority queue
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 > MinCostso we kill them.
MinCost=35
1

15. WHY BRANCH AND BOUND ?
•An enhancement 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.
•PsuedoCode :
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. PROGRAM AND EXECUTION:
Click to Code Click to execute program

20. BACKTRACKING
V=0
W=0
V=20
W=2
V=60
W=4
killed
W=6
V=100
W=3
V=120
W=5
V=40
W=1
V=60
W=3
V=100
W=5
killed
W=7
V=140
W=4
killed
W=6
V=40
W=1
V=60
W=4
V=100
W=3
killed
W=7
V=40
W=1
V=100
W=5
V=140
W=4
killed
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
V=0
W=0
X
4=1X
4=0X
4=1X
4=0X
4=1
X
3=0X
3=1
X
2=1
X
1=1
X
3=0
X
3=1X
3=0X
3=1 X
3=0X
3=1
X
4=0
X
4=1X
4=0X
4=1
X
4=0
X
4=1
X
2=0
X
2=1
X
1=0
X
2=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

21. 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);
}
}

22. PROGRAM AND EXECUTION:
Click to code Click to execute program

23. BRANCH AND BOUND :
V=0
W=0
B=155
killed
W=6
V=140
W=4
B=150
killed
W=8
V=140
W=4
B=155
V=40
W=1
B=155
V=40
W=1
B=100
V=140
W=4
B=140
V=0
W=0
B=130
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
B<MaxValue
killed
B<MaxValue
killed
X
4=0X
4=1
X
3=0X
3=1
X
2=1
X
1=1 X
1=0
X
2=0

24. 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);

25. 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;

26. PROGRAM AND EXECUTION:
Click to code Click to execute program

27. REFERENCES :
•https://www.wikipedia.org
•https://www.geeksforgeeks.org/
•https://www.youtube.com/
•Thomas H. Cormen