A
Water Jug Problem: You are given two Jugs, a 4-gallon one and a
3-gallon one. Neither have any measuring markers on it. There is a
pump that can be used to fill the jugs with water. How can you get
exactly 2 gallons of water into the 4-gallon jug?
The state space for this problem can be described as the set of ordered pairs of integers (x, y), such that x=0, 1,2,3, or 4 and y = 0,1,2, 0r 3; x represents the number of gallons of water in the 4-gallon jug, and y represents the quality of water in the 3-gallon jug. The Start State is (0,0). The goal state is (2,n) for any value of n (since the problem does not specify how many gallons need to be in the 3-gallon jug).
1 (x, y) If x < 4 -> (4,y) Fill the 4-gallon jug.
2. (x, y) If y < 3 -> (x,3) Fill the 3-gallon jug.
3 (x, y) If x >0 -> (x – d, y) Pour some water out of the 4-gallon jug
4 (x, y) If y > 0 -> (x, y - d) pour some water out of the 3-Gallon jug
5 (x, y) If x > 0 -> (0, y) Empty the 4-gallon jug on the ground
6 (x, y) If y > 0 -> (x, 0) Empty the 3-gallon jug on the ground
7 (x, y) If x + y> 4 and y > 0 -> (4,y – (4 -x)) ;pour some water from the 3-Gallon jug in to the
4 - gallon jug until the 4 -gallon jug is full.
8 (x, y) If x + y> 3 and x > 0 -> (x-(3-y),3) ;pour water from the 4 -Gallon jug in to the
3 -gallon jug until the 3 -gallon jug is full.
9. (x, y) If x + y <4 and y > 0 -> (x+y,0) ;pour all the water from the 3-Gallon jug in to the
4- gallon jug
10 (x, y) If x + y < 3 and x > 0 -> (x+y,0) ;pour all the water from the 4-Gallon jug in to the
3- gallon jug
11 (0,2) -> (2,0) ;pour all 2 gallons from the 3-Gallon jug in to the
4-Gallon jug.
12. (2,y) -> (0,y) ;Empty the 2 gallons in the 4.gallons in the 4-gallon jug on the
Ground.
Production rules for the water jug problem.
Gallons of water in the 4-gallon jug. Gallons of water in the 3-gallon jug Rule Applied
0 0 2
0 3 9
3 0 2
3 3
4 2 7
0 2 5 0r 12
2 0 9 or 11
One solution for the water jug problem.
0 0 2
4 0 1
1 3 8
1 0 6
0 1 10
4 1 1
2 3 8
2 0 6
Second solution for the water jug problem
The state space for this problem can be described as the set of ordered pairs of integers (x, y), such that x=0, 1,2,3, or 4 and y = 0,1,2, 0r 3; x represents the number of gallons of water in the 4-gallon jug, and y represents the quality of water in the 3-gallon jug. The Start State is (0,0). The goal state is (2,n) for any value of n (since the problem does not specify how many gallons need to be in the 3-gallon jug).
1 (x, y) If x < 4 -> (4,y) Fill the 4-gallon jug.
2. (x, y) If y < 3 -> (x,3) Fill the 3-gallon jug.
3 (x, y) If x >0 -> (x – d, y) Pour some water out of the 4-gallon jug
4 (x, y) If y > 0 -> (x, y - d) pour some water out of the 3-Gallon jug
5 (x, y) If x > 0 -> (0, y) Empty the 4-gallon jug on the ground
6 (x, y) If y > 0 -> (x, 0) Empty the 3-gallon jug on the ground
7 (x, y) If x + y> 4 and y > 0 -> (4,y – (4 -x)) ;pour some water from the 3-Gallon jug in to the
4 - gallon jug until the 4 -gallon jug is full.
8 (x, y) If x + y> 3 and x > 0 -> (x-(3-y),3) ;pour water from the 4 -Gallon jug in to the
3 -gallon jug until the 3 -gallon jug is full.
9. (x, y) If x + y <4 and y > 0 -> (x+y,0) ;pour all the water from the 3-Gallon jug in to the
4- gallon jug
10 (x, y) If x + y < 3 and x > 0 -> (x+y,0) ;pour all the water from the 4-Gallon jug in to the
3- gallon jug
11 (0,2) -> (2,0) ;pour all 2 gallons from the 3-Gallon jug in to the
4-Gallon jug.
12. (2,y) -> (0,y) ;Empty the 2 gallons in the 4.gallons in the 4-gallon jug on the
Ground.
Production rules for the water jug problem.
Gallons of water in the 4-gallon jug. Gallons of water in the 3-gallon jug Rule Applied
0 0 2
0 3 9
3 0 2
3 3
4 2 7
0 2 5 0r 12
2 0 9 or 11
One solution for the water jug problem.
0 0 2
4 0 1
1 3 8
1 0 6
0 1 10
4 1 1
2 3 8
2 0 6
Second solution for the water jug problem
No comments:
Post a Comment