| 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:
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.
The algorithm assumes that we have some sort of data structures and functions to represent search states and operators. In particular:
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:
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.
(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.