Sunday, 11 September 2016

Problem Space in Artificial Intelligence

A problem in space in that can be generated by the application on any combination of objects the problem in space contains one or more

  • State Space :- A state space is the set of all states reachable from initial state.
Example :- Water-Jug Problem
There are two jugs one is 4 gallon and another is 3 gallon jugs one neither have any meaning maker on it there there is pump that can be user to fill the jugs with water how can you get exactly two gallons of water into the four gallon jug. 
                                      State Space
                                       (x.y)        x---->4 gallon jug
                                                       y----->3 gallon jug
x=0,1,2,3,4
y=0,1,2,3

initial state (0,0)
goal state (2,n)

Production Rules for Water-Jug Problem :-
  • (x,y) ---> (4,y)                                                  Fill 4 gallon jug
  • (x,y) ---> (x,3)                                                   Fill 3 gallon jug
  • if x>0 ,(x,y) ---> (x-d,y)                                    Pour some water out of 4 gallon jug on the ground
  • (x,y) ---> (x,y-d)                                                Pour some water out of 3 gallon jug on the ground
  • if x>0, (x,y) ---> (0,y)                                        Empty the 4 gallon jug on the ground
  • if y>0, (x,y) ---> (x,0)                                        Empty the 3 gallon jug on the ground
  • if (x+y)>=4 and y>0, (x,y) ---> (4,y-(4-x))        Pour water from 3 gallon jug into 4 gallon jug until it fulls
  • if (x+y)>=3 and x>0, (x,y) ---> (x-(3-y),3)       Pour water from 4 gallon jug to 3 gallon jug
  • if (x+y)<=4 and y>0, (x,y) ---> (x+y,0)            Pour all the water from 3 gallon jug to 4 hallon jug
  • if (x+y)<=4 and x>0, (x,y) ---> (0,x+y)            Pour all the water from 4 gallon jug to 3 gallon jug
  • (0,2) ---> (2,0)                                                   Pour the 2 gallon water from 3 gallon jug to 4 gallon jug
  • (2,y) ----> (0,y)                                                  Empty the 2 gallon jug in the 4 gallon jug
Solution Set :-

4 Gallon jug                       3 Gallon jug                        Rules Applied
        0                                        0                                         Rule 2
        0                                        3                                         Rule 9
        3                                        0                                         Rule 2
        3                                        3                                         Rule 7
        4                                        2                                      Rule 5 or Rule 11
        0                                        2                                       Rule 9 or Rule 11
        2                                        0                                      Rule 9  or Rule 11     
                         




No comments:

Post a Comment