![[CS logo]](../t.png)
CMSC 25000 - Artificial Intelligence
Winter 2004
Homework #2: Due January 20, 2004
Goals
Through this assignment you will:
- Implement search procedures.
- Understand the close interrelationships between different search procedures.
- Explore additional applications of search.
Background
Files for this homework assignment can be found
here
When trying to find cheap airfares, one often encounters itineraries and
routes that are convoluted to say the least. Here we exploring routing
through a hypothetical airline's system to locations that may be off the
beaten path. Any resemblance these routes bear to itineraries suggested
by on-line travel planners is purely coincidental.
The bulk of the code for this problem set can be loaded by airsearch.scm. The large data file is in airroutes.scm
The main search function is
(generalized-search start finish finish? merge-paths-into-queue how-many successors)
- start and finish are the starting and ending nodes of the search.
- finish? is a function that checks to see if the goal has been reached, and provides some abstraction in that check.
- merge-paths-into-queue is a function that determines how new paths are added to the queue. As you should recall from lecture, this component has a great deal of impact on what type of search is implemented.
- how-many is either all or an integer indicating how many paths to find.
- successors is a function that computes the way in which a path is extended.
The main data abstractions are as follows:
- An airport consists of its name, its (approximate) latitude and longitude in integer values, and the names of those airports in connects to. E.g.
(chicago-midway 88 132 indianapolis detroit bwi las-vegas orlando)
The variable *data* is bound to a list of airports.
- path is a list of airport names.
- queue is the list of paths currently being explored.
Problem 1
Since we are searching a graph rather than a tree, there are some additional
details that must be handled. To explore one of these difficulties try
the following simple search: (step-by-step '(chicago-midway)). This function incrementally and interactively extends the search path.
Press 'y' a few times to observe its behavior.
What problem you observe?
Fix the problem in extend-path and hand in your code
and the output of a run on the above example to demonstrate that it works.
Problem 2
The source code contains a stub for the depth-first procedure.
Complete the implementation, debugging your code on the test data.
When it works, run your completed code on (depth-first 'newark 'san-francisco using the
(loadrealdata) to load the real data.
Turn in your modification of depth-first and the verbose
output for the above run.
Problem 3
In class we discussed the relationship between depth-first and breadth-first
search. We also know how irritating it is to have a large number of
connecting flights, and would like to find the route with the fewest hops.
Implement a function breadth-first. Debug using the
small test data set.
When your code is operational, load the real data and run
(breadth-first 'newark 'san-francisco). Hand in your function code,
and the verbose output from the run.
Problem 4
Just finding a route is useful, but we'd really prefer to find the
SHORTEST route efficiently.
Implement a version of a-star search. Run your
version of a-star on the above example.
Consider using a hash table to implement dynamic programming.
You will probably need to modify some of the data abstractions
since we are now concerned with path costs as well. We have included
a function straight-line-distance to aid in your search.
The library loaded at the top of the code should also import a quicksort function.
What differences are there? What savings do you gain?