CogSci 108b Lecture Notes
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.
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. In
LISP, an "empty bag" is almost surely going to be implemented with
nil
.
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.
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.
Lists can be used to implement queues and stacks fairly easily. In
this discussion I assume that we will keep our states in a global
variable called "states". For both stacks and queues, the "empty bag"
of states will be represented with nil. So we could initialize our
search with:
datum * queue = NULL;
Implementing stacks with lists is easy. The "cons" function will be
our "add to bag" operator, and the "first" function will get a state
from the queue. We need to make sure that the list if states is
updated to the right value after each of these functions is called:
datum * add_to_stack (datum * new_state, datum * stack) {
return (cons (new_state, stack));
}
datum * remove_from_stack (datum *stack) {
return (rest (stack));
}
For breadth-first search, we need to implement a queue. This will be
easier to do with a function called "append". The
function append takes two lists, and returns a list containing all of
the elements of the first list, followed by all of the elements of the
second list:
append (a b) (c d)) => (a b c d)
(append (1) (2 3 4)) => (1 2 3 4)
(append (1 2 3 4) (5)) => (1 2 3 4 5)
To add an element to a queue, we need to create a list that has all of
the existing elements of the queue first, and then the new element at
the end. This is just like the last example above, and so we can do:
datum * add_to_queue (datum * new_state, datum * queue) {
return (append (queue, cons (new_state, NULL)));
}
Note that append works only on lists, so we need to create a list
containing the new state, before calling append.
The function for removing an item from a queue is exactly the same as
the one for removing one from a stack - just return the first element
of the list, and update the list to point to the rest of its elements.
$Id: searchimp.html,v 1.4 2000/01/24 18:29:28 batali Exp $