Navigation by searching a graph (part 2) [20 points]
The goal of this assignment is to develop your own program to run graph
searching algorithms. The program needs to use a graph representing a 2D map
of some area, consisting of nodes, corresponding to places on the map, and
edges, corresponding to roads connecting the map places. The places will have
specific 2D spatial coordinates, and the edges will have costs, corresponding
to travel distances between the places.
Your first task will be to locate a library of AI graph searching procedures
for the programming language of your choice. Then write a program to use this
library to allow the user to find the shortest (or any, depending on the graph
searching algorithm selected by the user) path between the selected starting
point and destination, and dispay this path as a sequence of places.
Do not worry about a fancy user interface. The simple sequence of questions
(start, destination, search algorithm) is perfectly sufficient.
You can create a graph using some program (even the AISpace graph searching
applet), or you can create it with a text editor. All the connections should
have distances specified going each way. Make sure your grah is not too small
or trivial, so that you can make meaningful searches on it. Approximately 20
nodes, with at least several paths connecting most of the nodes should provide
a rich enough environment to test searching algorithms.
Also, think about some way to provide a heuristic for the navigation. A simple and useful heuristic can be obtained by measuring the geometric distance between two nodes. But in order to be able to use it, your graph nodes would have to have geometric coordinates.