module5_backtrackingnbranchnbound_2022.pdf

Backtracking
8 queen
Sum of subset
Graph Coloring
Branch and Bound
8 puzzle problem

1. Module 5
Backtracking & Branch and
Bound

2. The backtracking method
•For problems where no. of choices grow exponentially with problem size
•A given problem has a set of constraintsand possibly an objective function
•The solution optimizes an objective function, and/or is feasible.
•We can represent the solution space for the problem using a state space tree
–The rootof the tree represents 0 choices,
–Nodes at depth 1 represent first choice
–Nodes at depth 2 represent the second choice, etc.
–In this tree a pathfrom root to a leafrepresents a candidate solution
•Definition:We call a node nonpromisingif it cannot lead to a feasible (or
optimal) solution, otherwise it is promising
•Main idea:Backtracking consists of doing a DFSof the state space tree,
checking whether each node is promising and if the node is nonpromising
backtrackingto the node’s parent

3. Backtracking
•Forsomeproblems,theonlywaytosolveistocheckall
possibilities.
•Backtrackingisasystematicwaytogothroughallthepossible
configurationsofasearchspace.
•Many problems solved by backtracking satisfy a set of
constraintswhich may divided into two categories: explicit and
implicit.
Explicit constraintsare rules that restrict each to take on values only
from a given set
Implicit constraintsare rules which relate to each other. i
x i
x

4. Backtracking
•Find whether there is any feasible solution?DecisionProblem
•What is best solution? OptimizationProblem
•List all feasible solutions? EnumerationProblem

5. •Problem State is each node in the tree
•State Space is all possible paths from root to other nodes
•Solution State is all possible paths from root to solution
•Answer State satisfies implicit constraints
•A live nodeis a node which has been generated but whose all children
have not been generated.
•An E-node(i.e., expanding node) is a live node whose children are
currently being generated.
•A dead nodeis a generated node which is not to be expanded further or
all of whose children have been generated.
•Two ways to generate problem states:
•Breadth FirstGeneration (queue of live nodes)
•Depth FirstGeneration (stack of live nodes)
Generating Problem States

6. •Depth FirstGeneration (stack of live nodes)
•When a new child C of the current E-node R is generated, this child
becomes the new E-node.
•Then R will become the new E-node again when the subtree C has
been fully explored.
•Corresponds to a depth first search of the problem states.
Generating Problem States

7. •Breadth FirstGeneration (queue of live nodes)
•The E-node remains the E-node until it is dead.
•Bounding functionsare used in both to kill live nodes without generating all
of their children.
•At the end of the process, an answer node (or all answer nodes) are generated.
•The depth search generation method with bounding function is called
backtracking.
•The breadth first generation method is used in the branch-and-bound
method.
Generating Problem States

8. Improving Backtracking: Search Pruning
•Searchpruningwillhelpustoreducethesearchspaceandhencegeta
solutionfaster.
•Theideaistoavoidthosepathsthatmaynotleadtoasolutionasearly
aspossiblebyfindingcontradictionssothatwecanbacktrack
immediatelywithouttheneedtobuildahopelesssolutionvector.

9. Greedy vs Backtracking
•Method ofobtaining
optimumsolution,without
revising previously
generatedsolutions
•Statespacetreenotcreated
•Lessefficient
•Eg.Jobsequencingwith
deadlines,Optimalstorage
ontapes
•Method ofobtaining
optimumsolution,may
requirerevisionofpreviously
generatedsolutions
•Statespacetreecreated
•Efficienttoobtainoptimum
solution
•Eg.8Queenproblem,Sumof
subsetproblem

10. Applications of Backtracking
•8 Queen / n Queen Problem
•Sum of Subset problem
•Graph Coloring
•0/1 Knapsack

11. N Queens problem

12. Eight Queen Problem
•Attempts to place 8 queens on a chessboard in such a
way that no queen can attack any other.
•A queen can attack another queen if it exists in the same
row, column or diagonal as the queen.
•This problem can be solved by trying to place the first
queen, then the second queen so that it cannot attack the
first, and then the third so that it is not conflicting with
previously placed queens.
•The solution is a vector of length 8 (x
1, x
2, x
3, ... x
8)
x
icorresponds to the column where we should place the i
th
queen.
•The solution is to build a partial solution element by element until it is complete.
•We should backtrack in case we reach to a partial solution of length k, that we couldn't
expand any more.

13. Eight Queen Problem: Algorithm
putQueen(row)
{ for every position col on the same row
if position col is available
place the next queen in position col
if (row<8)
putQueen(row+1);
else success;
}
•Define an 8 by 8 array of 1s and 0s to represent the chessboard
•Note that the search space is very huge:
16,772, 216 (8
8
) possibilities.
•Is there a way to reduce search space?
Yes Search Pruning.

14. •Since each queen (1-8) must be on a different row, we can assume queen iis
on row i.
•All solutions to the 8-queens problem can be represented as an 8-tuple
where queen i is on column j.
•The explicit constraints are
•The implicit constraints are that no two ’s can be the same (as queens must
be on different columns) and no two queens can be on the same diagonal.
•This implies that all solutions are permutations of the 8-tuple (1,2,…,8),
and reduces the solution space from tuples to 8! tuples. 10,0 orxx
ii  ),...,,(
821 xxx .81},8,...,2,1{  iS
i 8
8 i
x
Eight Queen Problem

15. •Generalizing earlier discussion, solution space contains all n!permutations of (1,2,…,n).
•The tree below shows possible organization for n=4.
•Tree is called a permutation tree (nodes are numbered as indepth first search).
•Edges labeled by possible values of
•The solution spaceis all paths from the root node to a leaf node.
•There are 4!=24 leaf nodes in tree.
444239373331282623211715121075
1
1x 
2x 2 3 1 4
605855534947 6365
43413836323027252220161411964 595754524846 6264
40352924191383 565145 61
34182 502 3 4 2 3 1 4 1 1 2 3 4 2 3 4 2 3 4 2 3 4 2 3 4 3 4 3 4 1 2 3 4 1 2 3 4 1 2 3 4 1 2 4 1 2 3 2 1 2 3 2 1 3 1 2 1 2 1 1 1 i
x
Four Queen Problem

16. 3315
1
1x 
2x 2 1
321614119
2924191383
1822 3 4 2 1 2 3 4 3 3 4 3 1 
3
x 
4x
Backtracking on 4-queens problem
B
BB
B
B
B B
1
2
3
4

17. Backtracking Algorithm for n-Queens
problem
•Let represent where the i
th
queen is placed (in row i and
column on an n by n chessboard.
•Observe that two queens on the same diagonal that runs from “upper
left” to “lower right” have the same “row-column” value.
•Also two queens on the same diagonal from “upper right” to “lower
left” have the same “row+column” value),...,,(
21 n
xxx i
x

18. •Then two queens at (i,j) and (k,l) are on the same diagonal
•iff i-j=k-l or i+j=k+l
•iff i-k=j-l or j-l = k-i
•iff |j-l|=|i-k| .
•Algorithm PLACE(k,i) returns true if the k
th
queen can be placed in column i and
runs in O(k) time (see next slide)
•Using PLACE, the recursive version of the general backtracking method can be
used to give a precise solution to the n-queens problem
•Array x[ ] is global in the Algorithm invoked by NQUEENS(1, n).
Backtracking Algorithm for n-Queens
problem

19. bool Place(int k, int i)
// Returns true if a queen can be placed in kth row and ith column. Otherwise it returns false.
// x[]is a global array whose first (k-1) values have been set.
// abs(r)returns the absolute value of r.
{
for (int j = 1; j < k; j++)
if ((x[j] == i) // Two in the same column
|| (abs(x[j]-i) == abs(j-k))) // or in the same diagonal
return(false);
return(true);
}
void NQueens(int k, int n)
// Using backtracking, this procedure prints all possible placements of n queens on an n x n
// chessboard so that they are nonattacking
{
for (int i=1; i<=n; i++) {
if (Place(k, i)) {
x[k] = i; //if no conflict place queen
if (k==n) { for (int j=1;j<=n;j++) //dead end
cout << x[j] << ' '; cout << endl;//print board configuration
}
else NQueens(k+1, n); //try next queen next position
}
}
}
Backtracking Algorithm for n-Queens
problem
Complexity: n!
j
th
queen at x[j] and k
th
queen at i

20. TASK
•Solve problem on slide 16 as per algorithm on slide 19

21. Sum of Subset problem

22. Sum of Subset Problem
•Given positive numbers and m, find all subsets of ,
whose sum is m.
•If n=4, ={11, 13, 24, 7} and m=31, the desired solution sets
are (11, 13, 7)and (24, 7).
•If the solution vectors are given using the indices of the x
ivalues used, then
the solution vectors are (1,2,4) and (3,4).
•In general, all solutions are k-tuples with and different solutions
may have different values of k.
•The explicit constraintson the solution space are that each
•The implicit constraintsare that (so each item will occur
only once) and that the sum of the corresponding ’s be m. i
w ),...,,(
21 k
xxx nk1 }.,...,2,1{ nx
i ,1,
1 nixx
ii 
 },,,{
4321 wwww ,1, niw
i
 11
(1)
kn
i i i
i i k
wk w m
  
 mwkw
k
k
i
ii



 1
1
)2( hold)2(and)1(iff),...,,(
21 truexxxB
kk 
The boundary function used uses both of the preceding conditions:
Bounding function

23. •The next figure gives the tree that corresponds to this variable tuple formation.
•An edge from a level inode to a level i+1node represents a value for
•The solution space is all paths from the root node to any node in the tree.
•Possible paths include empty path, (1), (1,2), (1,2,3), (1,2,3,4), (1,2,4), (1,3,4), …
•The leftmost subtree gives all subsets containing , the next subtree gives all
subsets containing but not , etc..
ix 1w 2w 1w
16
1
1x 
2x 2 3 1 4
15141312
11109876
432 52 3 4 4 3 3 4 4 4 4 4 
3
x 
4x
Nodes are numbered as in breadth first search
First
Formulation

24. •Another formulation of this problem represents each solution by an n-tuple
with
•Here if is not chosen and if is chosen
•Given the earlier instance of (11,13,24,7) and m=31, the solutions (11,13,7) and
(24,7) are represented by (1,1,0,1) and (0,0,1,1).
•Here, all solutions have a fixed tuple size. The tree on next slide corresponds to this
formulation (nodes are numbered as in D-search).
•Edge from a level i node to a level i+1node is labeled with the value of
•All paths from the root to a leaf give solution space.
•The left subtree gives all subsets containing and the right subtree gives all subsets
not containing . ),...,,(
21 n
xxx .1},1,0{ nix
i  0
i
x i
w 1
ix i
w )10(orx
i 1w 1w
Sum of Subset Problem : Second Formulation

25. 981110151417162322252429283130
76131221202726
541918
32
1
1x 
2x 
3
x 
4x 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

26. Sum of subset Problem
i
1
i
2
i
3
yes no
0
0
0
0
2
2
2
6
6
12
8
4
4
10
6
yes
yes
no
no
no
nono
no
The sum of the included integers is stored at the node.
yes
yes
yesyes
State SpaceTree for n= 3 items
w1 = 2, w2 = 4, w3 = 6 and S= 6
Solutions:
{2,4} and {6}

27. A Depth First Search Solution
Pruned State Space Tree
0
0
0
3
3
3
7
712 8
4
4
9
5
3
4 4
0
0
0
5
50
0 0
06
13 7 -backtrack
1
2
3
4 5
6 7
8
109
11
12
15
14
13
Nodes numbered in “call” order
w1 = 3, w2 = 4, w3 = 5, w4 = 6;
S= 13

28. sumOfSubsets ( s,k,r ) //sum, index, remaining sum
//generate left child until s+w[k]≤m
if (s+w[k]=m)
write(x(1:k)) //subset found
else if (s+w[k]+w[k+1]] ≤ m)
sumOfSubsets ( s+w[k],k+1,r-w[k] )
//generate right child
if (s+r-w[k]≥ m) and (s+w[k+1]] ≤ m)
x[k]=0
sumOfSubsets ( s,k+1,r-w[k] )
Initial call sumOfSubsets(0, 0, )

n
i
i
w
1
Sum of subset Algorithm
Complexity: 2
n

29. Given n=6,M=30 and
W(1…6)=(5,10,12,13,15,18).
I
st
solution is A -> 1 1 0 0 1 0
II
nd
solution is B -> 1 0 1 1 0 0
III
rd
solution is C -> 0 0 1 0 0 1
15,5,33
0,1,73
5,2,68
15,3,58
27,4,46 15,4,46
5,3,58
17,4,46 5,4,4
0,2,68
10,3,587
10,4,46
0,3,58
C
A
B
5,5,33 10,5,33
20,6,18
X
i=1
X
i=0
X
i=1
X
i=0
X
i=0
X
i=1 X
i=0
X
i=1
X
i=0
X
i=0X
i=0X
i=1
X
i=1
X
i=1
X
i=1
X
i=1
X
i=0
X
i=0
X
i=0
B
27,5,33
B
27,6,18
B
B

30. TASK
•M=13 w={3,4,5,6}

31. GRAPH / MAP coloring
•Graph Coloring is an assignment of colors
•Proper Coloring is if no two adjacent vertices have the same color
•Optimization Problem
•Chromatic no: smallest no. of colors used to color graph
•The Four Color Theoremstates that any map on a plane can be
colored with no more than four colors, so that no two countries with a
common border are the same color

32. Origin of the problem
m-coloring decision problem: whether the graph can be colored or not
m-coloring optimization problem: min # of colors to color graph
chromatic problem
More than 1 possible solution

33. Algo
•Number out each vertex (V
0, V
1, V
2, … V
n-1)
•Number out the available colors (C
0, C
1, C
2, … C
m-1)
•Start assigning C
ito each V
i. While assigning the colors note that two
adjacent vertices should not be colored by the same color. And least
no. of colors should be used.
•While assigning the appropriate color, just backtrack and change the
color if two adjacent colors are getting the same.
Complexity: m
n

35. Applications of Graph Theory
•Computer N/W security (Minimum Vertex Cover)
•Timetabling Problem (Vertex Coloring of Bipartite MultiGraph)
•GSM Mobile Phone Networks (Map Coloring)
•Represent Natural Language Parsing Diagrams
•Pattern recognition
•Molecules in chemistry and physics

36. Branch and Bound
•Branch and bound is used to find optimal solutions to optimization
problems.
•Is applied where Greedy and Dynamic fail.
•Is indeed much slower. Might require exponential time in worst case.
•BnB uses state space tree where in all children of node generated
before expanding any of its child.

37. Backtracking vs Branch and Bound
•Follows DFS approach
•Solves DecisionProblems
•While finding solution, bad
choices can be made
•State space tree is searched until
solution is found
•Space required is O(ht. of tree)
•Applications: N Queens, Sum of
subset
•Follows DFS / BFS / Best First
Search approach
•Solves optimizationproblems
•Proceeds on a better solution, so
possibility of bad solution is
ruled out
•State space tree is searched
completely since solution can be
found elsewhere
•Space required is O(No. of
leaves)
•Applications: 15 puzzle, TSP

38. The Branch and Bound Steps
•In BnB, a state space tree is built and all children of E nodes (a live
nodewhose children are currently been generated) are generated
before any other node can become live node.
•For exploring new nodes either BFS(FIFO queue) or D-search(LIFO
stack) is used or replace the FIFO queue with a priority queue (least-
cost(or max priority)).
–The search for an answer node can often be speeded up using an
“intelligent” ranking function for the live nodes though it requires
additional computational effort.
•In this method, a space tree of possible solutions is generated. Then
partitioning (branching) is done at each node. LB and UB computed
at each node, leading to selection of answer node.
•Bounding functions (when LB>=UB) avoid generation of trees
(fathoming) not containing answer node.

39. •Abranch-and-boundalgorithmcomputesanumber(bound)atanode
todeterminewhetherthenodeispromising.
•Thenumberisaboundonthevalueofthesolutionthatcouldbe
obtainedbyexpandingbeyondthenode.
•Ifthatboundisnobetterthanthevalueofthebestsolutionfoundso
far,thenodeisnonpromising.Otherwise,itispromising.
•Besidesusingtheboundtodeterminewhetheranodeispromising,we
cancomparetheboundsofpromisingnodesandvisitthechildrenof
theonewiththebestbound.
•Thisapproachiscalledbest-firstsearchwithbranch-and-bound
pruning.Theimplementationofthisapproachisamodificationofthe
breadth-firstsearchwithbranch-and-boundpruning.
The Branch and Bound variants

40. Branch and Bound Algorithm
AlgorithmBnB()
E←new(node) //E is node pointer pointing root node
while(true)
if(E is a final leaf)
write(path from E to root)//E is optimal sol.
return
Expand(E)
if(H is empty)//H is heap for all live nodes
write(“there is no solution”)//E is optimal sol.
return
E← delete_top(H)
AlgorithmExpand(E)
Generate all children of E
Compute approximate cost value of each child
Insert each child into heap H

41. Least Cost search
•In BnB, basic idea is selection of E-node, so that we reach to answer
node quickly.
•Using FIFO and LIFO BnB selection of E-node is complicated (since
expansion of all live nodes required before leading to an answer) and
blind.
•Best First Search and D-search are special cases of LC-search.
•In LC-searchan intelligent ranking function (smallest c^(x)) is
formed. c
^
(x)=f(x)+ ĝ(x) (where f(x) is cost of reaching x from root,
ĝ(x) is an estimate of additional effort needed to reach an answer node
from x).
•LC-search terminates only when either an answer node is found or the
entire state space tree has been generated and searched.
•Note that termination is only guaranteed for finite space trees.

42. Applications of Branch and Bound
•8 Puzzle Problem
•Travelling Salesman Problem

43. 8 Puzzle problem using Branch and Bound

44. TASK
1 3 4 15 1 2 3 4
2 5 12 5 6 7 8
7 6 11 14 9 10 11 12
8 9 1013 131415
Initial Arrangement Goal Arrangement