|
1.0 Tree Searches |
In this section we present some methods for searching trees and graphs. All
coding examples are in C#.
Consider the following. We have a tree data structure shown in Figure 1 with one
or more nodes interconnected by undirected edges such that
(a) one node R is designated the root of the tree, and
(b) the remaining nodes excluding the root are partitioned into disjoint sets and
each of these sets is a tree, and
(c) one node G is designated a Goal node.
|
Figure 1-1 Tree Data Structure |
Our problem is to find the Goal node, if it exists, and determine a path from the
Root to the Goal. Initially, we know nothing of the structure of the tree,
whether the Goal node is present, or if the tree has a finite number of nodes.
Although our node numbering follows a discernible pattern here of left-to-right,
top-to-bottom, we should not infer that higher node numbers are further right and
further down. The numbers could have been randomly generated.
What is needed is a method for examining each node to determine if it is the Goal
node. We shall further specify that a node may be examined only once.
An uninformed search proceeds blindly from the Root and stops either when
the Goal node has been found or after each node has been inspected. One method
follows each leg in the structure, for instance R-1-2, until it finds a node
with no successors (Node 2), and continues the search beginning at the most recent
junction (Node 1) where it examines 3-4 and then continues at 5-6-7-8. On
the next leg of the search beginning at Node 9, the Goal node is found and the search
stops. This is an example of a Depth First Search (DFS).
Alternately we could examine each of the nearest neighbors of the Root, nodes 1,
5, and 9, and then examine each of their nearest neighbors, nodes 2, 6, 10 and 11
which are each two nodes distance from the Root and so forth. The search ends
in the third iteration where nodes 4-7-G-12 are visited. The Nth iteration
examines nodes at a distance N from the Root. This is a Breadth First Search
(BFS).
In both kinds of searches we started with a child node on the left. The decision
is arbitrary. We could have started with a child on the right or one that
is neither on the left nor right.
Our approach consists of three parts. First, we define a node class and
an abstract class for a tree structure, and then a specific implementation.
The class Node defined below has an integer value and a templated
List collection of neighboring
nodes both exposed as public properties, and a Boolean property Visited used for
indicating that the node has been examined in a tree search. Neighbor nodes
are added as an array through the public method AddNodes( ). The node's value is set
in its constructor.
|
|
Listing 1-1 Node Class Definition
public class Node
{
private int _nodeval;
public List<Node> _neighbornodes;
private bool _visited;
public Node(int nodeval)
{
_nodeval = nodeval;
_neighbornodes = new List<Node>();
}
// Methods
public void AddNodes(Node[] neighbors)
{
for (int i = 0; i < neighbors.Length; i++)
this.NeighborNodes.Add(neighbors[i]);
}
// Properties
public int NodeValue
{
get { return _nodeval; }
set { _nodeval = value; }
}
public List<Node> NeighborNodes
{
get { return _neighbornodes; }
set { _neighbornodes = value; }
}
public bool Visited
{
get { return _visited; }
set { _visited = value; }
}
} // end class Node
|
To allocate a new node called myNode with value 2 and neighboring nodes node2 and
node3 which are both assumed to exist, write
Node myNode = new Node(2);
myNode.AddNodes ( new Node[] {node2, node3} );
Search methods are incorporated into a tree-search class which together with
the Node class allow for traversing a tree with prescribed structure. We will study different methods
for performing searches and different ways for specifying
the tree's structure. In order to generalize this process, we first propose
an abstract tree-search class, defined in the listing below for class AbsTreeSearch.
While the class does not specify a search method (this may change as this project
progresses), it specifies the signature for building an adjacency list and defines
two important helper methods which we don't wish to repeat with every derived class.
The adjacency list defines the structure of the tree. It consists of node
creation and calls to the Node class method AddNodes( ).
The adjacency list, which is a list of nodes and their neighbors, occupies a templated
collection, _nList. It is created in the abstract class. This and two
other Node variables _root and _goal appear in all implementations of tree searches
and are defined here with protected access level.
The helper methods that are defined here (so that they don't have to be redfined
in derived classes) are ResetVisitedStates( ) and ShowNodes( ). The
first sets the Visited property of each node in the node list to false and should
be run between searches. The second displays the node list on the standard
output which normally will be the client Console window. Good programming
practice would normally test nList to ensure that it exists (i.e., is not a null
object) before iterating through its members. However, nList has already been
instantiated in the abstract class constructor making this step unnecessary.
|
|
|
Listing 1_2 AbstractTreeSearch Class Definition
abstract public class AbsTreeSearch
{
protected List<Node> _nLst;
protected Node _root;
protected Node _goal; // Note: there may be more than one
// target state, but only one may be
// designated as a goal.
public AbsTreeSearch()
{
_nLst = new List<Node>();
}
abstract public void BuildAdjacencyList();
public void ResetVisitedStates()
{
if (_nLst != null)
foreach (Node node in _nLst)
node.Visited = false;
}
public void ShowNodes()
{
for (int i = 0; i < _nLst.Count; i++)
{
string decoration;
if (_nLst[i] == _root)
decoration = "(ROOT)";
else
if (_nLst[i] == _goal)
decoration = "(GOAL)";
else
decoration = "";
Console.WriteLine("Node {0} {1} \n--------", i, decoration);
Console.Write("Neighbors: ");
int neighborcount = _nLst[i].NeighborNodes.Count;
if (neighborcount == 0)
Console.WriteLine("none \n");
else
{
for (int j = 0; j < neighborcount; j++)
if (j != neighborcount - 1)
Console.Write("{0}, ",
_nLst[i].NeighborNodes[j].NodeValue.ToString());
else
Console.WriteLine("{0} \n",
_nLst[i].NeighborNodes[j].NodeValue.ToString());
}
}
}
} // end class AbsTreeSearch
|
On the next page, we present a "simple" impelmentation of the TreeSearch class derived
from the abstract class with implementations of search functions. Two of these
are Depth First Search (DFS) methods; one is recursive. The third search function
is a non-recursive Breadth First Search (BFS). These functions are discussed
on the next page. Following this discussion, we will give some examples of
the use of the search functions, and then turn our attention to heuristic methods
that improve performance.
|