CMSC 671

Artificial Intelligence -- Fall 2001

HOMEWORK TWO
out 9/11/01 due 9/25/01

http://www.cs.umbc.edu/671/fall01/hw2.html



PART I.  Uninformed search (60 pts.)

READING: Read Chapter 3 of Russell & Norvig

ASSIGNMENT:

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

Describe a search space in which iterative deepening search performs much worse than depth-first search.

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

Write out the algorithm for bidirectional search, using pseudo-code similar to the examples in the textbook. Assume that each search is a breadth-first search, and that the forward and backward searches alternate expanding one node at a time. Be careful to avoid checking each node in the forward search against each node in the backward search.

3. Analyzing bidirectional search (R&N 3.12 - 6 pts.)

Give the time complexity of bidirectional search when the test for connecting the two searches is done by comparing a newly generated state in the forward direction against all the staets generated in the backward direction, one at a time.

4. Uninformed search methods

Suppose you have the following search space:
State Next state Cost
A B 4
A C 1
B D 3
B E 8
C C 0
C D 2
C F 6
D C 2
D E 4
E G 2
F G 8

(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:

  1. Breadth-first search (6 pts.)
  2. Depth-first search (6 pts.)
  3. Uniform cost search (6 pts.)
  4. Iterative deepening search (6 pts.)
At each step of the search algorithm, show Also report the eventual solution found by each algorithm, and the solution cost.

5. Thinking about search trees

Suppose we have a finite, uniform search tree of branching factor b and depth d. The only solution node is at the middle of the last level.
  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.
Partial credit will be given for incorrect answers with near-correct derivations, so show how you arrived at your answer!

PART II. Lisp data structures (40 pts.)

READING: Read Lisp Ch. 3 and supplementary notes distributed in class

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 providedfor the map of Romania on page 95 of the textbook:
  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.
  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.
    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)