Techniques for Dealing with Hard ProblemsBacktrackBacktrack Example: Non-Attacking QueensSlide 5“Domino” PhenomenonEstimating Backtrack EfficiencyEstimating Backtrack Efficiency: Monte CarloMonte Carlo Example: Case 1Slide 10Monte Carlo Example: Case 2Monte Carlo Example: Case 3Monte Carlo ExampleSlide 14Branch-and-Bound (B&B)Branch-and-Bound Example: Game TreeGame Tree Example – “NIM”Game Tree ExampleSlide 19Game Tree Example (before pruning)Game Tree Example (after pruning)SPARE SLIDESBacktrack example: 3-coloringTechniques 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 queenA 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 non-attacking queens.Backtrack Example: Non-Attacking Queens13 4 4 1432411 23 223“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 falseNote: 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 advanceEstimating 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 X2 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 1X1=1X2=4X3=2Thus, we have 1 + 4 + 4*2 + 4*2 = 21 nodesMonte Carlo Example: Case 2•Case 2: X1=1, X2=3X1=1X2=3We would conclude that there are 13 nodes.Monte Carlo Example: Case 3•Case 3: X1=2, X2=4, X3=1, X4=3X2=4X1=2X3=1X4=3We could imagine the decision tree has 17 nodes.Monte Carlo Example• The real decision tree 13 4 4 1432411 23 223Monte 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 nodesBranch-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 timeBranch-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 game1st player wants to maximize payoff (Call her Max)2nd player wants to minimize payoff (Call her Min)Game Tree Example•Basic IdeaUse both upper and lower cut-off values in a game tree T UQR S•If the value of a Max son is , then  is a lower cut-off value on the value of Max•If Max has a lower cut-off value , then all Max’s children have lower cut-off value Game Tree Example•If the value of a Min son is , then  is a upper cut-off value on the value of Min.•If Min has a upper cut-off value , then all Min’s children have upper cut-off value .QR S    T UGame Tree Example (before pruning)2 -221 876-3543-311 -3 2 -44 -3 6 -2 -51 4-3 61 -31ABCD EFGHKJIML NGame Tree Example (after pruning)2 -221 311 1 2 -4-21 2-21 -2ABCD EFGHKJIML N111111111111-22SPARE SLIDESBacktrack example: 3-coloringAlgorithm 3-coloring (G, var U);Input: G = (V,E) (an undirected graph). Let U = set of vertices that have already been colored together with