Water-Jug Problem
Imagine that you have two jugs called X and Y. Initially, both are empty. You are allowed to fill either
jug X or jug Y from a tap but if you do, you have to fill it completely. You are also allowed to fill jug X
from jug Y, or jug Y from jug X, and to empty either jug on the ground. Jug X can hold 4 pints and jug
Y can hold 3 pints.
The problem is simply this: given the allowed actions, can you manage to reach a state where you have exactly 2 pints in jug X. This problem is known as the water jugs problem and it has no easy solution. If we just fill X from the tap we end up with 4 pints in X, not 2. If we fill Y from the tap and empty it into X, we end up with 3 pints in X. The only way to find a solution to this problem is to consider systematically the effects achieved by performing sequences of actions. But how can we go about this? Systematically considering all possible sequences of actions is just like systematically considering all possible sequences of locations (i.e. all possible routes). So the water jugs problem can be construed as a sort of search problem. Of course, if we are going to construe the water jugs problem as a search problem, nodes in the search space will have to represent states of the two jugs rather than locations in a physical environment. The start node, will have to be a representation of the initial state (e.g. 0 pints in both jugs); the goal node will have to be a representation of the goal state (e.g. 2 pints in X, any amount
in Y), and the successor function will have to return that set of new states which can be reached from
any given state by performing exactly one allowed action. So the main difference between this example and the one used in the previous chapter is that each state now contains some components (e.g. the contents of the two jugs) rather than just being an atomic value (e.g. clock_tower).
Constructing Successor Nodes
We can represent states in the water jugs problem as two-element lists in which the first element is an
integer representing the number of pints in the jug called X, and the second element is an integer
representing the number of pints in Y. Thus, the state in which X has 3 pints in it and Y has 2 would be
represented by the list expression:
__________ _____ ____ ____ ________ ___ ____ _______ ____.
______ __________ ___ ______ ______.
_________ _____ __________ ____ ______ ________ ________ ________ ____ _________ ________ ____.
___ _____ __________ _____ ___ ___ __________.
_____ _______ ______ ________ __________ ______ _______.
________ ____ _____ _______ ____ _____ ___ __________ ___ ____.
__________ _____ _______ ________ _____ _____ ________ _________.
______ ______ ___ _________ __________ ____ ___ ______ ____ ___ ___ ___.
__________ __________ _______ _____ _____.
___ ____ _____ ______ _______ ____ ________.
___ _______ ____ _________ ____ _______ _____ _________ ____ _________ _______.
___ ______ ______ _______ ______ ___ ______ ______ _____ __________ __________.
____ _______ ___ ____ __________ __________ ______ _________ ___ _________.
______ ________ _____ __________ ______ _______ _______ ____ _________ __________ ______.
_______ ______ ______ _________ _________ ________ _______ _______ _________ ___ _____ ___.
_______ ________ _________ ______ ________ ______ __________.
________ ______ ____ _____ __________ _____ ___ _______ __________ _____.
____ ___ ________ ______ ___ ______.
______ __________ __________ ________ _________ ______ _____ _____ ______ ______ _______.
______ ________ __________ __________ ______.
__________ ________ ______ ___ _______.
______ _______ _______ _________ ______ ___ ___ __________ __________ ____ _________ __________.
______ _____ ____ __________ ___ __________.
________ ________ ____ _________ ______ _________ ____ __________ ________ ____ __________.
____ _____ ___ ___ _______ ____ _______ ________ _______ ________ __________.
______ __________ ____ ____ ______ ______ _____ ________ _______.
___ __________ _________ ____ __________.
____ _______ _______ __________ _______ ___ _____.
________ ________ __________ _____ _____ ________.
________ ____ ________ _____ ______ _____ ______.
________ _____ _________ ____ ___ ______.
__________ _________ ________ _______ __________ ___ ______.
___ ____ __________ __________ ______ ____ _________ ______ ___ __________ __________ __________.
_______ ____ _______ __________ _________ ______ _______ ___ _______.
_______ ____ ________ ________ ___ _____ ___ ____.
________ _______ ________ ____ _________ _________ _______ ___.
___ ____ ________ ________ ____.
__________ __________ __________ _______ ______ _______.
_____ ______ ________ ________ _________ ___ _________ __________ ______.
_____ ____ _________ ____ ________ ____ ________ ____ ______ _______ ________ __________.
_____ ________ ____ ______ _________ ______ ________.
____ _______ _________ __________ _________ _____ _________ ______ _________ _________.
________ ________ _________ ____ ______ __________ _______ _________ ___ ________.
____ ________ ____ ________ _____ __________ ____ __________ _____.
__________ _______ __________ ____ ____ _______ _______ __________ _________.
______ ___ __________ ____ ___ ___.
________ _______ ______ ______ ________ _____ ________ ______ _________ _____ __________.
___ ___ _____ __________ __________ ___ ___.
_____ _______ ______ _________ __________ ______ _____ _____ ________.
_________ _________ ___ __________ ____ _____ ____ ________ __________ _____ _________.
_____ ____ _____ ________ ______ ___.
_____ ________ ____ _______ _________ ____ _____ ___ ______ ________ ______ _____.
_____ _______ ______ ______ _______.
______ _______ _____ ______ __________ ____ ______ _______ __________.
__________ ______ ______ ____ __________ ________ _________ _____.
_____ ______ _______ _________ _____ ______ ___.
____ ________ ________ ____ _____ _______.
_________ ____ _____ _________ ______ _________ _______ ___ ________ ___.
__________ ________ _________ ___ ___ __________ ____ ____ _____ ___ _______ ___.
_______ ____ ___ ____ ________ __________ ___ ______ ________ _____ ____ __________.
________ __________ _______ _______ _______ ________.
______ ___ ______ __________ ___ ___ __________ ____ _____ ________ _________ ______.
_________ ______ ________ __________ ________ _______ ___ _____ __________ ______.
___ _____ _______ ________ ___ _________ ____.
_________ _______ ____ __________ ____ _________ _________ __________ ________ _________ _______ ___.
__________ __________ __________ _____ ___ ___ _______ ________.
________ _____ ______ ________ ____.
________ ________ _____ ____ ______ _______ ___ ____ ___ ___ _________.
_________ _________ __________ ________ ___ _____.
_____ _________ ______ _______ _________.
____ ___ __________ ______ __________ ______ _______.
___ ____ _____ _________ ______ ______.
_________ ________ ________ ____ _________ ________ ____ _______ ____ __________.
____ _______ ________ _____ _________.
________ ___ _______ ________ _________ ________ ____ ____ _____ __________ _____.
________ ______ _____ ____ _____ __________.
_______ ____ _______ _________ _____ ____ ______ _________ __________ _______ ___ _____.
______ ______ _____ ________ _________ ______ _______.
_____ ___ ______ _________ ____ ________ ___ _________ _________ ________.
_____ _____ ________ _______ ________.
______ ________ ________ __________ ____ _________ _______ __________.
__________ __________ _________ _________ ____.
____ _______ _______ ______ _________ _______ __________ ____ __________ ____ ___ ___.
___ _________ _________ _______ _____ __________ ____.
______ ____ ________ __________ ___ __________ ______ ____.
________ ________ _____ __________ ______ __________ ____ _________ _________ __________ __________ ___.
_____ ______ _______ ______ _________ _____ __________ _________ _____ ______.
____ _______ _______ ______ ________ _______ __________ _____ ___ _____ _________ ______.
_________ ____ __________ ________ _____.
_____ _________ _________ ______ __________.
____ _________ ____ ________ _______ __________ __________ ____ _________ _________ ____ ________.
_______ _____ __________ ______ ________ _____.
_____ ____ _______ __________ _______.
_________ _______ ______ ______ _____ ________ __________ _____ _______ ____.
________ ______ __________ __________ __________.
____ _______ ____ __________ _______ ___ ______ _____ __________.
________ _______ ___ _______ ___ ___ ________ ________.
_______ ________ ___ ______ ________ _________ __________ __________ _____ ________ ________ _______.
______ ______ ____ ________ _______ ________ __________ _________ _______ ________.
______ ____ ____ ________ __________ ____ _________ ___ __________ ________.
__________ _________ ______ _____ ________.
____ _____ ___ __________ __________ ______ _________ _______ _____ ___ ______ _______.
__________ ______ ______ ______ ______ _______ _________ _____.
__________ ________ _________ ____ _____ ___ ___ ______.
____ __________ _________ __________ _________ _______.
____ ____ ___ _____ ___ _______ _____ _________ ____.
_____ _____ ______ ___ _____ ______ ____ ___.
_________ _____ _________ ______.
- Solved Assignments
- Study Notes
- Guess Papers
- Question Papers
✓ Unlock up to 60% of the answer
✓ No payment required