CompSci 100e7.1The Power of Recursion: Brute force! Consider the TypingJob APT problemn: What is minimumnumber of minutes needed to type n term papers given pagecounts and three typists typing one page/minute? (assignpapers to typists to minimize minutes to completion)! Example: {3, 3, 3 ,5 ,9 ,10 ,10} as page counts! How can we solve this in general? Suppose we're told thatthere are no more than 10 papers on a given day.! How does this constraint help us?! What is complexity of using brute-force?CompSci 100e7.2Backtracking, Search, Heuristics! Many problems require an approach similar to solving a maze! Certain mazes can be solved using the “right-hand” rule! Other mazes, e.g., with islands, require another approach! If you have “markers”, leave them at intersections, don’texplore the same place twice! What happens if you try to search the web, using links onpages to explore other links, using those links to …! How many web pages are there?! What rules to webcrawlers/webspiders follow?• Who enforces the rules?! Keep track of where you’ve been don’t go there again! Any problems with this approach?CompSci 100e7.3Backtracking with Boggle! Boggletm played on 4x4 board! Other sizes possible! Form words by connecting lettershorizontally, vertically, diagonally! Cannot re-use letters (normally)! Two approaches! Build words from connections, findpartial words in dictionary! Look up every word in thedictionary on the board! Which is better? How is backtrackingused?CompSci 100e7.4Classic problem: N queens! Can queens be placed on a chessboard so that no queens attackeach other?! Easily place two queens! What about 8 queens?! Make the board NxN, this is theN queens problem! Place one queen/column! # different tries/column?! Backtracking! Use “current” row in a col! If ok, try next col! If fail, back-up, next rowCompSci 100e7.5Backtracking idea with N queens! Try to place a queen in each column in turn! Try first row in column C, if ok, move onto next column! If solved, great, otherwise try next row in column C, placequeen, move onto the next column• Must unplace the placed queen to keep going! What happens when we start in a column, where to start?! If we fail, move back to previous column (whichremembers where it is/failed)! When starting in a column anew, start at beginning• When backing up, try next location, not beginning! Backtracking in general, record an attempt go forward! If going forward fails, undo the record and backupCompSci 100e7.6Basic ideas in backtracking search! We need to be able to enumerate all possible choices/moves! We try these choices in order, committing to a choice! If the choice doesn’t pan out we must undo the choice• This is the backtracking step, choices must be undoable! Process is inherently recursive, so we need to know when thesearch finishes! When all columns tried in N queens! When all board locations tried in boggle! When every possible moved tried in Tic-tac-toe or chess?• Is there a difference between these games?! Summary: enumerate choices, try a choice, undo a choice, thisis brute force search: try everythingCompSci 100e7.7Computer v. Human in Games! Computers can explore a largesearch space of moves quickly! How many moves possible inchess, for example?! Computers cannot explore everymove (why) so must use heuristics! Rules of thumb about position,strategy, board evaluation! Try a move, undo it and tryanother, track the best move! What do humans do well in thesegames? What about computers?! What about at Duke?CompSci 100e7.8Backtracking, minimax, game search! We’ll use tic-tac-toe to illustrate the idea, but it’s a silly gameto show the power of the method! What games might be better? Problems?! Minimax idea: two players, one maximizes score, the otherminimizes score, search complete/partial game tree for bestpossible move! In tic-tac-toe we can search until the end-of-the game, butthis isn’t possible in general, why not?! Use static board evaluation functions instead of searchingall the way until the game ends! Minimax leads to alpha-beta search, then to other rules andheuristicsCompSci 100e7.9Minimax for tic-tac-toe! Players alternate, one might becomputer, one human (or twocomputer players)! Simple rules: win scores +10,loss scores –10, tie is zero! X maximizes, O minimizes! Assume opponent plays smart! What happens otherwise?! As game tree is explored isthere redundant search?! What can we do about this?XOXXOXXOXXXOXOXOXOXOXOXOXXOXOCompSci 100e7.10Recasting the problem! Instead of writing this function, write another and call it// @return min minutes to type papers in pagesint bestTime(int[] pages){}! What cases do we consider in function below?int best(int[] pages, int index, int t1, int t2, int t3)// returns min minutes to type papers in pages// starting with index-th paper and given// minutes assigned to typists, t1, t2, t3{}return best(pages,0,0,0,0);CompSci 100e7.11Loop Invariants! Want to reason about the correctness of a proposed iterativesolution! Loop invariants provide a means to effectively about thecorrectness of codewhile !done do // what is true at every step // Update/iterate // maintain invariantodCompSci 100e7.12Bean Can game! Can contains N black beans and M white beans initially! Emptied according the following repeated process! Select two beans from the can! If the beans are:• same color: put a black bean back in the can• different colors: put a white bean back in the can! Player who chooses the color of the remaining bean winsthe game! Analyze the link between the initial state and the final state! Identify a property that is preserved as beans are removedfrom the can! Invariant that characterizes the removal processCompSci 100e7.13Bean Can Algorithmwhile (num-beans-in-can > 1) do pick 2 beans randomly if bean1-color == bean2-color then put-back black bean else put-back white beanodCompSci 100e7.14Bean Can Analysis! What happens each turn?! Number of beans in can is decreased by one! Number of white beans is either reduced by 2 or 0! Number of black beans is either reduced by 1 or 0! Examine the final states for 2 bean and 3 bean initial states! Any guesses for the correct strategy?! What is the process invariant?CompSci 100e7.15The Game of Nim! Two Piles of counters with N and M counters in each pile! 2 players take turns:! Remove some number of counters (! 1) from one pile! Player who removes last counter wins! Properties! Complete information: could exhaustively
View Full Document
Unlocking...