Due date: Thursday, February 14, 2008.

Ex. 1 Download the file graph_path.py. Add the following things to it:

a. Add a data attribute to the class graph called "names", which should be a list of a size equal to the number of nodes, storing a name for each of them. Add a loop to the class method readfile to read the names from the graph file. Here are two examples of graph files:
graph1.txt
roman.txt

These names are stored on a single line, separated from the set of distance values by a single empty line. You can assume that the graph file has the correct format. The graph in the file roman.txt is based on Figure 3.2, page 63 in the textbook, and the distances on page 95.

b. Note that the file contains an implementation of the algorithm A*. At the end of the algorithm, the data attribute graph.pred should contain the predecessor of each vertex on the path from the origin of the search to it. Write a function print_path that reconstructs the path from this data member from the origin to the destination and prints it out using the names stored in the data attribute that you added at point (a). The function should also print the total cost of the path at the end. Implement this function as a class method in the class Graph taking a parameter "self" and two other parameters for the origin and destination. Call this function at the end of the execution of A_star (from inside).

c. Implement the function rbfs using the data structure Graph. The pseudocode for this function can be found in the Informed Search slides.

Write a paragraph or two to compare the two search methods and argue why you think one is better than the other (you can also argue that they are similar if that is your opinion). Perform some experiments on the given graphs with both of them to support your arguments.

Ex. 2 Consider the graph in the following figure. This is based on a Middle Earth map, examples of which you can find here. See the Oncourse resources for a bigger detailed map in pdf format taken from this site.

Option a. Find an optimal path going from Eriador to Mordor by tracing the A* algorithm by hand. Here are the Euclidean distances to Mordor you will need for this part:
Dunland - 85
Enedwaith - 93
Eriador - 120
Gondor - 57
Haradwaith - 50
Harondor - 37
Iron Hills - 88
Khand - 35
Northern Waste - 118
Rhovanion - 73
Rhun - 76
Rohan - 68
Umbar - 90

Write the content of the queue after each step. You can turn this in on paper or as a text file.

Option b. Write a graph file in the format we've used at Exercise 1 to represent the Middle Earth path and run the implemented algorithm on it to find the path between Eriador and Mordor. Send me the result of the run either in the email or as a separate text (!) file, together with the graph file.

Question. Can you tell after doing this (for either option) if the path taken by Frodo was optimal?

Turn in: all the functions in one python file, by email only, and whatever you choose to do for Exercise 2.