DOC PREVIEW
Penn CIT 594 - Backtracking

This preview shows page 1-2-19-20 out of 20 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 20 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

BacktrackingSlide 2Solving a mazeColoring a mapSolving a puzzleBacktracking (animation)Terminology ITerminology IIReal and virtual treesThe backtracking algorithmFull example: Map coloringData structuresCreating the mapSetting the initial colorsThe main programThe backtracking methodChecking if a color can be usedPrinting the resultsRecapThe EndBacktracking2BacktrackingSuppose you have to make a series of decisi ons, among various choices, whereYou don’t have enough information to know what to chooseEach decision leads to a new set of choicesSome sequence of choices (possibly more than one) may be a solution to your problemBacktracking is a methodical way of trying out various sequences of decisions, until you find one that “works”3Solving a mazeGiven a maze, find a path from start to finishAt each intersection, you have to decide between three or fewer choices:Go straightGo leftGo rightYou don’t have enough information to choose correctlyEach choice leads to another set of choicesOne or more sequences of choices may (or may not) lead to a solutionMany types of maze problem can be solved with backtracking4Coloring a mapYou wish to color a map withnot more than four colorsred, yellow, green, blueAdjacent countries must be indifferent colorsYou don’t have enough information to choose colorsEach choice leads to another set of choicesOne or more sequences of choices may (or may not) lead to a solutionMany coloring problems can be solved with backtracking5Solving a puzzleIn this puzzle, all holes but oneare filled with white pegsYou can jump over one pegwith anotherJumped pegs are removedThe object is to remove allbut the last pegYou don’t have enough information to jump correctlyEach choice leads to another set of choicesOne or more sequences of choices may (or may not) lead to a solutionMany kinds of puzzle can be solved with backtracking6Backtracking (animation)start ??dead enddead end??dead enddead end?success!dead end7Terminology IThere are three kinds of nodes:A tree is composed of nodesThe (one) root nodeInternal nodesLeaf nodesBacktracki ng can be thought of as searching a tree for a particular “goal” leaf node8Terminology IIEach non-leaf node in a tree is a parent of one or more other nodes (its children)Each node in the tree, other than the root, has exactly one parentparentchildrenparentchildrenUsually, however, we draw our trees downward, with the root at the top9Real and virtual treesThere is a type of data structure called a treeBut we are not using it hereIf we diagram the sequence of choices we make, the diagram looks like a treeIn fact, we did just this a couple of slides agoOur backtracking algorithm “sweeps out a tree” in “problem space”10The backtracking algorithmBacktracking is really quite simple--we “explore” each node, as follows:To “explore” node N: 1. If N is a goal node, return “success” 2. If N is a leaf node, return “failure” 3. For each child C of N, 3.1. Explore C 3.1.1. If C was successful, return “success” 4. Return “failure”11Full example: Map coloringThe Four Color Theorem states that any map on a plane can be colored with no more than four colors, so that no two countries with a common border are the same colorFor most maps, finding a legal coloring is easyFor some maps, it can be fairly difficult to find a legal coloringWe will develop a complete Java program to solve this problem12Data structuresWe need a data structure that is easy to work with, and supports:Setting a color for each countryFor each country, finding all adjacent countriesWe can do this with two arraysAn array of “colors”, where countryColor[i] is the color of the ith countryA ragged array of adjacent countries, where map[i][j] is the jth country adjacent to country iExample: map[5][3]==8 means the 3th country adjacent to country 5 is country 813Creating the map0 142365int map[][];void createMap() { map = new int[7][]; map[0] = new int[] { 1, 4, 2, 5 }; map[1] = new int[] { 0, 4, 6, 5 }; map[2] = new int[] { 0, 4, 3, 6, 5 }; map[3] = new int[] { 2, 4, 6 }; map[4] = new int[] { 0, 1, 6, 3, 2 }; map[5] = new int[] { 2, 6, 1, 0 }; map[6] = new int[] { 2, 3, 4, 1, 5 };}14Setting the initial colorsstatic final int NONE = 0;static final int RED = 1;static final int YELLOW = 2;static final int GREEN = 3;static final int BLUE = 4;int mapColors[] = { NONE, NONE, NONE, NONE, NONE, NONE, NONE };15The main program (The name of the enclosing class is ColoredMap) public static void main(String args[]) { ColoredMap m = new ColoredMap(); m.createMap(); boolean result = m.explore(0, RED); System.out.println(result); m.printMap(); }16The backtracking method boolean explore(int country, int color) { if (country >= map.length) return true; if (okToColor(country, color)) { mapColors[country] = color; for (int i = RED; i <= BLUE; i++) { if (explore(country + 1, i)) return true; } } return false; }17Checking if a color can be used boolean okToColor(int country, int color) { for (int i = 0; i < map[country].length; i++) { int ithAdjCountry = map[country][i]; if (mapColors[ithAdjCountry] == color) { return false; } } return true; }18Printing the results void printMap() { for (int i = 0; i < mapColors.length; i++) { System.out.print("map[" + i + "] is "); switch (mapColors[i]) { case NONE: System.out.println("none"); break; case RED: System.out.println("red"); break; case YELLOW: System.out.println("yellow"); break; case GREEN: System.out.println("green"); break; case BLUE: System.out.println("blue"); break; } }}19RecapWe went through all the countries recursively, starting with country zeroAt each country we had to decide a colorIt had to be different from all adjacent countriesIf we could not find a legal color, we reported failureIf we could find a color, we used it and recurred with the next countryIf we ran out of countries (colored them all), we reported successWhen we returned from the topmost call, we were done20The


View Full Document

Penn CIT 594 - Backtracking

Documents in this Course
Trees

Trees

17 pages

Searching

Searching

24 pages

Pruning

Pruning

11 pages

Arrays

Arrays

17 pages

Stacks

Stacks

30 pages

Recursion

Recursion

25 pages

Hashing

Hashing

24 pages

Recursion

Recursion

24 pages

Graphs

Graphs

25 pages

Storage

Storage

37 pages

Trees

Trees

21 pages

Arrays

Arrays

24 pages

Hashing

Hashing

24 pages

Recursion

Recursion

25 pages

Graphs

Graphs

23 pages

Graphs

Graphs

25 pages

Stacks

Stacks

25 pages

Recursion

Recursion

25 pages

Quicksort

Quicksort

21 pages

Quicksort

Quicksort

21 pages

Graphs

Graphs

25 pages

Recursion

Recursion

25 pages

Searching

Searching

24 pages

Counting

Counting

20 pages

HTML

HTML

18 pages

Recursion

Recursion

24 pages

Pruning

Pruning

11 pages

Graphs

Graphs

25 pages

Load more
Download Backtracking
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Backtracking and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Backtracking 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?