0:00
[MUSIC]
This video is the project overview for week three.
Extending and improving graph search.
Specifically, where gonna be doing shortest path on a weighing graph.
There's two key parts to this assignment.
The first is Dijkstra's algorithm, and the second is aStarSearch.
Now again, both of these methods are gonna find us the shortest path in
the weighing graph.
A store search will just do so a little more quickly than Dijkstra search does.
You're gonna be working with the same code as you did in week two.
And we're working with MapGraph.java in the roadmap package.
And you may find that you have to revise more than just MapGraph.java.
You may have to modify some of your other classes within your class organization in
order to support these methods.
And we'll talk about those details in just a little bit.
0:46
If you weren't entirely happy with your week two solution.
You can feel free to use our week two solution as a starting point for
week three.
But I do encourage you to use your own code.
As it's likely that you'll be more comfortable with your own code.
So again, you're gonna be authoring two main search methods
that we've learned about this week.
The first, again, is dijkstra.
The second is aStarSearch.
Both these methods take a start point and a goal point.
And your goal is to find the shortest path from the start to the goal.
1:31
For testing purposes you may want to just use the dijkstra,
the aStarSearch that don't require this consumer object.
You can just call these methods.
And we'll create that main consumer object,
and then we'll call your Appropriate method.
You don't need to modify these methods.
These are just useful for the testing.
Your first step is gonna be authoring Dijkstra's algorithm.
Now this shouldn't be too bad.
You'll be able to use your breadth first method from week two as a starting point.
And you can use the pseudocode from the videos from this week.
The biggest changes that you'll need to make for
this week are actually modifying your MapGraph
class along with your support classes to be able to facilitate this search.
2:06
Specifically, right at the start of Dijkstra's algorithm we say initialize
the distance to each of the vertices or nodes to positive infinity.
And that essentially allows us to keep track of a current distance from my start
node to each of the nodes.
It's likely that within your class structure,
you didn't keep some kind of distance like this associated with each of the nodes.
Now whether or not what you wanna add a current distance to the nodes, or
you wanna make a wrapper class to store that there, or you want some entire other
data structure to keep those current distances is all up to you.
You'll just need to keep track again of this distance
from the start node to the vertex as your algorithm progresses.
So, the second piece is this is likely your first time working with
a priority queue.
And when you insert items into a priority queue.
You need to have some ordering of their priorities.
In this case, you're gonna be using the distance from their start node to
prioritize them.
And with a shorter distance being a higher priority than a longer distance.
In order to do this, whatever element you're inserting into the PriorityQueue.
And this element's likely gonna store both the node itself as well as the distance to
that node.
Needs to implement the interface comparable.
And to implement the interface comparable you need to author the compareTo method.
You can look at the javadocs for Comparable for more details.
3:21
If you want to use the visualization tool in the provided GUI just as we did
our project overview video.
You're gonna need to report removal of nodes from the queue to
this consumer object.
And you're gonna do so by using the accept method.
And that takes a geographic point.
So for example you may have, you may call the except method on your node search.
Then pass it, geographic point.
Where you're assuming here that next is the element that you just removed from
the priority queue.
And that the getLocation gets you that geographic point associated with the node
that you just removed.
Next step, just like with all other methods in this course.
You're gonna wanna test your code.
So after you've coded Dijkstra.
I encourage you to try a number of simple test cases.
Let's look at the example that we just looked at from week two for breadth for
search, and figure out what should Dijkstra return back as the shortest path.
In this example, the first search found us the shortest path by visiting
the fewest number of vertices.
Breadth for search found us the path from 1,1 to 8,-1 by
going through 4,1, then 7,3, and then to The 8, -1.
But this actually isn't the shortest path.
So we hope Djikstra will actually do is find the shortest path and
the shortest path here should be from 1,1 to 4,1 to 5,1 to 6.5, 0 to 8,-1.
Now that we have a good idea of what it should do.
Let's look at how we would do this with our code.
In order to test Dijkstra on this example.
We've provided you simpletest.map as a data file,
which contains this exact example.
What you could do is run Dijkstra on this.
And it should find the same shortest path as we just worked through.
I encourage you to try some additional test cases to check to make sure
that your algorithm is actually working properly.
Your next step in the project is going to be authoring AStarSearch.
So your gonna always look back at the videos from this week for
the pseudo-code for AStarSearch.
And you'll likely will use your Dijkstra method from this week as a starting point.
Now there are some critical changes to be made going from Dijkstra to AStarSearch.
But again, much of the work that you're gonna need to do for
this part of the project is in changing around your classes
to you'll support now the storage of two distance values, not just one.
You'll still need to maintain the actual distance from the start.
Just as you did with Djikstra.
But you'll also need to keep a predicted distance,
which is the actual distance to the node.
5:52
As a hint, be sure when you start your algorithm to initialize both your
actual and your predicted values to positive infinity.
And it set both of those values to be zero for the start node.
Just like we did with Dijkstra.
If you wanna use the visualization tool,
you'll again want to use this accept method on the consumer object.
But we want to test AStarSearch in two ways.
The first is that we wanna make sure that AStarSearch returns the same
answer as Dijkstra.
So it should be finding the same shortest path.
6:24
The biggest distance between AStarSearch and Dijkstra is the number of nodes
that get visited on the path to finding your solution.
So you could look at the previous example.
What you see in our previous example is a Dijkstra diagram's actually gonna visit
all the nodes in this graph in the process of trying to find it's path from 1,1 to
8,-1.
AStarSearch is gonna do this much more efficiently.
It's gonna find the path from 1,1 to 8,
-1 by only exploring nodes in fact on the shortest path.
In order to test this, you can use the simpletest.map file in the data folder.
Run Djikstra on it and look at the nodes it visited.
It should visit essentially these nine nodes in this order.
You can run then AStarSearch on it,
and it should visit these five nodes in this order.
You might be asking, well how do I know which nodes are being visited?
And the best way to do that is to just print out nodes as they get visited
to help with the bugging.
And then you'll want to comment out whatever that print is
before you start running it on larger examples.
7:25
I encourage you to run your code, not only in this example, but in others to see if
AStarSearch is in fact finding a shorter path by visiting fewer nodes.
In fact, one of the best parts of this assignment is running this in the GUI.
And you'll see Dijkstra exploring tons of nodes in the path and
finding the shortest path from one location to another.
Whereas AStarSearch does such a more efficient job,
looking at only the nodes on a reasonable path from the start to the goal.
Once you're happy with your code for both Dijkstra and AStarSearch.
You're gonna submit your code just as you did with week two with
zipping all the files in the roadgraph package into one zipfile called mod3.zip.
And then you're gonna go, just like we did with previous assignments.
You're gonna go to My submission, you're gonna create a new submission.
And you're gonna submit your zip file and
you'll get feedback about how well it performs.
You can always look at the feedback from the graders to see what went wrong.
And you can always look at the graders themselves in our source code
to see what tasks are being performed.
>> There is one last piece to this assignment, and the quiz it's coming up.
We will ask you to provide the number of nodes that are visited, using Djikstras
algorithim, as well as using aStarSearch out of them on one of our test cases.