Now that we have introduced the search classes and have outlined their hierarchy we will explain how they can and should be used. As said, class SEARCH_6 is one of the most important and most basic classes. One of the tasks of class SEARCH_ is to keep track of the number of operators that may be applied to the nodes (in the expansion procedure). It receives this information through its constructor, therefore, every class that is derived from SEARCH_ must call SEARCH_'s constructor, passing to it the number of operators, as an integer. The node representing the initial state and the node representing the goal state must also be passed to this constructor, except when deriving from class AOSEARCH_, in this case only the start node and number of operators should be passed7. But as we never derive directly from class SEARCH_ we do not pass this information to SEARCH_ directly, but through one of its derivatives, using the constructor of the derived class. Suppose we build a class called PUZZLE_, derived from class DEPTH_GRAPH_, then this could be a constructor of PUZZLE_:
PUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *goal) :DEPTH_GRAPH_(start, goal, 4) { // pass start node, goal node and number of } // of operators to DEPTH_GRAPH_ 's construc- // tor (that will pass them on to SEARCH_)
As PUZZLE_ is ultimately derived from SEARCH_ it must implement all
virtual functions (in SEARCH_) that are still left undefined (i.e., that are
not instantiated by one of SEARCH_'s derivatives). In the case of the DEPTH_
and BREADTH_ classes there are none. But some of the other search classes have
a couple of virtual functions that must implemented by the user. Class UNICOST_TREE_
and UNICOST_GRAPH_ require the implementation of funcion compute_g() and class
BEST_ of both this function and of function compute_h(). Both of these functions
serve to compute a cost associated with a node: compute_g() computes the cost
of getting from a node's parent to the node itself, i.e. the cost associated
with the arc connecting both nodes, and compute_h() computes the
heuristic value of a node (see section and section
, but
note that function compute_g() must only compute the second half of g(n)):
int compute_g(const NODE_ &) // computes cost of getting from // node's parent to node itself int compute_h(const NODE_ &) // computes heuristic value of // a node
The search classes derived from BISEARCH_ do not have any non-defined virtual functions left. But the last set of classes, AODEPTH_TREE_ and AOBREADTH_TREE_, require the implementation of function is_terminal() which checks whether a node represents a terminal node:8
int is_terminal(const AONODE_ &) // node is terminal node? // 1 : yes, 0 : no
Just like class SEARCH_ class NODE_ also has a number of virtual functions that must be implemented by the user. One of the most important of these is do_operator() that is used for node expansion (step 4 in the algorithm).
NODE_ *do_operator(int) const // apply operator n and // return new node or NULLNote that the object returned by do_operator() must have been allocated in memory. Function do_operator() is called by SEARCH_::solve(), that passes do_operator() an integer representing one of the operators. This way the operators are numbered, starting at 0 and ending at number of operators minus 1. If the operator can be applied do_operator() should return a new node (allocated by new), if not, it should return NULL. This is one way a node may be expanded. Another possibility is by use of funtion expand(). This function is similar to do_operator(), except that it returns a linked list of all of its successors, instead of one successor at a time. This is useful when dealing with problems that do not use operators or that have a variable number of operators.
NODE_ *expand(int) const // expand node and return all of // its successors in a linked listThe linked list that expand() returns must be built using the next-pointer field in NODE_ (NODE_ *next). An example of how funtion expand() may be used and how to build the linked list is given in demo five.
Apart from do_operator() there are two other functions, which are virtual in class NODE_, that must be implemented. One of these, equal(), tests whether two nodes are the same, it must return 1 if true and 0 if not. The other one, display() is used to display a node:
int equal(const VOBJECT_ &) const // nodes are the same node? // 1 : true, 0 : false void display() const // display the nodeNote that the argument in equal() is VOBJECT_ and not NODE_, this is because equal() is inherited by NODE_ from VOBJECT_.
Using these funtions the implementation of user-defined problems should be
straightforward. Still, it will be helpful to make some remarks concerning the
the AND/OR search classes. In section we explained how an
AND/OR graph may be created and we introduced the concept of AND-nodes and
OR-nodes. The meaning of these terms is slightly different in the
implementation of the AND/OR search classes. Here we will call all nodes OR-nodes,
except those nodes that connect a set of sub-problems (nodes N and M in
fig.
), which are to be called AND-nodes. This relates to the
AND/OR search classes in the following way. As said, the user-definable objects
that serve to represent the nodes in the search tree must be derived from
class ORNODE_. But now suppose that some node A may be reduced to the set of
sub-problems {B,C,D}. Normally we would call B, C and D AND-nodes, but here,
as said, they are called OR-nodes. The next step is to create a node that
connects nodes B, C and D and this node is called an AND-node. This AND-node
must created by calling new ANDNODE_() and adding to this node all of its
successors, in this case node B, C and D, by calling addsucc(), like this:
ANDNODE_ *andnode; andnode = new ANDNODE_; // it must be allocated andnode->addsucc(node_a); andnode->addsucc(node_b); andnode->addsucc(node_c); return(andnode);
When the number of successors is known in advance a different possibility is to pass this number to the constructor of ANDNODE_ and then using setsucc() to pass the successors, like this:
AND_NODE_ *andnode; andnode = new ANDNODE_(3); // we will add 3 nodes andnode->setsucc(0, node_a); // we start counting at 0 andnode->setsucc(1, node_b); andnode->setsucc(2, node_c); return(andnode);
The only problem that may, and most of the time will, arise is that we don't know before hand what kind of node will be produced, an AND-node or and OR-node, so we do not know if we need and AND_NODE_ or an OR_NODE_ pointer (this is especially true when building a linked list of nodes as in expand()). But this is easily solved when we use a AONODE_ pointer, because both AND_NODE_ and OR_NODE_ are derived from this class, and next casting the result if needed. An example of this technique is given in demo seven.
One thing has not been mentioned yet: how must the search be started? This is done by a call to function generate(), a member function of class SEARCH_. For example:
PUZZLE_ puzzle; .... puzzle.generate(); // start looking for a solution