Your goal is to write a LISP program that can easily and modularly be modified to solve many different state-space search problems. This is just a case of natural object-oriented programming. The search algorithm is independent of the problem (domain-independent) and can be reused in different domains by simply changing the representation of the problem. Contrariwise and interestingly, different search algorithms can easily be dropped in for the same domain to assess their strengths and weaknesses.
A search algorithm does not depend on its domain. What is domain-dependent, then? The representation of the problem state , the operators (equivalently, the successor function ), the starting (initial) state , and the test for whether you're done (solved the problem, found the goal state ).
After a while you'll be able to look, as CB did, through a book of puzzles and see immediately the problems for which state-space search is appropriate work. Maybe you too can win prizes solving newspaper puzzles using LISP on your home computer. OK, Onward.
Represent a binary tree whose nodes are integers as an S-expression where the first element is the (sub) tree root and the second and third are, recursively, the left and right (sub) trees. So the tree
0 / \ 1 2 / \ / \ 3 4 5 6 is (0 (1 (3)(4)) (2 (5) (6))) and 0 / \ 1 2 / \ 3 6 / 4 is (0 (1 (3 (4) ()) ()) (2 () (6)))
Write a program to solve water-jug problems. WARNING: It seems to be incredibly seductive to students to build domain-dependent stuff into their code, so this is a chance to get some minimal credit for writing a special-purpose, one-off jug-solving program. But you shouldn't do that, right? You should make this the first test of your general state-space searching problem-solving program. That means you'll be getting credit on THIS part of the assignment that also will count on the NEXT part. Congratulations, you're double-dipping!
In fact, I'll give you my version of a representation and successor function for this problem so you only have to write the search part, which should be useful for stage two.
So read this section and the next carefully, and do modular design that lets you reuse the maximum amount of code (the entire search implementation) between different search problems.
In the most usual form of jug puzzles, the rules say you you start with n (possibly empty) jugs, each with a maximum capacity. Call the capacities c1, c2, ...., cn. Jugs have no measuring marks on them. There is a pump to supply water, and you can pour water either into a jug or onto the ground. Your task is to achieve some particular goal state , often with some particular amount of water in any jug, or in a particular jug.
So what's important here? How do we represent the core (the state of this problem? With an infinite supply of water from the pump and an infinite sink (the ground) into which we can pour water, the only variables left to describe the system, (they make up the state description), are just how much water there is in the jugs.
But of course the problem also specifies the operations , which are equally important. Both state and operations are problem-dependent. Typically for jugs you can completely fill a jug, pour all or some of the water from one jug to another, or pour water on the ground.
Formulate this problem as a state-space search problem: how can you describe the relevant state of the system? Hint: n variables, one per jug, containing the amount in that jug. Let's call them j1 thru jn. Store them in a list and you have a state vector . What effect do your operators have on the state? (e.g. filling jug 2 changes its j2 to c2, emptying on the ground changes j2 to 0, pouring it into jug 3 changes j2 to 0 and j3 to the minimum of c3 and j3+j2, etc.). Here is where you code the effects of your allowed operations on the state into a successor function.
Remember what's going to happen: you're going to try an operation, (or maybe several, so as to generate all the successors to the current state), and then check the resulting state(s) to see if if you're at the goal state, and if not try another operation. Which operations you try in which order is your search strategy, which is NOT going to be problem dependent.
In this case thinking of operations can be a bit of a distraction, because if you increase the number of jugs it seems like you need to increase the number of operations. For this problem as for others, it's better to think of a successor-generator function that produces a new state from a particular operator description. You don't want operations like "Pour_1_into_2", since it's not easy to generalize a program with names like this automatically as the number of jugs increases. The answer is NOT to worry about how to create new variables in LISP, or anything weird or complex. The answer is to step back and think a bit. Think Successor Function, think of ONE parameterized operation. While you're at it, think whether the pump and the sink (or ground) are maybe like jugs a bit. Here is CB's representation and successor function for use with your search algorithms.
Write a program whose input is a start state (typically all jugs empty), a goal state, and a set of operators, and which finds a solution by searching the state space. It starts at the start state, applies an operator (or generates sucessors), sees if the result is the goal state. If so it declares success and prints out the set of operations it performed to move from start to goal. Otherwise it continues searching the successors of the states already investigated. For this problem, you can use "breadth-first" search with a queue, or "depth-first" search with recursion or a stack. If you use depth-first, you need to detect repeated states (you're in a loop). That may be enough to make sure you are making forward progress. In either case you will need to keep track of the parent of your current state so that you can remember the path that got you there from the initial state. All this should be problem-independent, right?
Here's a sample problem to test your work: You have two jugs, a 4-gallon and a 3-gallon. Your job is to get exactly 2 gallons into the 4-gallon jug.
Your output should be a list whose sublists are the states (the j
numbers)
in order
from initial to goal state. Since the rules are so simple you'll be
able to tell what the operator was that took you from state to state.
So for example a solution to the problem above might look like...
START IS: (0 0)
GOAL IS: (2 0)
C NUMBERS ARE: (4 3).
SOLUTION: ( (0 0) (0 3) (3 0)... (0 2) (2 0))
STATES EVALUATED: 54
SOLUTION LENGTH: 8 OPERATIONS
For extra credit, implement both breadth- and depth-first search and write a little report on their behavior: which finds shorter solutions, which explores more states, how do those answers change when the problem size increases, etc.
Use your general search routines on one or more problems that call for new representations and operators.
This should not involve modifying your search algorithms, only a new formalization of the state, the operators, and of course the starting and goal states. Here's one sort of different problem, but not seriously different: you might want to do it as a quick five-finger exercise since it is a very slight change to the basic jugs problem.
A merchant has a beaker containing 24 ounces of a precious fluid. He also has empty 5-ounce, 11-ounce, and 13-ounce beakers. How can he divide the fluid into three equal portions?
This one seems just like the standard jug problem except for the goal state, and presumably we don't want to pour precious fluids onto the ground so the operators change a bit. Same representation, very similar operations, so not seriously different. Simple, classic, and definitely different is the "missionaries and cannibals" problem: (Text, problem 3.9, Page 90).
Other fun problems from Sam Loyd are in the course reserves , and are interesting in that their representations involve things like checkerboards, game boards (like the famous 15 puzzle), and there are a couple of variations on the classic "missionaries and cannibals" puzzle.
Do at least two problems (one per team member) that require non-jug representations and operations.
For extra credit: Given a "classic" N-jug problem, is it possible predict whether a solution exists just from the jug capacities? Give your algorithm or method and prove or show why it works (or show that you actually cannot say anything about the existence of a solution). For partial extra credit write your thoughts on how you would approach this problem. Examples: can you measure out 37 gallons with jugs of 1,2, and 1000000 gallons? clearly yes. With jugs of 1 and 10000 gallons? Yes again. With jugs of 2,4,6,8,10,12,18, 24, and 48 gallons? No. So what's the general rule here?
Submit on WebCT your code, a README that explains it, and a nice writeup in good technical prose, explaining what you did and how, and detailing the results of any experiments or comparisons you did using your code. The writeup must be in PDF. Upload to WebCT as usual.
There are examples of project writeups for this course at
242's main assignment page
and there are explicit writing helper documents on
The writing helper page
.