We assume that you have read carefully the formal statement of the problem and that you have practiced a bit your basic skills in this area so that you are also familiar with our color scheme, that is
3 oz
|
5 oz
|
8 oz
|
In other words, we are given three mugs:
- An 8 oz Red mug
- A 5 oz Blue mug
- Gray for the 3 oz mug
The Red mug is full of beer.
Our mission in life is to devise a pouring scheme that will produce 4 oz of beer in the Red and Blue mugs, like this:
3 oz
|
5 oz
|
8 oz
|
We begin our analysis of this problem with a very simple observation with regard to the beer pouring process: to describe the dynamics of the pouring process we need a state variable of the form:
s=(g,b,r)
where:
- g = volume of beer in Gray
- b = volume of beer in Blue
- r = volume of beer in Red
Observe, however that because the total volume of beer is fixed (8 oz) it is only necessary to know how much beer is currently stored in any two mugs. The volume in the third mug is equal to 8 less the total volume in the two designated mugs.
It will be convenient to use the two small mugs for this purpose. Thus, we shall describe the dynamics of the beer pouring process by a pair of numbers s=(g,b) where g represents the volume of beer in the gray mug and b represents the volume of beer in the blue mug. The possible values of g are {0,1,2,3} and of b are {0,1,2,3,4,5}.
For example, s=(1,5) represents the situation where there is 1 oz of beer in the Gray mug, 5 oz of beer in the Blue mug and 2 oz of beer in the Red mug. In particular, the initial state of the process is s=(0,0) and the final state is s=(0,4).
Furthermore, conveniently, all the feasible states are contained in the following grid:
| b | ||||||||||||||||||||||||||||||||||||
| g |
|
The bottom line question is then: what sequence of (feasible) actions (pourings) will transform the process from the initial state s=(0,0) to the desired state s=(0,4)?
We shall not address this question in full in this preliminary analysis. We shall focus on the feasibility issue. In other words, our objective here is to determine what kind of actions (pourings) are feasible for any given state of the process.
We shall represent an action by a pair (i,j) and interprete it as follows: the first element of the pair (i) is the mug from which we pour the beer and the second element (j) is the mug to which we pour the beer. Thus, a=(Red,Gray) represents the action "pour beer from the Red mug to the Gray mug".
But how much beer can we actually pour with this action?
To keep thinks simple, we do not allow mock pouring so we decree: though shalt pour only strictly positive volumes of beer! That is, action (i,j) is not allowed if mug i is empty.
We shall also be very strict about keeping the place nice and clean, so we decree: Thou shalt not pour unto mug j more than its capacity can handle without spilling! That is, we have to comply with the following restriction: the amout we pour into mug i should not exceed C(j)-v(j), where C(j) is the capacity of mug j and v(j) is the volume of beer currently contained in mug j. For example, if say mug Gray currently contains 1 oz of beer, then we are not allowed to pour into it more than 2=3-1 oz of beer.
In summary, action (i,j) is feasible if and only if:
- v(i) > 0
- C(j) > v(j)
Obviously, if action (i,j) is feasible then the amount we pour from mug i to mug j is equal to min(v(i),C(j)-v(j)).
Use the following interactive state transition matrix to test your skills in determining the actions pertaining to each of the states of the process. Note that we use the term child in this context to describe a state that can be generated (in one transition) from the current state.
|
Click a cell coresponding to the state s= (g,b) you want to examine. |
|
This table displays the set of all feasible actions associated with the state you selected above. |
|||||||||||||||||||||||
In case you cannot figure out how this works consider the state s=(0,0) as an example. If you click on this cell in the sky-blue table, two things will happen:
Two cells, namely (3,0) and (0,5) , of the sky-blue matrix become green. These are the feasible children of the state (cell) you selected (which now is painted black).
- Two cells, namely (Red,Gray) and (Red, Blue), in the white table become green. These cells represent the feasible actions associated with the chosen state. The numbers in these cells represent the volumes to be poured. In the case of the state s=(0,0), the actions are (Red,Gray) and (Red,Blue) and the respective volumes are 3 and 5.
We are almost ready now for a bit of a DP perspective on the problem. But before we move there, let's try to solve the problem by trial and error or guessing. For this purpose we prepared for you a simple device that you can use to generate a sequence of feasible decisions. Try it!
This brings to an end our preliminary analysis of the problem. We are ready to have a quick look at DP's approach to this problem.
