COSC-574: Automated Reasoning

Project 3
Fall 2017

Due: R 12/7 @ 11:59 P.M.
10 points

For this project, we're going to France. Formidable!

Using Java, implement

  1. uniform-cost search as the method ucs,
  2. greedy best-first search as the method gbfs, and
  3. A* as the method astar.
  • Encode the following weighted graph:

    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:00E
    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

    The file graph.txt should help you save a few keystrokes, especially if you know how to program. There is also a copy of this file on cs-class, which you can copy by executing

    cs-class% cp ~maloofm/cosc574/graph.txt ./

  • In addition to computing a solution and its cost for the initial and goal cities, each search method should also compute:

    1. the number of nodes explored, entered, or visited
    2. the number of nodes expanded (i.e., the total number of successors)
    3. the number of nodes maintained (i.e., stored in the frontier)

    Main.main should use each of the three search methods to find a 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

    Main.main should print the solution, the path cost of the solution, and the counts.

  • For each search method over the seven city pairs, compute the following:

    1. the average number of nodes explored or entered
    2. the average number of nodes expanded (i.e., the total number of successors)
    3. the average number of nodes maintained (i.e., stored in the frontier)
    4. the average number of times it found the optimal solution
    Place these averages in a file named README. Write a paragraph that compares and contrasts the search algorithms in terms of these statistics. What differences or similarities do you see between the informed search algorithm and the optimal search algorithms? What differences or similarities do you see between the two optimal search algorithms. Include this file with your submission.

    Instructions for Electronic Submission

    In a file named HONOR, provide the following information:
    In accordance with the class policies and Georgetown's Honor Code,
    I certify that, with the exceptions of the course materials and those
    items noted below, I have neither given nor received any assistance
    on this project.

    When you are ready to submit your project, create the zip file for uploading by typing:

    $ zip (other java files) README HONOR
    Upload to Autolab. You can submit your assignment p3 five times. The autograder will simply call Main.main.

    Plan B

    If Autolab is down, upload your zip file to Canvas.

    Copyright © 2019 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.