Searching techniques Backtracking Branch and Bound Main issues How to organize the candidate solution space How to traverse unravel the candidate solution space Techniques for pruning the search Analysis of searching algorithm Examples n queens problem and subset sum problem General template Candidate solution space Candidate solutions can generally be represented as an n tuple x1 x2 xn In some representations and some problems the candidate solutions all have the same length n for otherse the candidate solutions have different lengths There should be a finite number of choices for each component of the ntuple One can visualize the candidate solution space as a tree or directed acyclic graph dag The size of the candidate solution space depends on the cleverness of your representation of solutions You need to make sure you include all optimal solutions At the same time you want to minimize the number of extraneous candidate solutions Criterion function P x1 x2 xn Candidate solutions must minimize maximize or satisfy some criterion function P Traversal algorithm Thinking of the space as a tree or dag we can use traditional graph traversal techniques such as DFS or BFS Backtracking is generally a DFS through this solution space A breadth first search is more appropriate if there is no upper bound on the size of a vector the solution space is potentially infinite We can also use pruning techniques to limit number of candidate solutions explored Use of such a pruning technique is typically referred to as branch andbound Must evaluate trade off between time spent on evaluating pruning condition with time saved by limiting search space 1 Example n Queens problem Input Positive integer n Task Place n queens on an n by n chessboard so that no 2 attack none are on same row column or diagonal or report that this is impossible Solve the n queens problems for n 1 2 3 n queens problem with n 4 Solution 1 Solution space Let xi represent the position of the ith queen for 1 i 4 There are 16 different squares number them from 1 to 16 Size of solution space is 164 216 Criterion function P P x1 x2 x3 x4 1 if and only if all 4 positions are in unique rows columns and diagonals Brute force traversal Pseudocode algorithm for i 1 i 16 i for j 1 j 16 j for k 1 k 16 k for l 1 l 16 l if P i j k l 1 print i j k l How can we improve upon this solution strategy We can reduce candidate search space in several ways Assume that x1 x2 x3 x4 removes some redundancies and prunes search space to 16 1820 4 We know each queen must be in a different row so assume that queen 1 is in row 1 queen 2 is in row 2 queen 3 is in row 3 and queen 4 is in row 4 giving 44 256 nodes to search We can prune impossible searches earlier by detecting column and or diagonal conflicts earlier If queens 1 and 2 are both in column 1 they already attack each other and thus we do not need to explore any further in this tree 2 Solution 2 using ordering constraint on xi Solution space Let xi represent the position of the ith queen for 1 i 4 Add constraint xi xi 1 Size of solution space is 16 1820 4 Criterion function P P x1 x2 x3 x4 1 if and only if all 4 positions are in unique rows columns and diagonals Brute force traversal Pseudocode algorithm for i 1 i 16 i for j i 1 j 16 j for k j 1 k 16 k for l k 1 l 16 l if P i j k l 1 print i j k l Solution 3 using one queen per row constraint Solution space Let xi represent the column of the ith queen for 1 i 4 Assumption that queen i is in row i Size of solution space is 44 256 Criterion function P P x1 x2 x3 x4 1 if and only if all 4 positions are in unique rows columns and diagonals Brute force traversal Pseudocode algorithm for i 1 i 4 i for j 1 j 4 j for k 1 k 4 k for l 1 l 4 l if P i j k l 1 print i j k l Solution 4 using one queen per row constraint and some pruning Solution space Let xi represent the column of the ith queen for 1 i 4 Assumption that queen i is in row i Size of solution space is 44 256 Criterion function P P x1 x2 x3 x4 1 if and only if all 4 positions are in unique rows columns and diagonals 3 Smarter traversal Detect conflicts before we have complete candidate solutions Types of conflicts Column conflicts two queens conflict if their xi values are identical Diag45 conflicts two queens i and j are on the same 45 degree diagonal if xi i xj j Diag135 conflicts two queens i and j are on the same 135 degree diagonal if xi i xj j Assuming the first i queens are compatible we check that the i 1st queen is compatible when adding it Pseudocode algorithm queens int k set col set diag45 set diag135 global array x 1 k contains choices so far col x i 1 i k diag45 x i i 1 i k diag45 x i i 1 i k if k 4 then write print x we have a complete solution else explore all k 1 extensions to the solution for j 1 j 4 j if j notin col and j notin diag45 and j notin diag135 j works with previous choices x k 1 j queens k 1 col union j diag45 union j k diag135 union j k n queens problem with n 8 If we use solution 1 we need to explore a 648 size solution space With solution 2 we cut this down to 64 8 4 426 165 368 With solution 3 we cut this down to 88 16 777 216 With pruning we cut the tree down to 2057 nodes If we need only one solution we find it after exploring 114 nodes n queens problem with n 12 With solution 3 we have a solution space of 1212 nodes With pruning we cut the tree down to 856 189 nodes The first solution is found after exploring 262 nodes 4 Example Subset sum problem Input Positive integer vector x of size n x1 x2 xn Integer M Task Find a subvector not necessarily contiguous such that the sum of the subvector is M Example x 11 13 24 7 M 31 Solutions 11 13 7 and 24 7 Alternate representations 1 2 4 and 3 4 Fixed length alternate representation 1 1 0 1 and 0 0 1 1 Solution 1 Solution space There are 2n possible solutions A solution has the form d1 dk where di di 1 and k n Solutions have variable length and correspond to …