Due: F 2/4 @ 5 PM ET
For this project, we're going to France. Formidable! You will implement state-space search routines for finding paths in a weighted graph.
For this and subsequent projects, you must implement your program using Java 11. Your code must be well-structured and well-organized and follow object-oriented design principles. Do not use packages.
For this and subsequent projects, you must implement your program using only the standard libraries the language provides. If you want to use external libraries or something non-standard, check with me first.
For this and subsequent projects, you must also provide a Makefile that produces the required executable and class files. The Makefile must include a clean target that removes the class files so the autograder can produce the executable from the source code. Note that compiling and running your program on cs-class (cs-class-1.uis.georgetown.edu aka class-1.cs.georgetown.edu) will be the best guarantee that it will compile and run on Autolab.
I put some starter code on cs-class. To get started, log on to cs-class and copy over the following zip file:
cs-class-1% cd cs-class-1% cp ~maloofm/cosc270/p1.zip ./ cs-class-1% unzip p1.zipIn the p1 directory, you will find a Makefile and class definitions for Action, State, Problem, and Main.
Your implementation must work for any state-space search problem, so you will need to derive classes for finding paths in France from Action, State, and Problem. The code in Main should help you understand these classes and the other classes and methods you will need to implement. Do not change the names of the classes or methods that I have specified in this assignment. I will evaluate your implementation on a search problem that you have not seen before.
Derive a class from Problem and 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 france.txt should help you save a few keystrokes, especially if you know how to program. There is also a copy of this file in p1.zip.
The Main.main that you submit should use each of the three search methods to find a path between the following initial and goal cities:
|Run||Initial State||Goal State|
For each algorithm and then for each pair, your Main.main should print to the console the cost of the solution, the actions, and the counts.
Name NetID 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 submit.zip Main.java (other java files) Makefile README HONORYou can also type:
$ make submit
Upload submit.zip to Autolab. You can submit to the compile check p1c five times. You can submit your assignment p1 two times. Make sure you remove all debugging output before submitting.
Copyright © 2022 Mark Maloof. All Rights Reserved. This material may not be published, broadcast, rewritten, or redistributed.