Water Jug Problem in Artificial Intelligence – State Space Search
Water Jug Problem Definition,
“You are given two jugs, a 4-liter one and a 3-liter one. Neither has 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 liters of water into a 4-liter jug.”
Video Tutorial:
Representation of water Jug Problem in terms of state-space search,
State: (x, y)
where x represents the quantity of water in a 4-liter jug and y represents the quantity of water in a 3-liter jug.
That is, x = 0, 1, 2, 3, or 4 y = 0, 1, 2, 3
Start state: (0, 0).
Goal state: (2, n) for any n.
Here need to start from the current state and end up in a goal state.
Production Rules for Water Jug Problem in Artificial Intelligence
| 1 | (x, y) is X<4 ->(4, Y) | Fill the 4-liter jug |
| 2 | (x, y) if Y<3 -> (x, 3) | Fill the 3-liter jug |
| 3 | (x, y) if x>0 -> (x-d, d) | Pour some water out of the 4-liter jug. |
| 4 | (x, y) if Y>0 -> (d, y-d) | Pour some water out of the 3-liter jug. |
| 5 | (x, y) if x>0 -> (0, y) | Empty the 4-liter jug on the ground |
| 6 | (x, y) if y>0 -> (x,0) | Empty the 3-liter jug on the ground |
| 7 | (x, y) if X+Y >= 4 and y>0 -> (4, y-(4-x)) | Pour water from the 3-liter jug into the 4-liter jug until the 4-liter jug is full |
| 8 | (x, y) if X+Y>=3 and x>0 -> (x-(3-y), 3)) | Pour water from the 4-liter jug into the 3-liter jug until the 3-liter jug is full. |
| 9 | (x, y) if X+Y <=4 and y>0 -> (x+y, 0) | Pour all the water from the 3-liter jug into the 4-liter jug. |
| 10 | (x, y) if X+Y<=3 and x>0 -> (0, x+y) | Pour all the water from the 4-liter jug into the 3-liter jug. |
| 11 | (0, 2) -> (2, 0) | Pour the 2-liter water from the 3-liter jug into the 4-liter jug. |
| 12 | (2, Y) -> (0, y) | Empty the 2-liter in the 4-liter jug on the ground. |
The solution to Water Jug Problem in Artificial Intelligence
1. Current state = (0, 0)
2. Loop until the goal state (2, 0) reached
– Apply a rule whose left side matches the current state
– Set the new current state to be the resulting state
(0, 0) – Start State
(0, 3) – Rule 2, Fill the 3-liter jug
(3, 0) – Rule 9, Pour all the water from the 3-liter jug into the 4-liter jug.
(3, 3) – Rule 2, Fill the 3-liter jug
(4, 2) – Rule 7, Pour water from the 3-liter jug into the 4-liter jug until the 4-liter jug is full.
(0, 2) – Rule 5, Empty the 4-liter jug on the ground
(2, 0) – Rule 9, Pour all the water from the 3-liter jug into the 4-liter jug.
Goal State reached
Another solution to Water Jug Problem in Artificial Intelligence
(0, 0) – Start State
(4, 0) – Rule 1, Fill the 4-liter jug
(1, 3) – Rule 8, Pour water from the 4-liter jug into the 3-liter jug until the 3-liter jug is full.
(1, 0) – Rule 6, Empty the 3-liter jug on the ground
(0, 1) – Rule 10, Pour all the water from the 4-liter jug into the 3-liter jug.
(4, 1) – Rule 1, Fill the 4-liter jug
(2, 3) – Rule 8, Pour water from the 4-liter jug into the 3-liter jug until the 3-liter jug is full.
Goal State reached
Summary
This article discusses Water Jug Problem in Artificial Intelligence – State Space Search. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.