Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Shortest Path3-29-2010Opening Discussion●Do you have any questions about the quiz?●Do you have any questions about recursion before we begin?Week's Objective●Our goal for the week is to make it so that an actor can walk from any location in a maze to any other location taking the shortest path.●For today our goal is simply to write a method that will tell us how long the shortest path is from one place to another.The Approach●This problem can be solved without recursion, but it is challenging. So instead we will design a recursive solution.●Recursive solutions are basically built from two things. I want us to think about them.–Base cases: Under what conditions can you easily give an answer? What is the answer in those cases?–Recursive case: how could you get the shortest path if you knew it from other locations?Preventing Cycles●One of the things we have to do is prevent our algorithm from running in circles. We don't want it to keep going over the same location again and again.●To do this and to make it easy for us to look up the locations of walls, we will pass in an extra argument to the recursive function that is a 2-D array of ints. (int[][])Wrapping the Recursion●Because of this 2-D array, it will can't call the method directly. Instead, we need to have another method that we call that will build the array and then call the recursive method.●This type of “wrapping” is a common technique when additional information is needed in a method that the original caller might have a hard time putting together.Writing the Code●Let's write our method and try it out.Minute Essay●The method we made today checks all paths through the maze. Is it clear how it does that? What could be some problems with doing
View Full Document
Unlocking...