COPYRIGHTS

You're free to use, modify and distribute this software, as long as you don't pretend you wrote it all by yourself :-), i.e., as long as my name gets mentioned.
If you like this software or find any bugs or other problems I would like to hear about it.

DESCRIPTION

The search class library is a software package I wrote during an intership. It is meant to be used as a tool for developing problem solving software. Basically, the library offers the programmer a set of search algorithms that may be used to solve all kind of different problems. The idea is that when developing problem solving software the programmer should be able to concentrate on the representation of the problem to be solved and should not need to bother with the implementation of the search algorithm that will be used to actually conduct the search. This idea has been realized by the implementation of a set of search classes that may be incorporated in other software through C++'s features of derivation and inheritance. The following search algorithms have been implemented:

depth-first tree and graph search.
breadth-first tree and graph search.
uniform-cost tree and graph search.
best-first search.
bidirectional depth-first tree and graph search.
bidirectional breadth-first tree and graph search.
AND/OR depth tree search.
AND/OR breadth tree search.

Using one of these search methods in your own programs is just a matter of deriving a class from the desired search class and filling in the necessary parts.
Turning the representation of the problem into actual source code is also made easier because the library demands that certain functions be used (these - virtual - functions are called by several routines in the search library), which helps standardizing this process.

Although this package is meant as a tool for developing problem solving software it is not meant exclusively for programmers that are familiar with the concept of problem representation and search techniques. The document accompanying this package first describes (though condensed) the theory of problem solving in AI and next explains how the search class library must be used. Furthermore, as the source code is richly commented and as also some demo programs are included the package should also prove useful to people that want to get acquainted with the subject.

COMPILING

There are two kinds of makefiles present: one for BCC (this is the standard makefile), but it should be easy to modify it for other compilers, and another for GCC under UNIX.
When compiling with MSC you may want to use the define -DMSC, this is to solve some problems concerning the different format of the _set_new_handler() function that is used by this compiler. When compiling under UNIX you must first rename all .cpp files to .cc. Demo programs that make use of the search class library are in /demos, they must must be made seperately from the other sources.

DOCUMENTATION

Documentation is in directory /doc. The documentation comes in three formats:

search.tex: latex.
search.dvi: device independent output.
search.ps : postscript.

In these docs you'll find a short introduction to the theory of problem-solving in AI and an explanation of how the search library must be used.

SOURCE CODE

File names (in directory /src/) starting with 'g' denote graph searching routines and those starting with 't' denote tree searching routines.
I feel that the source is a bit overcommented, but I hope this enhances the instructional value of the package (ahem).

NOTES

Note that because some routines in the search library make use of recursion (namely, the routines that are used to print the solution of the problem) it may be necessary to increase the stack size when linking in the library (hasn't happened to me so far - just compile everything under UNIX :-).

Peter Bouthoorn
Jan Steenstr 12
9312 PV Nietap
The Netherlands

peter@icce.rug.nl,
or: peter@freedom.nmsu.edu (thanks Jeff!)