|
1.1 Uninformed Searches |
The SimpleTreeSearch class defined below in Listing 1-3 below contains two Depth First Search methods
and one Breadth First Search. Each method takes a starting node and
target node for its arguments and its node tree from _nList which was instanced
in the parent class AbsTreeSearch and populated in BuildAdjacencyList ( )
which must be overridden in the SimpleTreeSearch class definition. The base method's constructor
is called in SimleTreeSearch's constructor. This is not strictly necessary
(the base constructor is called by default), but included here as a reminder that
an argument can be passed to the constructor at this point. For instance,
in a large application, the base constructor might test available space before creating
an instance of the node list. The number of nodes could be passed back to
the base here.
In DFS ( ), a non-recursive DFS method, the starting node is pushed onto a Last
In First Out (LIFO) stack. The search proceeds down each limb of the tree
marking each node as visisted. A node's neighbors are pushed onto the stack.
If a node has been visited, it is not examined and execution continues in a new
iteration of the while-loop. Otherwise, nodes are popped from the stack one
at a time and their neighbors are pushed onto the stack, and so forth. The
search ends either when a node is found to be the goal node, or _nList has been
exhausted. Note that _nList does not explicitly appear in the DFS ( ) method.
However, all the nodes in the list will be tested (until a goal node is found) because
the neighbors of the starting node are tested, and each of their neighbors
are tested until all nodes and their neighbors have been examined.
The second DFS method DFS_Recursive ( ) replaces the stack with a recursive
call to itself. While execution proceeds down each branch of the stack, the
sequence of examined nodes differs from the non-recursive variation. In the
non-recursive case, popped nodes are examined in the reverse order that they were
pushed onto the stack.
BFS ( ), a Breadth First Search uses a First In First Out (FIFO) queue to order
nodes to be examined. All the nodes at a specific level or distance, say d,
from the starting node are examined before proceeding further.
A demonstration program which combines the three previous listings with the node
tree shown on the previous page can be run as shown in the skeletal listing on the
next page. The accompanying figure shows the resulting console output.
|
|
Listing 1-3 Simple Tree-Search Implementation with Depth First and Breadth First Searches
public class SimpleTreeSearch : AbsTreeSearch
{
Stack<Node> _nodes;
public SimpleTreeSearch(int noOfNodes) : base()
{
_nodes = new Stack<Node>();
BuildAdjacencyList ()
}
public void DFS(Node start, Node goal)
{
_nodes.Push(start);
while (_nodes.Count > 0)
{
Node node = _nodes.Pop();
if (node.Visited)
continue;
else
node.Visited = true;
Console.WriteLine("Visiting " + node.NodeValue.ToString());
if (node == goal)
{
Console.WriteLine("DFS found goal node.\n");
return;
}
for (int i = 0; i < node.NeighborNodes.Count; i++)
_nodes.Push(node.NeighborNodes[i]);
}
Console.WriteLine("DFS did not find goal node.\n");
}
public bool DFS_Recursive(Node start, Node goal)
{
if ((start != goal) && (!start.Visited))
{
Console.WriteLine("Visiting " + start.NodeValue.ToString());
start.Visited = true;
for (int i = 0; i < start.NeighborNodes.Count; i++)
if (!start.NeighborNodes[i].Visited)
{
if (DFS_Recursive(start.NeighborNodes[i], goal))
return true;
}
}
else
{
Console.WriteLine("Recursive DFS found goal node.\n");
return true;
}
return false;
}
public void BFS(Node start, Node goal)
{
Queue<Node> queue = new Queue<Node>();
queue.Enqueue(start);
while (queue.Count > 0)
{
Node node = queue.Dequeue();
if (node.Visited)
continue;
else
{
Console.WriteLine("visiting " + node.NodeValue.ToString());
if (node == goal)
{
Console.WriteLine("BFS found goal node.");
return;
}
node.Visited = true;
for (int i = 0; i < node.NeighborNodes.Count; i++)
{
if (!node.NeighborNodes[i].Visited)
queue.Enqueue(node.NeighborNodes[i]);
}
}
}
Console.WriteLine("BFS did not find goal node.");
}
public override void BuildAdjacencyList()
{
// Create the nodes.
for (int i = 0; i <= 15; i++)
// Add a node with NodeVal = i.
_nLst.Add(new Node(i));
_root = _nLst[0];
_goal = _nLst[15];
// Add connections.
_root.AddNodes(new Node[]{_nLst[1], _nLst[5], _nLst[9]});
_nLst[1].AddNodes(new Node[] { _nLst[2], _nLst[3], _root });
_nLst[2].AddNodes(new Node[] { _nLst[1] });
_nLst[3].AddNodes(new Node[] { _nLst[4], _nLst[1] });
_nLst[4].AddNodes(new Node[] { _nLst[3] });
_nLst[5].AddNodes(new Node[] { _nLst[6], _root });
_nLst[6].AddNodes(new Node[] { _nLst[7], _nLst[5] });
_nLst[7].AddNodes(new Node[] { _nLst[8], _nLst[6] });
_nLst[8].AddNodes(new Node[] { _nLst[7] });
_nLst[9].AddNodes(new Node[] { _root, _nLst[10], _nLst[11] });
_nLst[10].AddNodes(new Node[] { _goal });
_goal.AddNodes(new Node[] { _nLst[10] });
_nLst[11].AddNodes(new Node[] { _nLst[9], _nLst[12] });
_nLst[12].AddNodes(new Node[] { _nLst[11], _nLst[13], _nLst[14] });
_nLst[13].AddNodes(new Node[] { _nLst[12] });
_nLst[14].AddNodes(new Node[] { _nLst[12] });
}
|
A demonstration program which combines the three previous listings with the node
tree shown on the previous page can be run as shown by substituting listings in
Listing 1-4, below. The accompanying figure shows the resulting console output.
|
|
|
Listing 1-4 Simple Tree-Search Implementation with Depth First and Breadth First Searches
using System;
using System.Collections.Generic;
using System.Text;
namespace TreeSearch
{
public class Node
{
// Code in Listing 1-1 goes here.
}
abstract public class AbsTreeSearch
{
// Code in Listing 1-2 goes here.
}
public class SimpleTreeSearch : AbsTreeSearch
{
// Code in Listing 1-3 goes here.
}
static void Main (string[] args)
{
SimpleTreeSearch ts = new SimpleTreeSearch(16);
ts.ShowNodes();
Console.WriteLine("\n\n\n");
ts.DFS(ts._root, ts._goal);
ts.ResetVisitedStates();
if (!ts.DFS_Recursive(ts._root, ts._goal) )
Console.WriteLine("DFS_Recursive did not find goal node.\n\n");
ts.ResetVisitedStates();
ts.BFS(ts._root, ts._goal);
Console.ReadLine(); // stop here until user presses any key
}
} // end namespace TreeSearch
|
Figure 1-2 Results of Simple Tree Searches
|
|
1.2 Uninformed Searches with Additional Features
|
Note that the tree data structure (view here)
has no cycles. But in a connected tree with undirected edges, the goal node
will always be found with either the DFS or the BFS because all nodes that can be
reached from another node are visited once, and only once, even for nodes that appear
in a cycle. To see a demonstration of this, create a cycle by connecting nodes
3 and 6. This can be accomplished in BuildAdjacencyList ( ) by changing _nList[3]
and _nList[6] as shown below:
_nList[3].AddNodes (new Node[] {_nLst[4], _nLst[1] });
becomes
_nList[3].AddNodes(new Node[] {_nLst[4], _nLst[1], _nLst[6] });
The node list can have any geometry. It could be a random geometry. Rewrite BuildAdjacencyList ( ) as shown in
Listing 1-5 below. (Comment out the old version, if desired.) Create a list with 100 nodes (the value of N on the
first line) where each node has three neighbors chosen randomly and the next node in _nList connects to the third
neighbor of the previous node guaranteeing that all nodes can be reached starting from anywhere in the graph. By
the way, we'll present a Windows application shortly that shows the graph pictorially.
|
|
|
Listing 1-5 Simple Search With Additional Features
public override void BuildAdjacencyList()
{
int N = 100;
// Create the nodes.
for (int i = 0; i < N; i++)
_nLst.Add(new Node(i));
_root = _nLst[0];
_goal = _nLst[N/2];
int seed = (int)System.DateTime.Now.Ticks % System.Int32.MaxValue;
Random rchild = new Random(seed);
int randNo1, randNo2, randNo3;
Node prevNode = _nLst[0];
for (int i=0; i < N; i++)
{
while ( (randNo1 = rchild.Next(0, N)) == i);
while ((randNo2 = rchild.Next(0, N)) == i) ;
while ((randNo3 = rchild.Next(0, N)) == i) ;
_nLst[i].AddNodes(new Node[] {_nLst[randNo1], _nLst[randNo2],
_nLst[randNo3], prevNode });
prevNode = _nLst[randNo1];
}
}
|
There's more to come. Check back often! Comments?
Send feedback.
|