CMSC 471

PART I.  Uninformed search (60 pts.)

ASSIGNMENT:

1. Analyzing search (R&N 3.9 - 4 pts.)

2. Bidirectional search (R&N 3.11 - 7 pts.)

3. Uninformed search methods

(a) (4 pts.) Draw the state space of this problem as a directed graph in which the states are represented as nodes and actions/operators as directed edges, labeled by their cost.

(b) Assume that the initial state is A and the goal state is G. Show how each of the following search strategies would create a search tree to find a path from the initial state to the goal state. (Assume that when a node is expanded, the successor states are always generated in alphabetical order.)

1. Breadth-first search (6 pts.)
2. Depth-first search (6 pts.)
3. Uniform cost search (6 pts.)
4. Iterative deepening search (6 pts.)

• which node is being expanded,
• the content of the nodes list (with node names and costs for the path to that node through the search tree)

4. Thinking about search trees

1. (5 pts.) Compute the number of nodes expanded by an uninformed depth-first search.
2. (5 pts.) Compute the number of nodes expanded by an uninformed breadth-first search.
3. (5 pts.) Compute the number of nodes expanded by an uninformed iterative deepening search.

PART II. Lisp data structures (40 pts.)

ASSIGNMENT:

In this assignment, you will create data structures in Lisp to represent a road map, and utilities to manipulate the map. In the next assignment, we will use this code to perform search over the map, so be sure that your solutions are complete and that you understand the data structures thoroughly.

1. Create a city data structure, using defstruct. The structure should have 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 Bucharest
2. Define a global variable, *all-cities*, that contains a hash table that will store the cities. Initialize this table to be empty.
3. Define reader 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 on page 95 of the textbook:
• http://www.cs.umbc.edu/courses/undergraduate/471/fall02/hw/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.
• http://www.cs.umbc.edu/courses/undergraduate/471/fall01/hw/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: read in the cities first, then read in the neighbors file, updating the neighbor lists of both cities as you go along.
4. Write the following functions to manipulate your map. Some of these functions will be useful in your reader functions, so you may wish to test them first, then test the reader functions.
• all-cities should return a list of the names of all the cities on the map. (Hint: here and in many other functions, you will want to use the *all-cities* hash table. If you specify it as an optional argument, you can invoke the same function on other hash tables as well, thus making your code more general and elegant, but avoiding the bother of sending *all-cities* as an argument to every function.)
• get-city-struct should take the name of a city, and return the corresponding city structure. (Hint: it's often convenient to write functions that can be invoked generically on either a city or a city struct, so if you add a bit of error checking here, you can avoid checking to see if something's a city structure in other places in your code.)
• city-neighbor-list should take the name of a city and return a list of its direct neighbors (just the names, not the association table entries). (Hint: be sure that if your data structure is called "city," you don't then call the neighbor slot in the data structure "neighbor-list," because then the accessor function for the neighbor slot will conflict with this function name, which will cause you much grief.)
• neighbors-p should take the names of two cities and return the distance between them if they are directly connected, or NIL if they are not.
• neighbors-within-distance should take the name of a city and a distance value, and return a list of the names of all direct neighbors of the city that are within the specified distance of the city.
• closest-neighbor should take the name of a city and return the name of its closest direct neighbor.
• You may also want to have some printer utilities for printing cities or maps, in order to facilitate testing and debugging.  If you do write some printer utilities, demonstrate them in the script you turn in for extra credit.
5. Submit your code and a test run as follows:
1. Turn the code itself in using the submit facility. Please create a single file containing all of the code, and name it hw2-NAME.lisp, where NAME is your first name. The project name for submit is hw2.
2. Also turn in a script of your code running on the following test examples. This file should be called hw2-NAME.out. You should create this script as follows:
1. Start Lisp from the shell
2. (dribble "hw2-NAME.out")
3. (read-cities)
4. (all-cities)
5. (read-neighbors)
6. (city-neighbor-list 'oradea)
7. (closest-neighbor 'sibiu)
8. (get-city-struct 'pitesti)
9. (neighbors-within-d 'rimnicu_vilcea)
10. (dribble)