Techniques used, hierarchy of the search classes.

In this section we describe a basic technique used in the different search classes and explain how these classes relate to each other.

In writing the search engine we followed the procedure outlined in section [*] except that we do not build an actual tree-like structure. Instead, we use two lists, called OPEN and CLOSED. OPEN is a list containing nodes ready for expansion and CLOSED a list of those nodes that already have had the expansion procedure applied to them. The algorithm forming the search procedure consists of the following steps:

  1. Put the start node on OPEN.
  2. Get the first node from OPEN. If OPEN is empty exit with failure, otherwise continue.
  3. Remove this node from OPEN and put it on CLOSED; call this node .
  4. Expand node , generating all of its successors. This is done by calling function do_operator() or expand().
  5. Provide every successor with a pointer back to and pass it to function add() that may or may not put the node on OPEN.
  6. Check each successor to see if it is a goal node. If so exit, otherwise go to 2.5


The algorithm that we just described can be found in function solve() which is a member-function of class SEARCH_  and also of class BISEARCH_  and of class AOSEARCH_ . These three classes are the most important classes in the search class hierarchy, each implements basic routines needed by different search algorithms, as follows:


The names of these three classes correspond to three different kinds   of search techniques that are offered to the user to solve different kinds of problems: uni-directional, i.e., normal search, bi-directional search and AND/OR search. However, these classes should never be used for direct derivation, they must be thought of as skeleton classes that outline the overall search method. Other classes, derived from these three basic classes, implement the actual search algorithms, but before we are going to describe these classes we must first introduce another important class, class NODE_,.

Class NODE_ specifies a general structure that is to be processed by class SEARCH_ (and by class BISEARCH_). Class NODE_ is itself derived from class SVOBJECT_ (sortable object), which, in turn, is derived from class VOBJECT_. Class NODE_ may be thought of as an abstraction of the nodes in a search tree or, equivalently, of the states in a state space. When designing problem-solving software most time will be spent in finding a good representation of these nodes/states. Once this representation is found it must be turned into a class that is derived from class NODE_ (or from one of its derivatives, depending on the search algorithm that is used, see later), like this:

class PNODE_ : public NODE_
{
   ...
};

As said, class SEARCH_, BISEARCH_ and AOSEARCH_ are the most fundamental search classes and it should never be necessary to derive directly from these classes, but rather from one of the following classes, each derived from class SEARCH_:


Or from one of the following classes, derived from class BISEARCH_:


Or from one of the classes derived from class AOSEARCH_:


To make use of any of the search algorithms that the search class library offers the user must derive a class from one of the classes above, for instance:

class PUZZLE_ : public DEPTH_GRAPH_
{
   ...
};

The first four sets of classes, DEPTH_TREE_, DEPTH_GRAPH_, BREADTH_TREE_ and BREADTH_GRAPH_ and also the the classes derived from BISEARCH_, i.e., BIDEPTH_TREE_, BIDEPTH_GRAPH_, BIBREADTH_TREE_ and BIBREADTH_TREE_ must be used in conjuntion with class NODE_. This means that when performing, for instance, a depth-first search the class that is used to represent the nodes in the search tree must be derived from NODE_ (see first example above and also demo one and demo two).

Class UNICOST_TREE_, UNICOST_GRAPH_ and BEST_ require the nodes to have some special features. They must be used in conjunction with a derivative of class NODE_, class UNI_NODE_ or class BEST_NODE_, respectively (see demo four and five for classes that are derived from one of these two).

Lastly, class AODEPTH_TREE_ and AOBREADTH_TREE_ must be used in conjunction with classes ORNODE_, a derivative from class AONODE_, which is derived from class NODE_ (see demo seven for a class derived from class ORNODE_). Another derivative from class AONODE_ is class ANDNODE_, but this class should never be used for derivation, its use will be explained later.

To summarize: