State Space Search: Generate and Test

Generate and Test is an approach which is used to search for the state space which is used for solution. This high level search algorithm has two components -One , is to generate a candidate from the state space and Another , is to test whether the generated  candidate is the solution or not.

Algorithm used for Generate and Test ()

  Generate and Test()

  while more candidates exist

    do Generate a candidate

     Test whether it is a solution

return FAILURE

We assume that there is any problem domain that has any functions defined which allows us to operate in the domain. So ,we need two functions to be defined in the domain.

They are as follows:

moveGen(State) : It takes a state as input and returns a set of states that are reachable in one step from the input state. We call the set of states as successors or children of the input state , which is the parent of the children.

goalTest(State) : It Returns true if the input state is the goal state and false otherwise .

goalTest(State, Goal) : It returns true if state matches goal and false otherwise.

 Let us look at an example of river-crossing puzzle. In this a group of entities need to cross the river, but all of them cannot cross at the same time due to the limited capacity of the boat or the bridge. In addition there may be constraints which restrict the combination of entities which can stay in one place.

So, there are 3 missionaries and 3 cannibals who want to cross the river. There is a boat with a capacity to seat two.  They are as follows:

  MAN, LION, GOAT , CABBAGE

A man(M) needs to transport a lion(L) , a goat(G), and a cabbage(C) across a river. He has a boat(B) in which he can take only  one of them at a time. It is only his presence that prevents the lion from eating the goat and the goat from eating the cabbage. How can he take them all across the river?

Let us say that we represent the state as a list of two lists, one for each bank of the river, say the left bank L and the righty bank R .

         Start state S = (( M G L C B ) ())

         Goal state G = (() ( M G L C B ))

The move generation could first generate all possible moves and then filter out illegal moves .

((  G L C ) ( M B )) , (( L C ) (M G  B)) , (( G C ) ( M L B )) and ( (G L) (M C B)) , only the second state , (( L C ) (M G  B)) is a legal state .

The moveGen has transferred some elements from the first list to the second . In the next move , it will need to transfer elements , in the opposite direction . Also, there is redundant information in the representation.

 When one knows what is on the left bank, one also knows what is on the right bank. Therefore one of the lists could be removed.

                   Start state S = ( M L G C Left )

                  Goal state G = ( M L G C Right)

Initialize set of successors C to empty set.

Add M to the compliment of given state N to get new state S.

If given state has Left , then add Right to S else add Left.

If legal (S) then add S to set of successors C for each other entity E in N

Make a copy S’ of S

Add E to S’

If legal (S’), then add S’ to C

Return (C)

The complement of state is with respect to the set { M L G C} .