Path Finding using a Greedy Algorithm
OverviewIn this week's project, you will be writing a code that is able to read any elevation data, and determine the "greedy" path to get from the west side of the map to the east side of the map (at a chosen north/south location). Let's look at an example, here is an elevation map:
The goal of this project is to choose a north/south starting point on the far west side of the map, and determine the "greedy" path that gets you to the far east side the map. Here is a sample solution:
The Greedy AlgorithmThe path is chosen by determining the "easiest" next step at any particular location. This is why it is called "greedy". A "greedy" algorithm is one in which, in the face of too many possible choices, you make a choice that seems best at that moment. Since our map is in a 2D grid, we can envision a "walk" as starting in some cell at the left-most edge of the map (column 1) and proceeding forward by taking a "step" into one of the 3 adjacent cells in the next column over (column 2). Our "greedy walk" will assume that you will choose the cell whose elevation is closest to the elevation of the cell you're standing in. (NOTE: this might mean walking uphill or downhill). See this sample grid below:
The diagrams below show a few scenarios for choosing where to take the next step. In the case of a tie with the forward (east) position, you should always choose to go straight forward (east). In the case of a tie between the two non-forward locations, you should go southeast. In other words:
AnimationThe starter code provides all the code necessary to create an animation fo the greedy algorithm finding the path. You are just filling in the algorithm part. Here is what your animation should look like for each of the three test cases:
Video of Simple gridVideo of 480 by 480 gridVideo of 844 by 480 gridPlease note:
- The animation will not play in Zybooks, but Zybooks will test your final path. Zybooks will time out if the soluiton takes a certain amount of time, so comment out the 'plot' and 'pause' lines of code before testing your code on Zybooks.
- For credit, you must change the colormap of the contour plot and the color of the path plotted over the top. Please use the help to figure out how to do this. This will not be tested here on Zybooks.
How to get Started
- Download the starter code and the three .dat files (). Place them on your computer in the same folder. Open the starter code in MATLAB.
- Run the code. As is, it should run the sample test case. You should see this:
Sample Animation Starter Code.
- If you comment out Case 1, and uncomment Case 2 or Case 3, you should see a simple solution but with different contour maps.
- Write the code that finds the greedy path. Path attention to all comments labelled "TO DO". And do them in order. Work incrementally and test frequently. If you don't want to follow the TODO order, that is fine, it is just a recommendation.