CS 63

Implementing search (100 pts.)

Reminders:

• Any code you turn in must be your own, with the sole exception of the code provided by the instructor as part of this assignment.
• Indicate whether you worked with anyone else or received any help on the concepts in this homework. (As the course policy states, you may discuss the assignment with other students, but must indicate this in your homework, and must write your own code yourself.)
• Don't forget to do error checking and to document your code.
• Use the function names indicated here, so that I can test your code for grading purposes.
• Be sure your code works in CLISP, even if you use another Lisp environment for development.

Assignment

1. The number of nodes expanded
2. The cost of the path found
3. The path from the start to the goal as a list of city names.

Use the Lisp function values to return these values.

The heuristic function h(n) that is used by the A* and greedy search algorithms (i.e., the estimate of the distance to the goal) should be the straight-line distance to Bucharest.

Results to Report

You should turn in your code using the handin63 facility. Please create a single file containing all of the code, including the code provided by the instructor with this assignment. Name this file <Lastname><Firstname>HW2.lisp. For example, I would turn in a file named EatonEricHW2.lisp.

Your code is due at exactly 7:00pm on the due date (the same time class starts). After that time, your submission is considered late. I highly suggest that you submit your code file often, both to test that the submission procedure works and to keep a backup copy of your progress.

In addition, you should turn in, in hardcopy, both a printout of your code (formatted as neatly as possible) and the results table of the three search functions applied to each city in Romania (as the first argument) for a path to Bucharest (the goal city), using the following table format as a guideline. To save paper, I recommend that you print your code with two logical pages per sheet (e.g., using mpage -2ol).

You should also write a brief summary of your findings, comparing the performance of the algorithms, and discussing particular cases where one of the algorithms performs better than the others. (This summary can be anywhere from a few short paragraphs to one or two pages.) This should be a well-written analysis of your results in the form of a mini-report.

Write a Lisp function called hw2 that loads all appropriate files, initializes all data structures, runs the appropriate searches, collects the results and prints them out in a table like this. If it's easier, you can provide the same information in a different format, as long as it's clearly readable, all of the data shown below is given, and you show the results for the 20 cities in alphabetical order. A (very) incomplete version of the hw2 function is included with the utilities described below. Hint: the bulk of this function will likely be a loop that runs all of the algorithms on all of the cities and gathers the results in some central place, then outputs the tabular data.

In the case where a search method fails to find a path, you should indicate the lack of a result (e.g., with "--" , NIL, or "FAILURE") in the corresponding table entry.

City name	#nodes / BFS	# nodes / greedy	# nodes / A*	Path cost / BFS	Path cost / greedy	Path cost / A*
Arad
Bucharest
...
Vaslui
Zerind

Provided Map Utilities

1. A city data structure, created using defstruct, with the following attributes:
1. The name of the city (represented as a symbol)
2. The neighbors of the city (represented as an association list of neighbor / distance dotted pairs)
3. The straight-line distance from this city to the goal city.
2. A global variable, *all-cities*, that contains a hash table that will store the cities. Initially, the hash table is empty.
3. Functions read-cities and read-neighbors that will read the cities, neighbors, and distances from two files I've provided for the map of Romania (the example used beginning page 95 of the textbook):
• cities.txt This file contains a series of lines, one for each city. Each line lists a city's name, followed by the city's straight-line distance to Bucharest.
• neighbors.txt : This file contains a series of lines, one for each neighbor/neighbor pair. Each line lists the first city's name, the second city's name, and the distance between the two.
• Hint: When you use these functions, read in the cities first, then read in the neighbors file.
4. The following map manipulation functions:
• all-cities : returns a list of the names of all the cities on the map.
• get-city-struct : takes the name of a city, and returns the corresponding city structure.
• city-neighbor-list : takes the name of a city and returns a list of its direct neighbors (just the names, not the data structures). (Note: In the data structure city, the neighbor slot in the data structure isn't called "neighbor-list," because then the accessor function for the neighbor slot will conflict with this function name, which would cause us all much grief.)
• neighbors-p : takes the names of two cities and returns the distance between them if they are directly connected, or NIL if they are not.
• closest-neighbor : takes the name of a city and returns the name of its closest direct neighbor.
• neighbors-within-distance : takes the name of a city and a distance value, and returns a list of the names of all direct neighbors of the city that are within the specified distance of the city. This function is incomplete and you must complete it as part of this assignment.
5. Here is a brief example of using the data structures. I recommend everyone try this example out! Here's what you should type into lisp after you start it from the shell.
   1. (load "hw2-utilities.lisp")
   2. (read-cities "cities.txt")
   3. (all-cities)
   4. (read-neighbors "neighbors.txt")
   5. (city-neighbor-list 'oradea)
   6. (closest-neighbor 'sibiu)
   7. (get-city-struct 'pitesti)
   8. (neighbors-within-distance 'rimnicu_vilcea 90)

The neighbors-within-distance function is incomplete. I provided the function with most of my comments, but without the code. You must fill in the code for this function as part of this homework assignment. It will give you practice using the map data structures before you launch into implementing the search algorithms. When doing your implementation, look at the other provided utility functions for inspiration.

The first thing you should do in completing this assignment is read the provided code in detail to understand it. Read it slowly, look up the usage of every lisp command you don't understand immediately, and then read it through several more times. If anyone still needs help understanding it, please see me in person. However, if you want me to help you understand it, you must first make a real effort to try to understand it yourself.

Implementation Suggestions

• Modify the provided city data structure to add a new field, visited, for marking which cities have already been visited in the search.
• Create a new data structure to represent a node in the search tree. This structure should have attributes pointing to the structures of the node's parent (empty for the root), the children of the node, and the city it represents. You may also want to include other attributes for bookkeeping purposes, such as the path so far, and the path cost.
• Implement the generic search strategy presented in the textbook that was reviewed in class. This function should take (at least) a city name and a queuing function as arguments. You may want to implement it to take other arguments as well (for example, the map and the expansion function). Your specialized search methods should invoke this generic search function with the appropriate arguments.
• Implement the function expand-node, which takes a node in the search tree and generates its children. Think about whether you want to use the same expand-node function for all three search strategies, or implement two or three different versions.
• Implement three queueing functions, one for breadth-first search, one for greedy search, and one for A* search. This function should take the current node list and the list of nodes generated by expand-node, and return an updated node list. Note that these queueing functions need to check for duplication of states and handle them appropriately.

This assignments was adapted by Eric Eaton from a set of two assignments by Tim Finin and Marie desJardins.