Search Graphs

Search Graphs: If the search space is not a tree, but a graph, the search tree may contain different nodes corresponding to the same state. It is easy to consider a pathological example to see that the search space size may be exponential in the total number of states.

In many cases we can modify the search algorithm to avoid repeated state expansions. The way to avoid generating the same state again when not required, the search algorithm can be modified to check a node when it is being generated. If another node corresponding to the state is already in OPEN, the new node should be discarded. But what if the state was in OPEN earlier but has been removed and expanded? To keep track of this phenomenon, we use another list called CLOSED, which records all the expanded nodes. The newly generated node is checked with the nodes in CLOSED too, and it is put in OPEN if the corresponding state cannot be found in CLOSED. This algorithm is outlined below:

Graph search algorithm

1. Let fringe be a list containing the initial state
2. Let closed be initially empty
3. Loop if fringe is empty return failure Node -> remove-first (fringe)
4. if Node is a goal
5. then return the path from initial state to Node
6. else put Node in closed
7. generate all successors of Node S
8. for all nodes m in S
9. if m is not in fringe or closed
10. merge m into fringe
11. End Loop

• But this algorithm is quite expensive. Apart from the fact that the CLOSED list has to be maintained, the algorithm is required to check every generated node to see if it is already there in OPEN or CLOSED. Unless there is a very efficient way to index nodes, this will require additional overhead for every node.
• In many search problems, we can adopt some less computationally intense strategies. Such strategies do not stop duplicate states from being generated, but are able to reduce many of such cases.
• The simplest strategy is to not return to the state the algorithm just came from. This simple strategy avoids many node re-expansions in 15-puzzle like problems.
• A second strategy is to check that you do not create paths with cycles in them. This algorithm only needs to check the nodes in the current path so is much more efficient than the full checking algorithm. Besides this strategy can be employed successfully with depth first search and not require additional storage.
• The third strategy is as outlined in the table. Do not generate any state that was ever created before.
• Which strategy one should employ must be determined by considering the frequency of “loops” in the state space.