by kirupa |
13 January 2006
If you want to go from Point A to Point
B, you are employing some kind of search. For a direction finder, going from
Point A to Point B literally means finding a path between where you are now and
your intended destination. For a chess game, Point A to Point B might be two
points between its current position and its position 5 moves from now. For a
genome sequencer, Points A and B could be a link between two DNA sequences.
As you can tell, going from Point A to Point B is different
for every situation. If there is a vast amount of interconnected data, and you
are trying to find a relation between few such pieces of data, you would use
search. In this tutorial, you will learn about two forms of searching, depth
first and breadth first.
Searching falls under Artificial
Intelligence (AI). A major goal of AI is to give computers the ability to think,
or in other words, mimic human behavior. The problem is, unfortunately,
computers don't function in the same way our minds do. They require a series of
well-reasoned out steps before finding a solution. Your goal,
then, is to take a complicated task and convert it into simpler steps that your
computer can handle. That conversion from something complex to something simple
is what this tutorial is primarily about. Learning how to use two search
algorithms is just a welcome side-effect.
Majority of this tutorial goes into detail about how to
solve depth and breadth first searches. Flash-only information is introduced
only in the later pages, therefore non-Flash programmers should find the
information useful also!
Our Search Representation
Let's first learn how we humans would solve a search problem. First, we need
a representation of how our search problem will exist.
The following is an example of our search tree. It is a series of interconnected nodes that
we will be searching through:
In our above graph, the path connections are not two-way. All
paths go only from top to bottom. In other words, A has a path to B and C, but B
and C do not have a path to A. It is basically like a one-way street.
Each lettered circle in our graph is a node. A node can be
connected to other via our edge/path, and those nodes that its connects to are
called neighbors. B and C are neighbors of A. E and D are neighbors of B, and B
is not a neighbors of D or E because B cannot be reached using either D or E.
Our search graph also contains depth:
We now have a way of describing location in our graph. We
know how the various nodes (the lettered circles) are related to each other
we have a way of characterizing the depth each belongs in. Knowing
this information isn't directly relevant in creating our search algorithm, but
they do help us to better understand the problem.
In the next page, let's use our above representation of our
graph to find out how Depth First Search works.
Onwards to the next page!