For every node that Simple Search 1 picks to inspect, many more are added in the bag. In mathematical terms the search tree generated by the program grows exponentially like Hercules demonstrated in his fight with hydra.
Simple Search 1 picks a node and from OPEN and checks if the goal
- If yes it returns the node N
- If no it had for children of N to OPEN.
There are two problems with the above program. The first is that the program could go into an infinite loop. This would happen when the state space is a graph with loops in which it would be possible to come back to the same state.
The algorithm given below shows simple search 1.
The Algorithm for Simple Search 1:
SimpleSearch()
open- { start }
while open is not empty
do pick some node n from open
open - open \ (n)
if GoalTest (n) = TRUE
then return n
else open - open U moveGen(n)
return Failure
One possible evolvement of OPEN is shown here . The node picked at each stage is bold.
(S)
(ABC)
(SACD)
(ABCACD)
(SACACDACD)
Simple Search 2
In simple search 2 algorithm it incorporates a check that is it does not add any seen nodes to OPEN again. To prune the search tree further one could also specify that it does not add any successor that are already on OPEN as well.
This would lead to a smaller search tree in which each node occurs exactly once . It maintains a list of seen nodes in a list called CLOSED .It contacts the list of states we have tested and should not visit again.
Simple search 2 picks some node from OPEN and adds it to CLOSED.
If N is goal ,it returns N, and else it adds unseen Successors of N to OPEN. The CLOSED list is shown by shaded notes and the OPEN list is shown by the dotted circles.
The Algorithm used for Simple Search 2 :
SimpleSearch2()
open - {start}
closed -{}
while open is not empty
do Pick some node n from open
open - open \ {n}
closed - closed U {n}
if GoalTest {n} =TRUE
then return n
else open - open U{MoveGen {n} \ closed }
return FAILURE
The search tree formed by SS2 is as follows :
OPEN CLOSED
(S) ()
(ABC) (S)
(BCE) (SA)
(CDE) (SAB)
(CGE) (DABS)
In simple search 2 , the tree is terminated when the goal G is picked and found.
The approach used for the given problem is shown here using Simple Search 2.
The solution is as follows :
Simple search 2 picks G from OPEN and terminates.
Drawbacks
Simple search 2 program returns the goal state when it finds which is not suitable for Configuration problems and in Planning problems.
Configuration Problems : They are the problems interested in finding a state satisfying some properties .Example - N-Queens Problem.
Planning problems : They are the problems in which sequence of moves for the path to the goal state.
Simple Search 3
Simple search 3 incorporates the drawbacks of simple search 2 after picking the node from OPEN, it extracts the current state H.
It tests with goalTest and generates its successors using moveGen. When the goal node is found, all that the algorithm needs to do is to reverse the road to get the path in the proper order.
The algorithm used for Simple Search 3:
SimpleSearch3()
open -{{start} }
closed - { }
while open is not empty
do pick some node n from open
h- Head(n)
if GoalTest (h) = TRUE
then return Reverse(n)
else closed - closed U {h}
successors - { MoveGen (h) \ closed }
successors - { successors \ Mapcar(open) }
open - { open \ { n } }
for each s in successors
do Add Cons (s, n) to open
return FAILURE
In simple search 3 , the information of the entire path is maintained at each node on OPEN in the search tree .
For the given same problem above , the search tree formed by the SS3 is as follows :
OPEN CLOSED
((S)) ()
((AS)(BS)(CS)) (S)
((BS)(CS)(EAS)) (AS)
((CS)(DBS)(EAS)) (BAS)
((CS)(GDBS)(EAS)) (DBAS)
In simple search 3 , same like SS2 the search tree is terminated as soon as the goal is picked .
But , here program finally reverses the path and returns SBDG, which is the desired path from S to G.
The function mapcar list an argument and returns a list containing the heads of the input lists. The function cons adds a new element to the head of a list.
In simple search 3, OPEN contains paths and CLOSED contains states. Next, we modify our search function such that both OPEN and CLOSED store node pairs representing a node and its parent node in the search tree . Now, all nodes in the search tree have the same structure. We will, however, need to do more work to return the path found .
Every node visited has its own back pointer to its consisting Parent Node.The algorithm reconstructPath used below reconstructs the path tracing this at pointers until it reaches the start node which has NIL has back pointer.
ReconstructPath (nodePair, closed)
path - List( Head ( nodePair))
parent- Second (nodePair)
while parent is not NIL
do path - Cons(parent, path)
nodePair - FindLink(parent, closed)
parent - Second(nodePair)
return path
FindLink(child, closed)
if child = Head(Head (closed) )
then return Head(closed)
else return FindLink (child, Tail (closed) )
No comments:
Post a Comment