Backtracking.ppt

1、Backtracking,What is backtracking?General structure of Backtracking algorithmsBacktracking and Recursion,Backtracking,Problem:Find out all 3-bit binary numbers for which the sum of the 1s is greater than or equal to 2.The only way to solve this problem is to check all the possibilities: (000, 001, 0

2、10, ,111)The 8 possibilities are called the search space of the problem. They can be organized into a tree.,Backtracking: Illustration,Backtracking,For some problems, the only way to solve is to check all possibilities.Backtracking is a systematic way to go through all the possible configurations of

3、 a search space.We assume our solution is a vector (a(1),a(2), a(3), a(n) where each element a(i) is selected from a finite ordered set S.,Backtracking,We build a partial solution v = (a(1), a(2),., a(k), extend it and test it.If the partial solution is still a candidate solution, proceed. elsedelet

4、e a(k) and try another possible choice for a(k).If possible choices of a(k) are exhausted, backtrack and try the next choice for a(k-1).,Backtracking: Iterative Version,Compute S(1) ,k = 1 While (k 0) do While S(k) != emptySet do (*advance*) a(k) = an element in S(k)S(k)= S(k)- a(k)if ( a(1),a(2),.,

5、a(k) is a solution, print itk = k + 1 Compute S(k)Compute , the candidate k-th element given v. k = k - 1 (*backtrack*),Backtracking: Recursive Version,Backtrack(a, k) if a is a solutionprint(a) else k = k +1 compute S(k)while do S(k)!=emptySeta(k) = an element in S(k)S(k)=S(k)-a(k) ,Backtracking an

6、d Recursion,Backtracking is easily implemented with recursion because:The run-time stack takes care of keeping track of the choices that got us to a given point.Upon failure we can get to the previous choice simply by returning a failure code from the recursive call.,Improving Backtracking: Search P

7、runing,Search pruning will help us to reduce the search space and hence get a solution faster.The idea is to a void those paths that may not lead to a solutions as early as possible by finding contradictions so that we can backtrack immediately without the need to build a hopeless solution vector.,E

8、ight 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, colum or diagonal as the queen.This problem can be solved by trying to place the first queen, then the second queen so that it

9、 cannot attack the first, and then the third so that it is not conflicting with previously placed queens.,Eight Queen Problem,The solution is a vector of length 8 (a(1), a(2), a(3), , a(8).a(i) corresponds to the column where we should place the i-th queen.The solution is to build a partial solution

10、 element by element until it is complete.We should backtrack in case we reach to a partial solution of length k, that we couldnt expand any more.,Eight Queen Problem: Algorithm,putQueen(row) for every position col on the same rowif position col is availableplace the next queen in position colif (row

11、8)putQueen(row+1);else success;remove the queen from position col ,Eight Queen Problem: Implementation,Define an 8 by 8 array of 1s and 0s to represent the chessboardThe array is initialized to 1s, and when a queen is put in a position (c,r), boardrc is set to zeroNote that the search space is very

12、huge: 16,772, 216 possibilities.Is there a way to reduce search space? Yes Search Pruning.,Eight Queen Problem: Implementation,We know that for queens:each row will have exactly one queeneach column will have exactly one queeneach diagonal will have at most one queenThis will help us to model the ch

13、essboard not as a 2-D array, but as a set of rows, columns and diagonals.To simplify the presentation, we will study for smaller chessboard, 4 by 4,Implementing the Chessboard,First: we need to define an array to store the location of so far placed queens,PositionInRow,Implementing the Chessboard Co

14、ntd,We need an array to keep track of the availability status of the column when we assign queens.,Suppose that we have placed two queens,Implementing the Chessboard Contd,We have 7 left diagonals, we want to keep track of available diagonals after the so far allocated queens,Implementing the Chessboard Contd,We have 7 left diagonals, we want to keep track of available diagonals after the so far allocated queens,Backtracking,The putQueen Recursive Method,static void putQueen(int row)for (int col=0;colsquares;col+)if (columncol=available ,