General Graph Search Algorithm

The following is a general graph searching procedure.

Key Features

  • \(b \rightarrow \) breadth/average branching factor

  • \(d \rightarrow \) depth

  • Time Complexity: \(O(b^d)\)

  • Space Complexity: \(O(b^d)\)

  • OPEN list - contains the nodes which are to be visited.

  • CLOSED list - contains the nodes which have been visited and their children nodes have been discovered.

As the search proceeds, more and more of the implicitly defined state space gets explicit.

Search might reach the same node n along different paths.

The Algorithm

  1. Create a search graph, \(G\) consisting solely of the start node \(s\). Put \(s\) on a list called OPEN. The OPEN list will consist of nodes that need to be explored

  2. Create a list called CLOSED that is initially empty The CLOSED list will keep track of nodes that are already explored/visited

  3. LOOP: If OPEN is empty, exit with failure

  4. Select the first node from OPEN, remove it from OPEN and put it on CLOSED. Call this node \(n\).

  5. If \(n\) is a goal node, exit successfully with the solution obtained by tracing a path along the pointers from \(n\) to \(s\) in \(G\).

    Arcs are created in step 7

  6. Expand node \(n\), generating a set \(M\) of its successors and install them as successors of \(n\) in \(G\).

  7. Establish a pointer to \(m\) from those members of \(M\) that were not already in \(G\) (i.e. not already on either OPEN or CLOSED)

    1. Add these members of \(M\) to OPEN

    2. For each member of \(M\) that was already on OPEN or CLOSED, decide whether or not to redirect its pointer to \(n\)

    3. For each member of \(M\) already on CLOSED, decide for each of its descendants in \(G\) whether or not to redirect their pointers to \(n\).

  8. Reorder the list OPEN, either according to some arbitrary scheme or according to heuristic merit.

  9. Goto LOOP

Static

Theorem: Termination of GRAPHSEARCH

GRAPHSEARCH always terminates for a finite graph.

The GRAPHSEARCH algorithm always terminates in step 3 or step 5. Notice that in every loop of the algorithm, a node is removed from the OPEN list and that only a finite number of new successors are added to OPEN.

For finite graphs, we ultimately run out of new successors and thus, unless the algorithm terminates successfully in step 5 by finding a goal node, it will terminate in step 3 after eventually depleting OPEN.

Therefore, the algorithm always terminates for finite graphs.

← Previous: Backtracking Strategies | ↑ Up: Advanced Artificial Intelligence | Next: Heuristic Search Procedure →