COSC 387: Artificial Intelligence

Project 2
Fall 2000

Due: Oct 18 @ 5 P.M.
7 points

  1. In Lisp, encode the following weighted graph:

  2. Use the following latitudes and longitudes for the cities to write a function that returns the estimated distance between two cities. 
    Paris, 48:51:00N 2:20:00E
Caen, 49:15:00N 0:20:00W
Calais, 50:57:36N 1:57:00E
Dijon, 47:21:00N 5:02:00E
Lyon, 45:44:00N 4:52:00E
Grenoble, 45:21:36N 5:19:12E
Avignon, 43:50:00N 4:45:00E
Marseille, 43:18:00N 5:25:00E
Nice, 43:42:00N 7:21:00E
Montpellier, 43:38:00N 3:53:00E
Toulouse, 43:37:00N 1:27:00E
Bordeaux, 44:50:00N 0:37:00W
Limoges, 45:30:00N 1:10:00W 
Rennes, 48:07:00N 1:02:00W
Brest, 48:24:00N 4:30:00W
Strasbourg, 48:32:24N 7:37:34E
Nancy, 48:50:00N 6:10:00E
Nantes, 47:15:00N 1:30:00W
  3. Implement

    1. one uninformed search algorithm (e.g., depth- or breadth-first),
    2. one informed search algorithm (e.g., hill-climbing or best-first search), and
    3. one admissible search algorithm (e.g., branch-and-bound or A*).

  4. Using each algorithm, attempt to find the shortest path between the following initial and goal cities:

    Run Initial State Goal State
    1 Brest Marseille
    2 Montpellier Calais
    3 Strasbourg Bordeaux
    4 Paris Grenoble
    5 Grenoble Paris
    6 Brest Grenoble
    7 Grenoble Brest

  5. For each algorithm, over the seven runs:

    1. what was the average number of nodes entered (i.e., visited)?
    2. what was the average number of nodes expanded?
    3. what was the average number of nodes maintained (i.e., stored)?
    4. how often did it find the optimum?

    Place these results in comments at the top of your source file.

Hint: Take a look at property lists as a way to represent graphs.

Instructions for Submission: Although you can use any Common Lisp environment, all programs must run under GNU gcl. When you are ready to submit your program for grading, e-mail it as one file to the TA using the last four digits of your student ID and the suffix ``.lisp'' as the subject line.

For example, if the last four digits of your student ID is 1234, the name of your source file is proj1.lisp, and your TA's e-mail address is ``imagoodtamaloof@cs'', then you would type at the UNIX prompt: 

gusun% mailx -s "1234.lisp" imagoodtamaloof@cs < proj1.lisp
You must e-mail your project before 5:00 P.M. on the due date.

Once you submit your project, it is important to keep an electronic copy that preserves the modification date and time. If we lose your project or the e-mail system breaks, then we will need to look at the modification date and time of your project to ensure that you submitted it before it was due.

Finally, when storing source code on university machines, it is important to set file permissions so others cannot read the file. To turn off such read/write permissions type at the UNIX prompt chmod og-rw <file>, where <file> is the name of your source file.