Defining the problem as a state space search

Suppose we have a water jug problem:

You are given two jugs , a 4- gallon one and a 3- gallon 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 exact 2 gallons of water into the 4- gallon jug?

The state space for this problem can be described as of ordered pairs of integers (x, y) , such that x=0,1,2,3 or 4 and y=0,1,2 or 3 , represents the number of gallons of water in the 4- gallon jug , and y represents the quantity 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).
The operators to be used to solve the problem can be described as shown in Fig bellow. They are represented as rules whose left side are matched against the current state and whose right sides describe the new state that results from applying the rule.

1- (x,y) (4,y) fill the 4- gallon jug
If x<4
2- (x,y) (x,3) fill the 3-gallon jug
If x<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 the 4-gallon
If x+y>=4 and y>0 jug until the 4-galoon jug is full

8- (x,y) (x-(3-y),3)) pour water from the 4- gallon jug into the 3-gallon
If x+y>=3 and x>0 jug until the 3-gallon jug is full
9- (x,y) (x+y,0) pour all the water from the 3 -gallon jug into
If x+y<=4 and y>0 the 3-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 the 3-gallon jug

11- (0,2) (2,0) pour the 2-gallon from the 3 -gallon jug into
the 4-gallon jug
12- (2,y) (0,x) empty the 2 gallon in the 4 gallon on the ground

Production for the water jug problem

Gallons in the Gallons in the Rule Applied
4- gallon Jug 3- gallon
0 0
0 3 2
3 0 9
3 3 2
4 2 7
0 2 5 or 12
2 0 9 or 11

One solution to the water Jug problem.




















Problem Solving Consist of:

1- data base:
-current states .
-goal .
2- operations:
manipulate knowledge base ( using rules , frames , nets).
3-control strategy
-control strategy
-what to do next
Objective:
To achieve goal by applying a sequence of operations of operations to the initial state .


Example(1):

To find a rout a from a to i
On the following graph
Data base: initial state, root so far, goal , “I”.
Operations: - go from last node visited to on adjacent node



Control strategy: choose an adjacent node to the last visited of random.


Example(2):
Eight tile puzzle
Data base: current state of tile


goal state




Operations: - move hole up or