Water Jug Problem in AI
Water Jug Problem is the state space representation.
A problem solving operator uses an operator which works to produce a new state in the knowledge base and is said to represent problems in a state -space.
Means , A set of all possible states of a given problem is known as the state space of the problem.
Consider, You are given two jugs, one is 4- gallon and another is 3- gallon . Neither has any measuring markers on the jug. There is a pump that can be used to fill the jugs with water. How can we get exactly two gallons of water into the four-gallon jug?
The state space for this problem can be described as the set of ordered pairs of integers (x,y)
Such as x= 0,1,2,3 or 4
y= 0,1,2 or 3
x is the number of gallons of water in the four-gallon jug and y the quantity of water in the three-gallon jug.
Start state =(0,0)
The goal state =(2,n) , n is any possible value.
As the problem does not specify how many gallons need to be filled in the 3 gallon jug.
1. (x,y) (4,y) Fill the 4-gallon jug
if x < 4
2. (x,y) (x,3) Fill the 3-gallon jug
if y<3
3. (x,y) (x-d,y) Pour some water out of the 4 gallon jug
if x>0
4.(x,y) (x,y-d) Pour some water out of the 3 gallon jug
if y>0
5. (x,y) (0,y) Empty the 4- gallon jug on the ground.
if x>0
6. (x,y) (x,0) Empty the 3- gallon jug on the ground.
if y>0
7. (x,y) (4, y-(4-x)) Pour water from the 3 -gallon jug into
if x+y>=4 and y>0 the 4- gallon jug until the 4 gallon jug is full
8.(x,y) (x-(3-y),3) Pour water from the 4 -gallon jug into
if x+y >=3 and x>0 the 3- gallon jug until the3 gallon jug is full
9. (x,y) (x+y,0) Pour all the water from the 3 gallon jug into 4
if x+y <=4 and y>0 gallon jug
10. (x,y) (0,x+y) Pour all the water from the 4 gallon jug into
if x+y <=3 and x>0 3 gallon jug
11. (0,2) (2,0) Pour the 2 gallons from the 3 gallon jug
into the 4 gallon jug.
12. (2,y) (0,y) Empty the 2 gallons in the 4 gallons jug
on the ground.
fig: Production Rules for the water jug problem
To solve the water jug problem , wee need the problem description given above, is a control structure which loops through a simple cycle in which some rule whose left side matches the current state is chosen, the appropriate change to the state is made as described in the corresponding right side and resulting sate is checked it is goal state or not.
Following is the one of the solution of the water jug problem
4 Gallon jug 3 Gallon Jug Rule Applied
0 0 2
0 3 9
3 0 2
3 3 7
4 2 5 or 12
0 2 9 or 11
2 0
Fig: One solution to the water jug problem
Hi. I’m Designer of Blog Magic. I’m CEO/Founder of ThemeXpose. I’m Creative Art Director, Web Designer, UI/UX Designer, Interaction Designer, Industrial Designer, Web Developer, Business Enthusiast, StartUp Enthusiast, Speaker, Writer and Photographer. Inspired to make things looks better.
0 comments:
Post a Comment