CMSC 471 - Fall 2008

Homework 3

This homework will have you write a breadth-first-search framework that will allow you to plug in several different search problems.

General notes:

All your functions should have some sort of comment describing what that function does.
Comment your code well, indent well and keep your parens organized so we can understand your code.
The names of functions are important so that we can grade your work.
All file names should have your last name in it somewhere.

Write a bfs function that takes the following parameters (in this order):

Start node. This node states what the search should start at. This node should be in whatever format your expand function takes.
Goal node. This node states what node must be discovered for the search to end. This node should be in whatever format your expand function takes.
An expand function. This function takes a parameter that is a node and returns a list of all possible nodes to transition to.

Now that the bfs function has these 3 paramters, use bfs to search the state space with a BFS. Expand the start node, then expand its children, then its childen, then its childen, etc. until the function finds the goal state. The bfs function should return the path from the starting node to the finishing node in the form of a list.

Hint: you want to think about how your searches will deal with loops in the search space graphs.

Hint on implementing your BFS:
Here is a major hint for HW3: First of all, you don't necessarily have to represent the state space as a "tree". the expand function does most of this. My suggestion is to get the BFS part of this working, where it just searches through the state space and finds a solution, but ignores the path to get there. Then, when you are sure this part is working, try to get the path returned. The part that makes this hard is keeping track of the path to each node. Think about your node "data structure".

What other stuff could you store per queue entry to keep track of the path? You could make a defstruct to make a structure, that stores the current state and the path to get there. Or, instead of enqueuing nodes, you enqueue lists that stores the path.

For example in the 8-puzzle domain, perhaps instead of queueing ((1 2 3), ('BLANK, 8, 4), (7 6 5)) as a to-explore node, you should enqueue something like ( ((1 2 3), ('BLANK, 8, 4), (7 6 5)), (('BLANK 2 3), (1, 8, 4), (7 6 5)), .... ((6 5 4), ('BLANK, 3, 1), (8 7 2)) ). Note, in this way, you store the current node to be explored (the car of the list above), plus the path that it took to get to that node (the cdr). This way, when you find the goal node, you can just return the list.

There are cleaner ways of doing this, and I recommend exploring these ways. However, this can get you by, and perhaps inspire you to do something similar.

Now, you will test your BFS by doing the following...

Figure out how you would represent the Missionaries and Cannibals problem as a search problem. Search for the solution with BFS.

Figure out how you would represent the following water jug problem as a search problem:
Two friends who have an eight-quart jug of water wish to share it evenly. They also have two empty jars, one holding five quarts, the other three. How can they each measure exactly 4 quarts of water?. Search for the solution with BFS.

Additional requirement: Although not required for the BFS to actually function, have your expand functions print to standard out what node it is currently expanding and the list of nodes it is returning. A line of output may look like: (3 4 3 1) --> (3 5 3 1), (3 3 3 1), (3 5 3 0)

Extra Credit:

For any extra credit, include a short writeup comparing the solutions returned by all search algorithms you used. Was one solution better than the other? How many expand-operations were performed for each one?

[.2 points] Write a function that follows the same framework as bfs that performs a DFS instead of a BFS. Call this function dfs.

[.3 points] Write a function that follows the same framework as dfs and bfs that performs iterative deepening DFS. Call this function id-dfs.