by kirupa 
13 January 2006From the previous page (and prior
pages), you learned how to solve search problems by hand. Now, it's time for the
next step. It is time to help your computer to solve the search problems also.
Pseudocode / Informal Algorithms
Now that you have a good idea on how to solve these various search problems, you
need to translate them so that a computer can solve it. Before we get into the
code, let's solve it generally using pseudocode, or if you prefer a better name,
an informal algorithm.
Depth First Search
The pseudocode for depth first search based on what we did in
Page 2 is:

Declare two empty lists: Open and Closed.

Add Start node to our Open list.

While our Open list is not empty, loop the following:

Remove the first node from our Open List.

Check to see if the removed node is our destination.

If the removed node is our destination, break out
of the loop, add the node to our Closed list, and return the
value of our Closed list.

If the removed node is not our destination,
continue the loop (go to Step c).

Extract the neighbors of our above removed node.

Add the neighbors to the beginning of
our Open list, and add the removed node to our Closed list. Continue
looping.
Breadth First Search
The pseudocode for breadth first first search is similar to what you see above,
and it is based on what we did in page 3
is:

Declare two empty lists: Open and Closed.

Add Start node to our Open list.

While our Open list is not empty, loop the following:

Remove the first node from our Open List.

Check to see if the removed node is our destination.

If the removed node is our destination, break out
of the loop, add the node to our Closed list, and return the
value of our Closed list.

If the removed node is not our destination,
continue the loop (go to Step c).

Extract the neighbors of our above removed node.

Add the neighbors to the end of our
Open list, and add the removed node to our Closed list.
The Pseudocode Converted to
Flash Syntax
The following is Depth First search in ActionScript using methods from the
Graph ADT:
 searchMethod =
function ()
{
 var origin:Node
= nodeOrigin;
 var destination:Node
= nodeDestination;
 // Creating our Open and Closed Lists
 var closedList:Array
= new
Array();
 var openList:Array
= new
Array();
 // Adding our starting point to Open List
 openList.push(origin);

 // Loop while openList contains some data.
 while (openList.length
!= 0)
{
 // Loop while openList contains some data.
 var n:Node
= Node(openList.shift());

 // Check if node is Destination
 if (n
== destination)
{
 closedList.push(destination);
 trace("Closed!");
 break;
 }

 // Store n's neighbors in array
 var
neighbors:Array
= n.getNeighbors();
 var nLength:Number
= neighbors.length;

 // Add each neighbor to the beginning of
our openList
 for (i=0;
i<
nLength; i++)
{
 openList.unshift(neighbors[nLength
 i
 1]);
 }

 // Add current node to closedList
 closedList.push(n);
 }
 };
Not to be left behind, you now have the
ASversion of Breadth First Search:
 searchMethod =
function ()
{
 var origin:Node
= nodeOrigin;
 var destination:Node
= nodeDestination;
 // Creating our Open and Closed Lists
 var closedList:Array
= new
Array();
 var openList:Array
= new
Array();
 // Adding our starting point to Open List
 openList.push(origin);

 // Loop while openList contains some data.
 while (openList.length
!= 0)
{
 // Loop while openList contains some data.
 var n:Node
= Node(openList.shift());

 // Check if node is Destination
 if (n
== destination)
{
 closedList.push(destination);
 trace("Closed!");
 break;
 }

 // Store n's neighbors in array
 var
neighbors:Array
= n.getNeighbors();
 var nLength:Number
= neighbors.length;

 // Add each neighbor to the end of our
openList
 for (i=0;
i<nLength;
i++)
{
 openList.push(neighbors[i]);
 }

 // Add current node to closedList
 closedList.push(n);
 }
 };
On the next page, I will go through each line of
code and explain what exactly it does and how it helps your computer to solve a
search problem.
Onwards to the next page!
