You are given two cans, one holding 3 pints, the other 4 pints. Neither has level markers. How can you exactly half fill the 4 pint can?
The state space is described by the pair (m,n), the volumes in the 4pt and 3pt can respectively. The initial state is (0,0), the final state is (2,*) where * is a ``don't care'' wildcard, here we have multiple goal states.
A set of production rules might be:
No | Applicability | After | Comment | |
1 | (m,n : m < 4) | ® | (4,n) | Fill 4 pint can |
2 | (m,n : n < 3) | ® | (m,3) | Fill 3 pint can |
3 | (m,n : m > 0) | ® | (m-d,n) | Pour volume d out of 4pt |
4 | (m,n : n > 0) | ® | (m,n-d) | Pour volume d out of 3pt |
5 | (m,n : m > 0) | ® | (0,n) | Drain 4pt |
6 | (m,n : n > 0) | ® | (m,0) | Drain 3pt |
7 | (m,n : m+n ³ 4 Ùn > 0 ) | ® | (4,m+n-4) | From 3 into 4 until full |
8 | (m,n : m+n ³ 3 Ùm > 0 ) | ® | (m+n-3,3) | From 4 into 3 until full |
9 | (m,n : m+n £ 4 Ùn > 0 ) | ® | (m+n,0) | Empty 3 into 4 |
10 | (m,n : m+n £ 3 Ùm > 0 ) | ® | (0,m+n) | Empty 4 into 3 |
So the production system comprises:
One possible solution is
m | n | Then Rule | Comment |
0 | 0 | 1 | Start;Fill 4 |
4 | 0 | 8 | From 4 to 3 until full |
1 | 3 | 6 | Drain 3 |
1 | 0 | 10 | Empty 4 into 3 |
0 | 1 | 1 | Fill 4 |
4 | 1 | 8 | From 4 to 3 until full |
2 | 3 | Goal |
Some of you will have been puzzled and uncertain about rules 3 and 4, and rightly so. The fact that we have 3 and 4pt cans tells us that the smallest quantum of water we can measure exactly is 1pt. So what place for some arbitrary quantity d? Of course there is none: those rules will never be used by our system in reaching the goal, they will always result in dead-ends in our search (dead-ends will be clearer after the next section). The question is, do we remove them and face the accusation of ``fixing'' the problem or do we let the system tell us they are redundant by never using them?