CPS 1007.1Towers of Hanoiÿ Move disks from “from”pegto“to”pegÿWhat is the recurrence relation in terms of numDisks?void Move(int from, int to, int aux, int numDisks)// pre: numDisks on peg from,// post: numDisks moved to peg to{if (numDisks == 1){cout<<from<<"to"<<to<<endl;}else{Move(from, aux, to, numDisks-1);Move(from, to, aux, 1);Move(aux, to, from, numDisks-1);}}CPS 1007.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 t here again Any problems with this approach?CPS 1007.3Classic 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?ÿ N Queens Demo Applet!ÿ Backtracking Use “current” row in a col If ok, try next col If fail, back-up, next rowCPS 1007.4Backtracking 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 u p, try next location, not beginningÿ Backtracking in general, record an attempt go forward If going forward fails, undo the record and backupCPS 1007.5Basic 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 we have found the exit in a maze When every possible moved tried in Tic-tac-toe or chess?• Is there a difference b etween these games?ÿ Summary: enumerate choices, try a choice, undo a choice, thisis brute force search: try everythingCPS 1007.6N queens backtracking: nqueens.cppbool Queens::SolveAtCol(int col)// pre: queens placed at columns 0,1,...,col-1// post: returns true if queen can be placed in column col// and N queen problem solved (N is square board size){int k; int rows = myBoard.numrows();if (col == rows) return true;for(k=0; k < rows; k++){ if (NoQueensAttackingAt(k,col)){ myBoard[k][col] = true; // place a queenif (SolveAtCol(col+1)){ return true;}myBoard[k][col] = false; // unplace the queen}}return false;}CPS 1007.7Computer v. Human in Gamesÿ Computers can explore a largesearch space of moves quickly How many moves p ossible 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?CPS 1007.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 andheuristicsCPS 1007.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?XOXXOXXOXXXOXOXOXOXOXOXOXXOXOCPS 1007.10yfzhltea byveqyeÿ The words above represent a simple substitution cypher Each letter mapped to one other letter, no inconsistencies Often used in cryptogram puzzles (newspaper, online, …) How can we write a computer program to solve this?ÿ Ideas for solving the problem? Benchmark/ballpark idea toaccept (or not)ÿProblems on the horizon?CPS 1007.11One possible solution in docrypto.cppÿ Study this for an example of backtracking Similar to N queens: make move, recurse, undo as needed What’s a move in this problem?ÿ IllustratesafewC++andOOconcepts Static variables and functions: belong to class not object Also called “class variables”, don’t need object to access Must be careful when initializing static variables becauseorder of initialization can be importantÿ See WordSource object shared by all CryptoMap objects,how a nd when is the WordSource initialized?CPS 1007.12Heuristicsÿ A heuristic is a rule of thumb, doesn’t always work, isn’tguaranteed to work, but useful in many/most cases Search problems that are “big” often can be approximatedor solved with the right heuristicsÿ What heuristic is good for cryptograms? Solve small words first Solve large words first Do something else?ÿ What other optimizations/improvements can we make? See program, cryptomap.cpp and
View Full Document
Unlocking...