Implementing Searches

Contents: A General Search Algorithm - Stacks and Queues

Recall from the previous lecture the diagrams of the order in which search states are considered for Breadth-First and Depth-First Search:

In Breadth-First search, all of the states at a given level are considered before any of the states at the next level:

In Depth-First search, states that result from applying operators to a state are considered immediately:

To implement these search techniques as programs we need ways to make sure that the programs perform as the abstract characterization of the technique requires.

This could be done by having the program create something like these diagrams, and using marks or something in the diagram to keep track of which states to explore next. However this approach is less efficient (and in fact much more complicated) than some alternatives.

To implement a breadth first search or a depth first search correctly, we need to provide an algorithm for which we can demonstrate that the states are explored in the right order.

A General Search Algorithm

I will describe a general abstract search algorithm that be specialized to implement a number of different search algorithms, including Breadth-First and Depth-First search.

The algorithm assumes that we have some sort of data structures and functions to represent search states and operators. In particular:

  • A predicate that tests whether the given state is a solution in the problem domain.
  • A predicate that tests whether the operator can be applied to the state.

  • A function that creates a representation of the new state that results from applying the indicated operator in the given state. If the operator is not applicable in the state, the result of this function is undefined.

    I also assume that we have some kind of data structure that can be used to collect states. I will call this set a "bag" for now, and describe the general algorithm in terms of the operations that can be defined on a bag:

  • A way to create an instance of a bag with no states stored in it.

  • A predicate to test if a bag is enpty.

  • A function that stores a new item into a bag. Depending on how bags are implemented, this operator will either return a new bag, or modify the existing one.

  • A function that returns one of the items in a bag, and modifies the bag so that the item is removed.

    The specific item returned by this function is not yet defined. As we will see, by changing the order in which items are removed from the bag, we can implement many different search algorithms.

    We can now define a general search algorithm as follows:

       1.1 Make a "bag" containing the initial state.
         2.1 If the bag of states is empty, the search fails.
         2.2 Otherwise, remove a state from the bag.
         2.3 If that state achieves the goal, the search succeeds.
         2.4 Loop through the set of operators:
          3.3 If the operator applies to the state,
               apply the operator and add the resulting state to the bag.
         2.5 Continue at step 2.1.

    The idea is that states that are going to be considered are kept in the bag. As states are removed from the bag, they are checked to see if they achieve the goal. If so, the search is done. If not, each operator is examined to see if it can be applied to the state, and if so, the new state that results is added to the bag. If the bag ever becomes empty, it means that we have examined all possible states and have not found a solution.

    A number of optimizations could be applied to this general algorithm. For example it might be reasonable to add a check that a state isn't being added to the bag that is already in there, or that has already already been considered. It is also probably a good idea to check that the new_state is a goal state before adding it to the bag - it is sort of silly to put a success state into the bag because we just have to wait until it is removed.

    Stacks and Queues

    To implement Breadth-First or Depth-First search, we need to make sure that the states are considered in the right order. If you look back at the diagram for Breadth-First search, the states could be examined in the order that they are labeled:
    (A B C D E F G H I J)
    (As I mentioned, I didn't draw the blue line this way, but this order would be a legitimate Breadth-First search.)

    Notice that the order that the states are to be corresponds to the order that they are created. This suggests that for breadth-first search, we want to consider states in the same order that they are created.

    In computer science, a data structure called a "queue" is used for this purpose. The idea of a queue is like a line at the bank or somewhere else you wait in lines. The first person who shows up is waited on, and the next person has to wait behind. If any other people show up while the first one is being served, they have to wait behind each other. (I'm pretty sure that this is obvious.) In any case, the order that people are served is the same as the order that they show up, unless there are some brutes who push their way ahead.

    If we could implement a data structure in which items are removed in the same order that they are added (i.e., a queue), we could use the above general search algorithm to implement Breadth-First search. We would just make the "add to bag" operator insert the item to the end of the queue, and define the "remove from bag" operator to remove and return the first item in the queue.

    To implement a Depth-First search, we need to make sure that when operators are applied to a state, the resultant states are considered immediately, but that the other states that we have previously created are considered later, if the news one lead to failure states.

    In this case, what we want is that the new states go to the front of the line, and that the other states stay where they are, in case they need to be considered later.

    Computer scientists use the term "stack" to refer to a data structure for storing items such that the last thing stored into the stack is the first thing retrieved. The idea of the name is that when you put a new item on the stack it goes on the "top" and pushes all the rest down, like plates in a cafeteria. All of the other plates are still there, but the first one that you grab is the last one that was put there. When you take one from the top, the rest pop up and can be removed next - unless some other ones are put on top of them.

    So to implement a Depth-First search, we need only define the bag addition and removal functions in terms of a stack.

    As we will see later, in the discussion of "heuristic search", we can also rearrange the items in the bag so that the ones that are most likely to succeed are at the front.