Notes on Search Algorithms


The description of most of the search algorithms in these notes is taken from J. Pearl, "Heuristics", Addison-Wesley, 1984.

Important issues about Search Algorithms

We will address:
  1. how to write search algorithms. In particular we will examine:
  2. properties of search algorithms and the solutions they find: Let's briefly examine the properties of some commonly used uninformed search algorithms.

    Depth-First Search
    Termination:
    guaranteed for a finite space if repeated nodes are checked. Guaranteed when a depth bound is used. Not guaranteed otherwise.
    Completeness:
    not guaranteed. Guaranteed only if the search space is finite (exhaustive search) and repeated nodes are checked.
    Admissibility:
    not guaranteed.
    Breadth-First Search
    Termination:
    guaranteed for finite space. Guaranteed when a solution exists.
    Completeness:
    guaranteed.
    Admissibility:
    the algorithm will always find the shortest path (it might not be the optimal path, if arcs have different costs).
    Depth-First Search Iterative-Deepening
    Termination:
    guaranteed for finite space. Guaranteed when a solution exists.
    Completeness:
    guaranteed.
    Admissibility:
    the algorithm will always find the shortest path (it might not be the optimal path, if arcs have different costs).

  3. classes of search algorithms. We can classify search algorithms along multiple dimensions. Here are some of the most common:

Description of an Uninformed Search Algorithm:
Depth-First Search with depth bound

1. Put the start node on OPEN.
2. until OPEN is empty or a goal node has been reached
   2.1 remove the topmost node from OPEN and put it on
       CLOSED.  Call this node n.
   2.2 if the depth of n is less than the depth bound 
       then
       2.2.1 expand n, generating all successors (if any).  
       2.2.2 if any of these successors is already on 
             the traversal path discard it
       2.2.3 if any of these successors is a goal node, 
             exit 
       2.2.4 put the successors on top of OPEN and 
             provide for each a pointer back to n
       else
       2.2.5 clean up CLOSED.
3. If a goal node is found, 
   then exit with the solution obtained by tracing back 
        through its pointers 
   else announce failure.
Notes:

Description of an Informed Search Algorithm
Best-First Search

The term best-first search is used in different ways by different authors. The Russell and Norvig textbook calls best-first search any algorithm that sorts the nodes according to some function and selects the best each time. Judea Pearl has a somewhat different definition of best-first, which is given here. The major difference is in the specification of how to handle nodes already seen (Russell and Norvig do not specify what to do) and in when goal test is done (Russell and Norvig in Graph-Search check for goal only on the first element of OPEN, Pearl checks as soon as the successors of a node are generated).
1. Put the start node S on OPEN.
2. until OPEN is empty or a goal node has been reached
   2.1 remove from OPEN a node at which f is minimum (break 
       ties arbitrarily) and put it on CLOSED.  Call this 
       node n.
   2.2 expand n, generating all successors (if any).
   2.3 if any of the successors of n is a goal node, exit.
   2.4 for each successor n' of n
       2.4.1 calculate f(n')
       2.4.2 if n' was neither on OPEN nor CLOSED, add it to 
             OPEN.  Attach the cost f(n') to it.
       2.4.3 if n' was already on OPEN or on CLOSED compare
             the new value f(n') with the previously assigned
             value f(n').  If the old value is lower discard 
             the newly generated node.  If the new value is 
             lower, substitute the new node for the old node.  
             If the old node was on CLOSED move it back to 
             OPEN.
3. If a goal node is found, 
   then exit with the solution obtained by tracing back 
        through pointers
   else announce failure.
Notes:

A*

1. Put the start node S on OPEN.  Attach to s the cost 
   g(s) = 0.  Initialize CLOSED to the empty queue.  
2. until OPEN is empty or a goal node has been reached
   2.1 remove from OPEN a node at which f is minimum 
       (break ties arbitrarily) and put it on CLOSED.  
       Call this node n.
   2.2 if n is a goal node, exit.
   2.3 expand n, generating all successors (if any).
   2.4 for each successor n' of n
       2.4.1 calculate f(n')= g(n') + h(n')
                            = g(n) + c(n,n') + h(n').
       2.4.2 if n' was neither on OPEN nor CLOSED, add 
             it to OPEN.  Attach the cost f(n') to it.
       2.4.3 if n' was already on OPEN or on CLOSED 
             direct its pointers along the path yielding 
             the lowest g(n') and keep the lowest f(n').
       2.4.4 if n' required pointer adjustment and was 
             found on CLOSED, move it back to OPEN.
3. If a goal node is found, 
   then exit with the solution obtained by tracing back 
        through its pointers
   else announce failure.
Notes:

Iterative-Deepening A* (IDA*)

IDA* is similar to Depth-First Iterative-Deepening, the difference being the cutoff criteria. A path is cutoff when its total cots f(n) exceeds a cost threshold. IDA* starts with a threshold equal to f(s) (which is equal to h'(s) since g(s) = 0). Each iteration is a depth-first search, cutting off a branch when its f(n) value exceeds the threshold. If a solution is found, the algorithm terminates. Otherwise, the threshold is increased to the minimum f value that exceeded the previous threshold and another depth-first search is started from scratch. This continues until a solution is found.
Time Complexity:
depends on the accuracy of the heuristic function. If the heuristic function is exact IDA* runs in linear time, if the heuristic function is useless, the time complexity is exponential (as for uniform cost).
Space Complexity:
O(d)

Heuristic functions

Examples of heuristic functions for the 8-puzzle

In the 8-puzzle problem 8 differently numbered tiles are fitted into 9 spaces on a 3x3 grid. One space has no tile (we call it blank) so that any tile adjacent to the empty space can be moved to occupy it by sliding from its original position. For instance, here is an initial and a goal state:
initial state           goal state
2   8   1		1   2   3
4      	6		8       4
7   5   3		7   6   5
Here are some different heuristic functions: Here is an example of how to compute these heuristics for the initial configuration shown above. The value of R(n) is 0 because there are no direct tile reversals.
P(n) = S(n) =
1 + (2 is 1 position away from goal position) 2 + (2 not followed by its successor)
2 + (8 is 2 positions away from goal position) 0 + (8 followed by its successor)
2 + (1 is 2 positions away from goal position) 2 + (1 not followed by its successor)
2 + (6 is 2 positions away from goal position) 2 + (6 not followed by its successor)
2 + (3 is 2 positions away from goal position) 2 + (3 not followed by its successor)
1 + (5 is 1 position away from goal position) 2 + (5 not followed by its successor)
0 + (7 is 0 position away from goal position) 2 + (7 not followed by its successor)
2 = (4 is 2 positions away from goal position) 2 = (4 not followed by its successor)
12 14
The blank tile does not count even if it is not in its goal position. In this case the center tile is blank so we do not add to S(N)1 for it. If we had the blank tile on the border it would not affect the sequence number because to compute the sequence number you look only at the numbered tiles.