Techniques for Dealing with Hard Problems Backtrack Systematically enumerates all potential solutions by continually trying to extend a partial solution component by component starting from null At each stage of the search if an extension of the current partial solution is not possible we backtrack to a shorter partial solution and try again with a different choice for extension Branch and Bound A special case of backtrack with costs Key point Most problems have special structures so we don t end up trying all possible solutions Backtrack Set up a 1 1 correspondence between configurations and possible solution sequences or partial solution vectors Decision Tree The root corresponds to the initial state of the problem usually is null means no decision is made and each branch corresponds to a decision concerning one parameter Backtrack Example Non Attacking Queens Put N queens on an N x N chessboard such that no queen attacks another queen A queen in chess can attack any square on the same row column or diagonal Given an n x n chessboard we seek to place n queens onto squares of the chessboard such that no queen attacks another queen The example shows a placement red squares of four mutually nonattacking queens Backtrack Example Non Attacking Queens 1 3 2 3 4 4 4 1 1 2 1 4 3 3 2 2 Domino Phenomenon Suppose the solution is represented by a vector Then a partial solution could be represented by a partial vector Once we find a partial vector that does not satisfy the solution requirements there is no point in extending the partial vector into a more complete solution Domino phenomenon Pk false Pk 1 false Note Domino phenomenon must be true for backtrack to work Estimating Backtrack Efficiency Backtrack is usually exponential in the worst case but performs much better on average One way to estimate count nodes in decision tree unrealistic nodes for the 4 queens problem is 1 4 4 4 4 4 4 4 4 4 4 341 Alternative way only count nodes of feasible choices But we don t know the feasible choices at each node in advance Estimating Backtrack Efficiency Monte Carlo To estimate the number of nodes in a decision tree can use the Monte Carlo approach Monte Carlo approach Traverse the decision tree selecting among feasible choices randomly at each node When a computation path is completed assume that all the computation paths those we did not travel are exactly the same as the one path we chose randomly Monte Carlo Example Case 1 To illustrate the Monte Carlo approach again use the 4 4 chessboard Case 1 Assume that X1 is chosen randomly to be 1 from 4 possible values 1 2 3 4 and X 2 is chosen randomly to be 4 from two possible values 3 4 then X3 is set to be 2 since it is the only choice So what will the decision tree look like according to the Monte Carlo approach Monte Carlo Example Case 1 X1 1 X2 4 X3 2 Thus we have 1 4 4 2 4 2 21 nodes Monte Carlo Example Case 2 Case 2 X1 1 X2 3 X1 1 X2 3 We would conclude that there are 13 nodes Monte Carlo Example Case 3 Case 3 X1 2 X2 4 X3 1 X4 3 X1 2 X2 4 X3 1 X4 3 We could imagine the decision tree has 17 nodes Monte Carlo Example The real decision tree 1 3 2 3 4 4 4 1 1 2 1 4 3 3 2 2 Monte Carlo Example The real decision tree has 17 nodes Suppose we got Case 1 twice Case 2 once and Case 3 once Then we could have estimated the nodes in decision tree to be 2 21 1 13 1 17 4 18 This is actually close to the real answer of 17 nodes Branch and Bound B B Special variation of backtrack Associate a cost with a partial solution such that the cost of a parent is always less than or equal to the cost of its child in the decision tree do not branch from an internal node whose cost is higher than the current bound cost of the minimum cost complete solution found so far the bound is updated if a better solution is found Key points Used for optimization problems Cost driven Bounding prunes the decision tree saves time Branch and Bound Example Game Tree In games e g chess can model the different stages of the game by a rooted tree Don t need to consider all possible situations of a game Can predict the outcome of the game using the concept of branch and bound Questions Who is the winner if both players play optimally How much is the payoff Initially we only know the payoff of the terminal nodes end states of the game Game Tree Example NIM NIM Two players alternately take chips from a given pile Each player must take at least one chip and at most three chips in his turn The winner is the player who empties the pile The amount of payoff is the number of chips the winner takes in his last turn Way to think about it payoff amount the 1st player receives at the end of game 1st player wants to maximize payoff Call her Max 2nd player wants to minimize payoff Call her Min Game Tree Example Basic Idea Use both upper and lower cut off values in a game tree Q If the value of a Max son is then is a lower cut off value on the value of Max R S T U If Max has a lower cut off value then all Max s children have lower cut off value Game Tree Example Q If the value of a Min son is then is a upper cut off value on the value of Min R S T U If Min has a upper cut off value then all Min s children have upper cut off value Game Tree Example before pruning A 1 B 3 I 1 C 1 E 3 1 1 1 3 H G 2 3 4 2 6 M 3 4 D 2 J F 4 K 3 5 2 3 L 4 N 6 6 7 2 8 5 Game Tree Example after pruning 1 B 1 1 C 1 1 E G 1 2 1 1 1 1 1 J F 2 2 1 D 2 A 1 3 2 1 H 1 2 I 2 K L 2 4 1 1 1 2 M 2 N SPARE SLIDES Backtrack example 3 coloring Algorithm 3 coloring G var U Input G V E an undirected graph Let U set of vertices that have already been colored together with their colors U is initially empty Output An assignment of one of three colors to each vertex of G Begin if U V then print coloring is completed return else pick a vertex v not in U for C 1 to 3 do if no neighbor of v is colored with color C then add v …