Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume41/aisearch/part04

Text File | 1994-02-01 | 87.6 KB | 2,624 lines

Newsgroups: comp.sources.misc
From: [e-mail] (Peter Bouthoorn)
Subject: v41i130:  aisearch - C++ AI search class library, Part04/05
Message-ID: <[e-mail]>
X-Md4-Signature: 133bcc4f6c9a97276b163c267b667909
Sender: [e-mail] (Kent Landfield)
Organization: Sterling Software
Date: Wed, 2 Feb 1994 04:00:21 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (Peter Bouthoorn)
Posting-number: Volume 41, Issue 130
Archive-name: aisearch/part04
Environment: C++ (UNIX, DOS)

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then feed it
# into a shell via "sh file" or similar.  To overwrite existing files,
# type "sh file -c".
# Contents:  demos/demo1.cpp demos/demo3.cpp demos/demo4.cpp
#   demos/demo7.cpp doc/search.tex include/list.h include/nodes.h
#   src/bisear/bisearch.cpp src/unisear/gbest.cpp
#   src/unisear/search.cpp
# Wrapped by kent@sparky on Thu Jan 27 22:25:10 1994
PATH=/bin:/usr/bin:/usr/ucb:/usr/local/bin:/usr/lbin:$PATH ; export PATH
echo If this archive is complete, you will see the following message:
echo '          "shar: End of archive 4 (of 5)."'
if test -f 'demos/demo1.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'demos/demo1.cpp'\"
else
  echo shar: Extracting \"'demos/demo1.cpp'\" \(3448 characters\)
  sed "s/^X//" >'demos/demo1.cpp' <<'END_OF_FILE'
X#include "demo1.h"
X
X/*                   PUZZLE_
X
X    Passes the start node, goal node, and number of operators on
X    the DEPTH_GRAPH_'s constructor.
X
X*/
X
XPUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *goal)
X    :DEPTH_GRAPH_(start, goal, 4)
X{
X}
X
X
X
X/*                    PNODE_
X
X    Creates a new board configuration.
X
X*/
X
XPNODE_::PNODE_(OP_USED_ op_used, int empty_x, int empty_y)
X{
X    operator_used = op_used;
X    x = empty_x;
X    y = empty_y;
X}
X
X
X
X/*                       DISPLAY
X
X    Displays the operator applied to get to this state and the
X    coordinates of the empty tile of the current state.
X
X*/
X
Xvoid PNODE_::display() const
X{
X    static char
X        *move[] = { "start state",
X                    "left",
X                    "right",
X                    "up",
X                    "down"
X                  };
X
X    printf("%s - empty spot at: [%d] [%d]\n", move[operator_used], y, x);
X}
X
X
X
X/*                       EQUAL.CPP
X
X    Determines if two states, i.e., two PNODE_'s are the same by
X    comparing the set of coordinates of both objects.
X
X*/
X
Xint PNODE_::equal(const VOBJECT_ &other) const
X{
X    return(x == ((const PNODE_ &)other).get_x()
X          && y == ((const PNODE_ &)other).get_y());
X}
X
X
X
X/*                      GET_X.CPP
X
X    Returns the x-coordinate of the position of the empty tile in
X    the current configuration.
X
X*/
X
Xint PNODE_::get_x() const
X{
X    return(x);
X}
X
X
X
X/*                       GET_Y.CPP
X
X    Returns the y-coordinate of the position of the empty tile in
X    the current configuration.
X
X*/
X
Xint PNODE_::get_y() const
X{
X    return(y);
X}
X
X
X
X/*                    DO_OPER.CPP
X
X    Returns a new PNODE_ object, i.e., a new state, by applying the
X    appropriate operator to the current state, or NULL when the
X    operator cannot be applied.
X
X*/
X
XNODE_ *PNODE_::do_operator(int index) const
X{
X    switch(index)
X    {
X        case 0:
X            return(do_left());
X        case 1:
X            return(do_right());
X        case 2:
X            return(do_up());
X    }
X    return(do_down());
X}
X
X
X
X/*                   DO_LEFT
X
X    Creates a new state/node representing the configuration that
X    arises when the empty tile is moved left one position.
X
X*/
X
XPNODE_ *PNODE_::do_left() const
X{
X    if (!x)
X        return(NULL);    // can't go left any further
X
X    return(new PNODE_(left_used, x - 1, y));
X}
X
X
X
X/*                   DO_RIGHT
X
X    Creates a new state/node representing the configuration that
X    arises when the empty tile is moved right one position.
X
X*/
X
XPNODE_ *PNODE_::do_right() const
X{
X    if (x == (4 - 1))
X        return(NULL);
X
X    return(new PNODE_(right_used, x + 1, y));
X}
X
X
X
X/*                        DO_UP
X
X
X    Creates a new state/node representing the configuration that
X    arises when the empty tile is moved up one position.
X
X*/
X
XPNODE_ *PNODE_::do_up() const
X{
X    if (!y)
X        return(NULL);       // can't go up any further
X
X    return(new PNODE_(up_used, x, y - 1));
X}
X
X
X
X/*                    DO_DOWN
X
X    Creates a new state/node representing the configuration that
X    arises when the empty tile is moved down one position.
X
X*/
X
XPNODE_ *PNODE_::do_down() const
X{
X    if (y == (4 - 1))          // can't go down any further
X        return(NULL);
X
X    return(new PNODE_(down_used, x, y + 1));
X}
X
X
Xint main()
X{
X    PUZZLE_
X        puzzle(new PNODE_(none_used, 3, 3), new PNODE_(none_used, 0, 0));
X
X    puzzle.generate();           // start search process
X
X    return(1);
X}
END_OF_FILE
  if test 3448 -ne `wc -c <'demos/demo1.cpp'`; then
    echo shar: \"'demos/demo1.cpp'\" unpacked with wrong size!
  fi
  # end of 'demos/demo1.cpp'
fi
if test -f 'demos/demo3.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'demos/demo3.cpp'\"
else
  echo shar: Extracting \"'demos/demo3.cpp'\" \(3640 characters\)
  sed "s/^X//" >'demos/demo3.cpp' <<'END_OF_FILE'
X#include "demo3.h"
X
XPUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *target)
X    :DEPTH_GRAPH_(start, target, 4)
X{
X}
X
X
X/*                 PNODE
X
X    Initializes a PNODE_ object.
X
X*/
X
XPNODE_::PNODE_(const char *b, int empty_x, int empty_y)
X{
X    char
X        *p = *board;
X    int
X        i;
X
X    for (i = 0; i <= 8; i++)
X        *(p + i) = *(b + i);
X
X    x = empty_x;
X    y = empty_y;
X}
X
X
X
X/*                       PNODE_
X
X    Initializes a new configuration using it's 'parent' configuration.
X    First copies the old board and then swaps the two tiles that are
X    on old_x, old_y and new_x, new_t respectively.
X
X*/
X
XPNODE_::PNODE_(const char *b, int old_x, int old_y, int new_x, int new_y)
X{
X    char
X        *p = *board;
X    int
X        i;
X
X    for (i = 0; i <= 8; i++)
X        *(p + i) = *(b + i);
X
X    board[old_x][old_y] = board[new_x][new_y];
X    board[new_x][new_y] = 0;
X
X    x = new_x;
X    y = new_y;
X}
X
X
X
X/*                    DISPLAY
X
X    Displays a board configuration.
X
X*/
X
Xvoid PNODE_::display() const
X{
X    int
X        row,
X        col;
X
X    for (row = 0; row < 3; row++)
X    {
X        for (col = 0; col < 3; col++)
X            printf("%d ", board[row][col]);
X        putchar('\n');
X    }
X    putchar('\n');
X}
X
X
X
X/*                    EQUAL
X
X    Determines if two nodes, i.e., two board positions are the same.
X    First, the x- and y-coordinates of the empty tile are compared
X    and next, if necessary, the two boards themselves.
X
X*/
X
Xint PNODE_::equal(const VOBJECT_ &other) const
X{
X     if (x != ((const PNODE_ &)other).get_x()
X          && y != ((const PNODE_ &)other).get_y())
X            return(0);
X    return(compare_board(((const PNODE_ &)other).get_board()));
X}
X
X
X
Xconst char *PNODE_::get_board() const
X{
X    return(*board);
X}
X
X
X
Xint PNODE_::get_x() const
X{
X    return(x);
X}
X
X
X
Xint PNODE_::get_y() const
X{
X    return(y);
X}
X
X
X
X/*                   COMP_BOARD
X
X    Compares the current board configuration with another. Could
X    have used memcmp() here.
X
X*/
X
Xint PNODE_::compare_board(const char *b) const
X{
X    const char
X        *p = *board;
X    int
X        i;
X
X    for (i = 0; i <= 8; i++)
X        if (*(p + i) != *(b + i))
X            return(0);
X
X    return(1);
X}
X
X
X
X/*                 DO_OPERATOR
X
X    Applies operator n to the current configuration, i.e. it moves
X    the empty tile (by calling one of the do_..() functions) resulting
X    in a new board configuration or NULL if the operator can't be applied.
X
X*/
X
XNODE_ *PNODE_::do_operator(int index) const
X{
X    switch(index)
X    {
X        case 0:
X            return(do_down());
X        case 1:
X            return(do_up());
X        case 2:
X            return(do_right());
X    }
X    return(do_left());
X}
X
X
X
XPNODE_ *PNODE_::do_left() const
X{
X    if (!y)
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x, y - 1));
X}
X
X
X
XPNODE_ *PNODE_::do_right() const
X{
X    if (y == (2))
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x, y + 1));
X}
X
X
X
XPNODE_ *PNODE_::do_up() const
X{
X    if (!x)
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x - 1, y));
X}
X
X
X
XPNODE_ *PNODE_::do_down() const
X{
X    if (x == (2))
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x + 1, y));
X}
X
X
X
Xint main()
X{
X    char
X        start[3][3] = {
X                        {1, 3, 4},
X                        {8, 0, 2},
X                        {7, 6, 5},
X                      };
X
X    char
X        goal[3][3] = {
X                        {1, 2, 3},
X                        {8, 0, 4},
X                        {7, 6, 5},
X                    };
X
X    PUZZLE_
X        puzzle(new PNODE_(*start, 1, 1), new PNODE_(*goal, 1, 1));
X
X    puzzle.generate();
X    return(1);
X}
END_OF_FILE
  if test 3640 -ne `wc -c <'demos/demo3.cpp'`; then
    echo shar: \"'demos/demo3.cpp'\" unpacked with wrong size!
  fi
  # end of 'demos/demo3.cpp'
fi
if test -f 'demos/demo4.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'demos/demo4.cpp'\"
else
  echo shar: Extracting \"'demos/demo4.cpp'\" \(4247 characters\)
  sed "s/^X//" >'demos/demo4.cpp' <<'END_OF_FILE'
X#include "demo4.h"
X
XPUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *target)
X    :BEST_(start, target, 4)
X{
X    goal = target;
X}
X
X
X
XPNODE_::PNODE_(const char *b, int empty_x, int empty_y)
X{
X    char
X        *p = *board;
X    int
X        i;
X
X    for (i = 0; i <= 8; i++)
X        *(p + i) = *(b + i);
X
X    x = empty_x;
X    y = empty_y;
X}
X
X
X
XPNODE_::PNODE_(const char *b, int old_x, int old_y, int new_x, int new_y)
X{
X    char
X        *p = *board;
X    int
X        i;
X
X    for (i = 0; i <= 8; i++)
X        *(p + i) = *(b + i);
X
X    board[old_x][old_y] = board[new_x][new_y];
X    board[new_x][new_y] = 0;
X
X    x = new_x;
X    y = new_y;
X}
X
X
X
Xvoid PNODE_::display() const
X{
X    int
X        row,
X        col;
X
X    for (row = 0; row < 3; row++)
X    {
X        for (col = 0; col < 3; col++)
X            printf("%d ", board[row][col]);
X        putchar('\n');
X    }
X    putchar('\n');
X}
X
X
X
Xint PNODE_::equal(const VOBJECT_ &other) const
X{
X     if (x != ((const PNODE_ &)other).get_x()
X          && y != ((const PNODE_ &)other).get_y())
X            return(0);
X    return(compare_board(((const PNODE_ &)other).get_board()));
X}
X
X
X
Xconst char (*PNODE_::get_board() const)[3]
X{
X    return(board);
X}
X
X
X
Xint PNODE_::get_x() const
X{
X    return(x);
X}
X
X
X
Xint PNODE_::get_y() const
X{
X    return(y);
X}
X
X
X
Xint PNODE_::compare_board(const char bo[3][3]) const
X{
X    const char
X        *p = *board,
X        *b = *bo;
X
X    int
X        i;
X
X    for (i = 0; i <= 8; i++)
X        if (*(p + i) != *(b + i))
X            return(0);
X
X    return(1);
X}
X
X
X
XNODE_ *PNODE_::do_operator(int index) const
X{
X    switch(index)
X    {
X        case 0:
X            return(do_left());
X        case 1:
X            return(do_right());
X        case 2:
X            return(do_up());
X    }
X    return(do_down());
X}
X
X
X
XPNODE_ *PNODE_::do_left() const
X{
X    if (!y)
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x, y - 1));
X}
X
X
X
XPNODE_ *PNODE_::do_right() const
X{
X    if (y == (2))
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x, y + 1));
X}
X
X
X
XPNODE_ *PNODE_::do_down() const
X{
X    if (x == (2))
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x + 1, y));
X}
X
X
X
XPNODE_ *PNODE_::do_up() const
X{
X    if (!x)
X        return(NULL);
X
X    return(new PNODE_(*board, x, y, x - 1, y));
X}
X
X
X/*                  COMPUT_G
X
X    In this problem all arc costs are 1, so we don't have to do any
X    computation in this function.
X
X*/
X
Xint PUZZLE_::compute_g(const NODE_ &)
X{
X    return(1);
X}
X
X
X
X/*                     COMPUT_H
X
X    This function returns the heuristic value associated with each
X    node, by calling totdist().
X
X*/
X
Xint PUZZLE_::compute_h(const NODE_ &node)
X{
X    return(totdist(((PNODE_ &)node).get_board(), goal->get_board()));
X}
X
X
X
X/*                  TOTDIST
X
X    Computes the total or Manhatten distance of the tiles in the
X    current configuration from their 'home squares' (= the ordering
X    of the tiles in the goal configuration). The Manhatten between
X    two squares S1 and S2 is the distance between S1 and S2 in the
X    horizontal direction plus the distance between S1 and S2 in the
X    vertical direction.
X
X*/
X
Xint PUZZLE_::totdist(const char now[3][3], const char target[3][3])
X{
X    int nrow, ncol,
X        trow, tcol,
X        found, tot = 0;
X
X    for (nrow = 0; nrow < 3; nrow++)
X        for (ncol = 0; ncol < 3; ncol++)
X        {
X            found = 0;
X            if (now[nrow][ncol] == 0)       // skip empty tile!
X                continue;
X            for (trow = 0; trow < 3 && !found; trow++)
X                for (tcol = 0; tcol < 3 && !found; tcol++)
X                    if (now[nrow][ncol] == target[trow][tcol])
X                    {
X                        tot += abs(ncol - tcol) + abs(nrow - trow);
X                        found = 1;
X                    }
X        }
X    return(tot);
X}
X
X
X
Xint main()
X{
X    char
X        start[3][3] = {
X                        {2, 1, 6},
X                        {4, 0, 8},
X                        {7, 5, 3},
X                      };
X
X    char
X        goal[3][3] = {
X                        {1, 2, 3},
X                        {8, 0, 4},
X                        {7, 6, 5},
X                    };
X
X    PUZZLE_
X        puzzle(new PNODE_(*start, 1, 1), new PNODE_(*goal, 1, 1));
X
X    puzzle.generate();
X    return(1);
X}
END_OF_FILE
  if test 4247 -ne `wc -c <'demos/demo4.cpp'`; then
    echo shar: \"'demos/demo4.cpp'\" unpacked with wrong size!
  fi
  # end of 'demos/demo4.cpp'
fi
if test -f 'demos/demo7.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'demos/demo7.cpp'\"
else
  echo shar: Extracting \"'demos/demo7.cpp'\" \(4060 characters\)
  sed "s/^X//" >'demos/demo7.cpp' <<'END_OF_FILE'
X#include "demo7.h"
X
X/*
X
X    First we make some simple DCG-like rules and a small lexicon and store
X    this information in two arrays, rules[] and lexicon[],  using function
X    init().
X*/
X
XITEM_ *init(int number, ITEM_ start, ...)
X{
X    ITEM_
X        *tmp;
X
X    if (!(tmp = (ITEM_ *) malloc(number * sizeof(ITEM_))))
X    {
X        puts("Error: out of memory data");
X        exit(0);
X    }
X    memcpy(tmp, &start, number * sizeof(ITEM_));
X    return(tmp);
X}
X
XRULE_
X    rules[] = {
X                {2, S, init(2, NP, VP)},
X                {1, NP, init(1, SNP)},
X                {2, NP, init(2, DET, N)},
X                {1, VP, init(1, IV)},
X                {2, VP, init(2, TV, NP)},
X                {3, VP, init(3, SV, CN, S)},
X                {VOID, VOID, NULL}
X              };
X
XLEX_
X    lexicon[] = {
X                    {TV, "kills"},
X                    {SV, "thinks"},
X                    {IV, "sleeps"},
X                    {SNP, "john"},
X                    {N, "man"},
X                    {DET, "the"},
X                    {CN, "that"},
X                    {VOID, NULL}
X                };
X
Xchar        /* to print syntactic categories */
X    *table[] = {"void" , "s", "vp", "iv", "tv", "sv", "np", "snp",
X                "n", "det", "cn"};
X
X
X
XPARSE_::PARSE_(char **s, ELEMENT_ *start)
X    : AODEPTH_TREE_(start, 0)
X{
X    string = s;
X    index = 0;
X}
X
X
XELEMENT_::ELEMENT_(ITEM_ it)
X{
X    item = it;
X}
X
X
Xvoid ELEMENT_::display() const
X{
X   printf("%s\n", table[item]);
X}
X
X
X/*                    EQUAL
X
X    We don't really need this function in this class because we are
X    performing a tree search, so we can be sure none of the nodes will
X    be generated twice; also, nodes won't be compared against a goal
X    node. Still, we must define this function because it's pure
X    virtual in NODE_.
X
X*/
X
Xint ELEMENT_::equal(const VOBJECT_ &) const
X{
X    return(0);
X}
X
X
XITEM_ ELEMENT_::get_item() const
X{
X    return(item);
X}
X
X
X/*                    EXPAND
X
X    Expanding a node means in this problem that we must find the syntactic
X    category that the node represents in the database of rules. Since a rule
X    may rewrite the syntactic category to more than one new category we may
X    have to, and most of the time will, produce an AND-node.
X
X*/
X
XNODE_ *ELEMENT_::expand(int ) const
X{
X    AONODE_
X        *tmp = NULL,
X        *start = NULL;
X    int
X        i,
X        d;
X
X    for (i = 0; rules[i].num != VOID; i++)  // find item in rules database
X    {
X        if (rules[i].head == item)
X        {
X            if (rules[i].num == 1)          // create OR node
X                tmp = new ELEMENT_(rules[i].tail[0]);
X            else
X            {
X                tmp = new ANDNODE_();       // create AND node
X/* remember that our terminology of AND and OR nodes differs
X   from normal usage  */
X                for (d = 0; d < rules[i].num; d++)
X                    ((ANDNODE_ *)tmp)->addsucc(new ELEMENT_(rules[i].tail[d]));
X            }
X
X            tmp->setnext(start);
X            start = tmp;
X        }
X    }
X    return(start);
X}
X
X
X/*                  IS_TERMINAL
X
X    To determine if a node may be considered terminal we check if the
X    syntactic item to be parsed, which must of course be terminal itself,
X    matches the word (pointed to by index) in the input string. Therefore,
X    we first locate the syntactic category in the lexicon (if we can't find it
X    there this means the syntactic category isn't terminal) and compare the
X    word that accompanies it with the word in the input string.
X
X*/
X
Xint PARSE_::is_terminal(const AONODE_ &node)
X{
X    int
X        i;
X
X    for (i = 0; lexicon[i].head != VOID; i++)
X        if (lexicon[i].head == ((ELEMENT_ &)node).get_item()
X               && !strcmp(lexicon[i].tail, string[index]))
X        {
X            index++;
X            return(1);
X        }
X
X    return(0);
X}
X
X
Xint main(int argc, char *argv[])
X{
X    if (argc == 1)
X    {
X        printf("Usage: %s <string>\n", argv[0]);
X        exit(0);
X    }
X    PARSE_
X        sentence(++argv, new ELEMENT_(S));
X
X    sentence.generate();
X    return(1);
X}
END_OF_FILE
  if test 4060 -ne `wc -c <'demos/demo7.cpp'`; then
    echo shar: \"'demos/demo7.cpp'\" unpacked with wrong size!
  fi
  # end of 'demos/demo7.cpp'
fi
if test -f 'doc/search.tex' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'doc/search.tex'\"
else
  echo shar: Extracting \"'doc/search.tex'\" \(43426 characters\)
  sed "s/^X//" >'doc/search.tex' <<'END_OF_FILE'
X% NEWCOMMAND FOR \ CHARACTER:
X% \bs
X
X\documentstyle[11pt]{article}
X
X\title{C$^{++}$ Search Class Library}
X
X\author{Peter Bouthoorn}
X\date{3 December 1993}
X
X\newcommand{\bs}{$\backslash$}
X
X\begin{document}
X\maketitle
X\section{Introduction}
X
XOne of our daily activities is solving problems of any kind. AI-research has
Xshown that a lot of these problems can equally well or sometimes more easily be
Xsolved by computer programs. To be able to write such a problem-solving program
Xit is necessary to give an exact description of the problem to be solved and to
Xknow how it can be defined in terms that facilitate the translation of the
Xproblem into a computer program. In this paper we first explain the theory of
Xproblem-solving in AI and next describe an implementation of some of the ideas
Xpresented (the description of the implementation, called the search class
Xlibrary, will be quite rough, because we will concentrate on how the search
Xclass library must be used. For details on the implementation see the comments
Xaccompanying the source code).
X
X\section{Problem representation and search techniques}
X
X\subsection{State space representation and problem reduction}
X
XIn this section, we will describe two methods commonly used in problem
Xrepresentation. As a sample problem the 8-puzzle will be used. The 8-puzzle
Xconsists of 8 numbered, movable tiles set in a 3 X 3 frame. One of the cells of
Xthe frame is always empty, which makes it possible to move the tiles.
X
XA sample 8-puzzle is given in fig.~\ref{figstate}. Consider the problem of
Xtransforming the first configuration into the second one, our goal.
X
X\begin{figure}[htb]
X\centering
X    \begin{tabular}{rrrcrrr}
X            2 & 1 & 6    \hspace{2cm}           & 1 & 2 & 3 \\
X            4 & 0 & 8    \hspace{2cm}           & 8 & 0 & 4 \\
X            7 & 5 & 3    \hspace{2cm}           & 7 & 6 & 5 \\
X    \end{tabular}
X    \caption{The 8-puzzle.}\label{figstate}
X\end{figure}
X
X\noindent
XTo solve this puzzle we try out various moves producing new configurations
Xuntil we produce the goal configuration. To give a more formal
Xdefinition of this problem we say that we are trying to reach a certain {\em
Xgoal\,} configuration starting with an {\em initial} configuration by using
Xsome set of {\em operators\,}. An operator transforms one configuration into
Xanother, in the case of the 8-puzzle it is most natural to think of 4 such
Xoperators, each corresponding to moving the empty tile: move empty tile left,
Xmove empty tile right, move empty tile up, move empty tile down.
X
XWhat we just have done is defining the problem of solving the 8-puzzle in
Xterms of a {\em state space search\,}. In a state space search the object is to
Xreach a certain goal {\em state\,} starting with an initial state. In the case
Xof the 8-puzzle the start and goal state are the configurations given in
Xfig.~\ref{figstate}.
XMore generally we can say that every configuration we produce when trying to
Xsolve the 8-puzzle corresponds to one state in the state space. All these
Xstates together, i.e., {\em all possible\,} configurations make up the state
Xspace. It is possible of course to define the state space without explicitly
Xenumerating all states. Indeed, most of the time this is impossible
Xand the state space will be defined implicitly by providing rules specifying
Xhow each state can be derived from another. The state space may be small as in
Xthe case of the 8-puzzle, but for most every day problems or other board games
Xit is quite large (e.g., in chess the total number of possible board configurations,
Xthis is the total number of possible states, equals roughly $10^{120}$).
XObviously it would be impossible to explore the entire state space and often
Xthis is not needed, because we are interested in finding only one solution to
Xa problem, i.e., only one path leading from the start state to the goal state.
XThis means that we do not have to search the state space {\em exhaustively\,},
Xbut a small(er) portion instead. The problem of course is, which portion?
X
XBut before we are going to discuss this point it will be helpful to look
Xsomewhat further at the approach we have described so far. We said that to
Xsolve a problem it is necessary to represent the problem as a state space
Xsearch. That is, we define a start state, a goal state and a set of operators
Xthat transform one state into another. The actual search consists in moving
Xaround in the state space, looking for a path from the initial state to the
Xgoal state. In this case the search process proceeds forward because we start
Xwith the initial state and move towards the goal state. Hence it is called a
X{\em forward reasoning system\,}. The opposite behaviour is also possible: a
Xsystem starting the search with the goal state and moving backward to the
Xinitial state. In this method, often called {\em backchaining\,} we {\em reason
Xbackward\,} from the goal states. These two techniques can be combined,
Xresulting in a {\em bidirectional search\,}. In the case of the 8-puzzle it
Xdoes not make much difference if we move forward or backward, because about the
Xsame number of paths will be generated in either case, but some problems can be
Xsolved more efficiently when searching in one direction rather than the other
X(see Rich (1983), p.58).
X
XA different technique, or rather a different way to represent problems, that
Xhas not been mentioned so far is that of {\em problem reduction\,}. In this
Xtype of representation each operator used may divide the problem into a set of
Xsub-problems that each have to be solved seperately. Additionally,
Xthere may be restrictions on the order in which these sub-problems have to be
Xsolved\footnote{In the search class library it is assumed that sub-problems
Xmust be solved in the order in which they are generated.}. The object of problem
Xreduction is to eventually produce a set of {\em primitive problems\,}\label{primprob}
Xwhose solutions are regarded as trivial: at this stage the process of dividing
Xproblems into sub-problems halts.
X
XThese two approaches, state space search and problem reduction, are two of the
Xmost common methods used in problem representation, although variations of
Xthese approaches, as used in, e.g., game-playing are also possible
X(see Barr(1981), p.84ff., Ritch(1983), p.113ff., Nilsson(1971), p.137ff).
X
X\subsection{Trees and graphs}
X
XSo far we have seen that a state space representation consists of the following
Xcomponents:
X\begin{itemize}
X    \item The state descriptions.
X    \item A start state, describing the situation from which the
X    problem-solving process may start.
X    \item A goal state, describing an acceptable solution to the problem.
X    \item A set of operators describing how to transform one state into
X    another.
X\end{itemize}
X
X\bigskip\noindent
XAlso, we said that to solve a problem we do not need to search the entire state
Xspace but only that part which leads to a solution, i.e., we need to search for
Xan appropriate operator sequence, transforming the initial state through a
Xnumber of intermediate states into the goal state. To perform this search
Xsystematically we need a control strategy that decides which operator to apply
Xnext during the search. These strategies are commonly represented using
X{\em trees\,}\label{treeproc}\footnote{See Knuth(1979), p.305ff. for the concept
Xof trees in computer science.}: construct a tree with the initial state as its
Xroot, next generate all the offspring of the root by applying all of the
Xapplicable operators to the initial state, next for every leaf node generate its
Xsuccessors by applying all of the applicable operators, etc. When these steps
Xare performed a structure as displayed in fig.~\ref{figtree} structure will
Xarise.
X\begin{figure}
X\begin{center}
X\unitlength=0.70mm
X\special{em:linewidth 0.4pt}
X\linethickness{0.4pt}
X\begin{picture}(75.00,55.00)
X\put(10.00,10.00){\circle{0.00}}
X\put(10.00,10.00){\circle{10.00}}
X\put(30.00,10.00){\circle{10.00}}
X\put(50.00,10.00){\circle{10.20}}
X\put(70.00,10.00){\circle{10.00}}
X\put(20.00,30.00){\circle{10.00}}
X\put(60.00,30.00){\circle{10.00}}
X\put(40.00,50.00){\circle{10.00}}
X\put(37.00,46.00){\line(-3,-2){17.00}}
X\put(43.00,46.00){\line(3,-2){17.00}}
X\put(17.00,26.00){\line(-2,-3){7.33}}
X\put(23.00,26.00){\line(2,-3){7.33}}
X\put(57.00,26.00){\line(-2,-3){7.33}}
X\put(63.00,26.00){\line(2,-3){7.33}}
X\put(40.00,50.00){\makebox(0,0)[cc]{a}}
X\put(20.00,30.00){\makebox(0,0)[cc]{b}}
X\put(60.00,30.00){\makebox(0,0)[cc]{c}}
X\put(10.00,10.00){\makebox(0,0)[cc]{d}}
X\put(30.00,10.00){\makebox(0,0)[cc]{e}}
X\put(50.00,10.00){\makebox(0,0)[cc]{f}}
X\put(70.00,10.00){\makebox(0,0)[cc]{g}}
X\end{picture}
X    \caption{Start of a search tree}\label{figtree}
X\end{center}
X\end{figure}
XIn this representation every leaf node corresponds to a state, with the root
Xnode representing the initial state. Each operator application is represented by
Xa connection between two nodes.
X
XTrees are a special case of a more general structure called a {\em graph\,}
X\footnote{See Nilsson(1971), p.22, Barr(1981), p.25/26, Ritch(1983), p.63}.
XA tree is a graph each of whose nodes has a unique parent (except for the root
Xnode, which has no parent). Searching a tree is easier than searching a graph,
Xbecause when a new node is generated in the tree we can be sure it has not
Xbeen generated before. This is true because every node has only one parent, so
Xthere cannot be two or more different paths leading to the same node. In a graph,
Xhowever, nodes usually have more than one parent.  Therefore, when
Xsearching a graph one should make provisions to deal with these situations. For
Xexample, in the case of the 8-puzzle the same state may be generated by a
Xdifferent sequence of operators. That is, the same node may be part of several
Xpaths, e.g., when we apply operators 'move empty tile left, move empty tile down'
Xwe produce exactly the same node as in the sequence 'move empty tile down, move
Xempty tile left'. Continuing the processing of both these nodes (which are
Xreally the same node) would be redundant and a waste of effort. This can be
Xavoided at the price of additional bookkeeping. Instead of traversing a tree we
Xtraverse a {\em directed graph\,}\footnote{Knuth(1979), p.371.}: every time a
Xnode is generated we examine the set of nodes generated so far to see if this
Xnode already exists in the graph. If it does, we throw it away (note: see
Xpage~\pageref{graph-keep} for exceptions to this rule), if not, we add it to
Xthe graph.
X
XThis way we will also avoid a related problem: if we did not check
Xwhether a node had been generated before, the search process would very likely
Xend up in a {\em cycle\,}, in which the same set of nodes is generated over and over
Xagain. For instance, when we apply operator 'move empty tile left', next 'move
Xempty right' and next move 'empty tile left' etc. to the 8-puzzle, the
Xproblem-solving process would go on producing the same nodes without end. When
Xwe modify the search procedure as described above, this situation will never
Xarise, because we try to look up every node that is generated, before it is
Xadded to the graph.
X
XA special kind of graph is the {\em AND/OR graph\,}\label{andorgraph} that is used in
Xproblem-solving methods involving problem reduction. In the case of a normal
Xgraph, each node represents a different alternative state to be chosen next and
Xthe search process may continue along one of these nodes arbitratily. In a
Xproblem-reduction representation, however, we also need to deal with operators
Xthat divide the original problem into a set of sub-problems {\em each\,} of which
Xneed to be solved, instead of any of them. For example, suppose problem A can be solved
Xeither by solving problems B and C or by solving problems D and E or by solving
Xproblem F. This situation is depicted in fig.~\ref{figtree_2}.
X\begin{figure}
X\begin{center}
X\unitlength=0.70mm
X\special{em:linewidth 0.4pt}
X\linethickness{0.4pt}
X\begin{picture}(75.00,55.00)
X\put(10.00,10.00){\circle{10.00}}
X\put(25.00,10.00){\circle{10.00}}
X\put(40.00,10.00){\circle{10.00}}
X\put(55.00,10.00){\circle{10.00}}
X\put(70.00,10.00){\circle{10.00}}
X\put(40.00,50.00){\circle{10.00}}
X\put(36.00,47.00){\line(-3,-4){24.00}}
X\put(39.00,45.00){\line(0,-1){30.00}}
X\put(42.00,45.00){\line(2,-5){12.00}}
X\put(40.00,50.00){\makebox(0,0)[cc]{a}}
X\put(10.00,10.00){\makebox(0,0)[cc]{b}}
X\put(25.00,10.00){\makebox(0,0)[cc]{c}}
X\put(40.00,10.00){\makebox(0,0)[cc]{d}}
X\put(55.00,10.00){\makebox(0,0)[cc]{e}}
X\put(70.00,10.00){\makebox(0,0)[cc]{f}}
X\put(40.00,33.00){\line(6,1){6.00}}
X\put(37.00,45.00){\line(-1,-3){10.00}}
X\put(44.00,47.00){\line(4,-5){25.67}}
X\put(26.00,35.00){\line(6,-5){7.00}}
X\end{picture}
X    \caption{A structure showing alternative sets of subproblems for A.}\label{figtree_2}
X\end{center}
X\end{figure}
XIn fig.~\ref{figtree_2} the nodes which form a set that has to be solved
Xentirely are indicated by a special mark linking their incoming arcs. It is
Xusual, however, to introduce some extra nodes into the structure so that each
Xset containing more than one successor problem is grouped below its own
Xparent node. With this convention the structure of fig.~\ref{figtree_2}
Xbecomes as shown in fig.~\ref{figtree_3}. In this figure the added nodes
Xlabelled N and M serve as exclusive parents for sets \{B,C\} and \{D,E\}, respectively.
XThis way one can think of N and M and F as {\em OR\,} nodes, because any of them
Xmay be solved to solve node A. Problem N, however, is reduced to a single
Xset of sub-problems B and C, and {\em each\,} of these sub-problems must
Xbe solved to solve N. For this reason nodes B, C, D and E are called {\em AND\,}
Xnodes. In fig.~\ref{figtree_3} AND nodes are indicated by a mark on their
Xincoming arcs.
X\begin{figure}
X\begin{center}
X\unitlength=0.70mm
X\special{em:linewidth 0.4pt}
X\linethickness{0.4pt}
X\begin{picture}(80.00,65.00)
X\put(10.00,10.00){\circle{10.00}}
X\put(25.00,10.00){\circle{10.00}}
X\put(40.00,10.00){\circle{10.00}}
X\put(55.00,10.00){\circle{10.00}}
X\put(18.00,30.00){\circle{10.00}}
X\put(48.00,30.00){\circle{10.00}}
X\put(75.00,30.00){\circle{10.00}}
X\put(48.00,60.00){\circle{10.00}}
X\put(48.00,55.00){\line(0,-1){19.00}}
X\put(10.00,10.00){\makebox(0,0)[cc]{b}}
X\put(25.00,10.00){\makebox(0,0)[cc]{c}}
X\put(40.00,10.00){\makebox(0,0)[cc]{d}}
X\put(55.00,10.00){\makebox(0,0)[cc]{e}}
X\put(15.00,25.00){\line(-1,-2){5.00}}
X\put(20.00,25.00){\line(1,-2){5.00}}
X\put(50.00,25.00){\rule{1.00\unitlength}{0.00\unitlength}}
X\put(45.00,25.00){\line(-1,-2){5.00}}
X\put(50.00,25.00){\line(1,-2){5.00}}
X\put(45.00,56.00){\line(-6,-5){25.00}}
X\put(51.00,55.00){\line(6,-5){24.00}}
X\put(48.00,60.00){\makebox(0,0)[cc]{a}}
X\put(18.00,30.00){\makebox(0,0)[cc]{n}}
X\put(48.00,30.00){\makebox(0,0)[cc]{m}}
X\put(75.00,30.00){\makebox(0,0)[cc]{f}}
X\put(13.00,21.00){\line(1,0){9.00}}
X\put(43.00,21.00){\line(1,0){10.00}}
X\end{picture}
X    \caption{An AND/OR graph}\label{figtree_3}
X\end{center}
X\end{figure}
X
X\subsection{Basic search methods - depth-first, breadth-first}
X
XIn section 2 we described the process of generating a search tree, in this
Xsection we will give a more precise description of this process.
X\begin{itemize}
X    \item A start node is associated with the initial state description.
X
X    \item The successors of a node are generated by applying all of the
X    applicable operators to the state description associated with the node.
X    We will call this procedure the {\em expansion\,} of a node.
X
X    \item Pointers are setup from each successor back to its parent node.
X    These pointers indicate the solution path in the game tree, leading from
X    the goal node, once it is finally found, back to the start.
X
X    \item Every successor node is checked to see if it is a goal node. When a
X    goal node has been found the process of expanding nodes finishes and we trace
X    back the solution path through the pointers.
X\end{itemize}
X
X\bigskip\noindent
XThese are the basic elements of a problem-solving process, but the order in
Xwhich nodes are to be expanded is still left open. We may choose, for instance,
Xto search one entire branch of the tree before examining nodes in the other
Xbranches. Alternatively, we may decide to expand all nodes that are on the
Xsame level, in different branches. The first option would result in what is
Xcalled a {\em depth-first\,} search: the most recently generated node gets
Xexpanded first. In a {\em breadth-first\,} search, the second option, nodes are
Xexpanded in the order in which they are generated.
X
X\subsection{Finding an optimal solution, uniform-cost search}
X
XIt should be noted that for some problems we are not interested in finding
X{\em any\,} solution, but rather the {\em optimal\,} or {\em best\,} one. What
X'best' means depends on the problem at hand, but for now we will call a
Xsolution path optimal if it contains the least possible number of nodes leading
Xto the goal node. Later on we will refine our definition to include a
Xdifferent, but related type of problems. In the case of a depth-first search we
Xcannot guarantee that the best solution will be found. This is because every
Xbranch is examined seperately, so if the search process finds a goal node in
Xone branch it will terminate. But it may well be that a better solution is
Xlocated in a different branch. Breadth-first search on the other hand is
Xguaranteed to find the shortest path, because it expands all nodes on one
Xlevel before advancing to the next.
X
XFor some problems, however, finding the best solution does not mean finding the
Xshortest path, but rather the {\em cheapest\,} path. This is true for instance
Xwhen we need to find the shortest path from one city to another. In this case
Xthere may be several routes that can be used to get from city A to city B,
Xvisiting other cities along the way. Now suppose the cities are nodes in a
Xsearch tree, clearly what we want is not the smallest number of nodes (cities)
Xthat make up a path from A to B, but the shortest route. To solve problems
Xlike this one we need to associate {\em costs\,} with the arcs in the tree (in
Xthis case the costs will represent the distances between the cities). The
Xobject is to find a path having the least cost.
X
XA more general version of the breadth-first method, called the {\em
Xuniform-cost search method\,} is guaranteed to find a path of minimal cost
Xfrom the start node to a goal node. Instead of expanding paths of equal length
Xlike the breadth-first method, this method expands paths of equal cost. To
Xcompute the cost of a path {\em s\,} to a node {\em n\,} we will use the
Xfunction {\em g(n)\,}\label{gfunc}. The cost associated with a node will consist
Xof the cost associated with its parent plus the cost of getting from the parent to
Xthis node. Using this method to order the set of nodes we are sure the
Xuniform-cost method expands nodes in order of increasing g(n).
X
XOne \label{graph-keep} should note that the graph search technique that we
Xdescribed earlier must be modified when we are looking for an optimal solution.
XWe said that during a graph search every node that is generated twice can
Xsimply be thrown away. If we would use this technique in a uniform-cost
Xsearch we could never guarantee to find the cheapest path. As said, in a graph
Xthere may be multiple paths leading to the same node. But each of these has
Xits own (possibly different) cost. So if we throw away a node without paying attention to this
Xfact we may be missing a better solution without ever noticing. Therefore,
Xthe graph search procedure must be modified in the following way: every time
Xa new node is generated we check whether it already exists in the graph. If not,
Xwe add it. If it does, we compare the cost of the old node and the cost of the
Xnewly generated node. If the old node is better (cheaper) nothing has to be
Xdone, if it is worse we change its cost and direct its pointer to the parent on
Xthe least costly path that has just been found.
X
X\subsection{Blind search vs heuristic search, best-first search}
X
XAll of the methods described so far are called {\em blind-search procedures\,} because they
Xdo not use any specific information about the problem to be solved, i.e, the
Xsearch process just continues until it happens on a solution: it is not
Xdirected in some way to the goal. The advantage of blind-search procedures is
Xthat they are easy to implement and may find a solution quickly for small
Xproblems. The obvious disadvantage of these methods is that they may be led
Xastray, expanding a lot of nodes that are not part of the solution path. For
Xexample, when traversing a tree in depth-first order we dive into the
Xleft most branch, this is fine if we happen to find a solution there. But suppose
Xthe goal node is located in a different part of the tree, e.g., at the right most
Xbranch. In this case we will have searched the entire tree before getting
Xon the right track. It would have been much better if we had known in advance
Xwhich way to go. But of course, this is impossible; if we had known this
Xwe would never have to {\em search\,} for a solution. Still, there may be
Xsituations where we do not know exactly where to go, but can give an estimate
Xof how far a node is removed from the goal node and hence determine if it is on
Xthe (best) solution path. Using this information it is possible to improve the
Xefficiency of the search process. Here, we have introduced the idea of using a
X{\em heuristic\,}.
X
XA heuristic is a rule of thumb, a technique that improves the efficiency of a
Xsearch process, possibly by sacrificing claims to completeness
X[Rich 1983, 35]. This means that, like all rules of thumb, heuristics may lead
Xthe search in the most promising way, finding a solution quickly, but also
Xthat they may take a wrong turn (but still leading to the goal) or lead to
Xdeadends. A good way to use heuristic information is by means of a {\em heuristic
Xfunction\,} that evaluates every node that is being generated, i.e. that determines
Xthe goodness or badness of a node. Using a heuristic function it will be
Xpossible to conduct the search in the most profitable direction, by suggesting
Xwhich path to follow first when more than one is available.
X
XWe will define a heuristic function {\em f(n)\,}\label{ffunc} being the sum of two components
X{\em g(n)\,} and {\em h(n)\,}:
X    \[ f(n) = g(n) + h(n) \]
XFunction g(n) is the same as the one described in section~\ref{gfunc}: a measure of the cost
Xof getting from the initial state to the current node. The function h(n) is an
Xestimate of the additional cost of getting from the current node to a goal
Xstate. Put differently, h(n) is the function in which the real heuristic
Xknowledge is imbedded. Using f(n) we are able to order the set of nodes waiting
Xfor expansion, by convention this will be done this in {\em increasing\,} order.
XAn algorithm can then be used to select the node having the smallest f(n) value
Xnext for expansion. One of the methods that uses this technique is the
X{\em best-first search method\,} or {\em $A{^*}$ algorithm\,}.
X
XIt is important to keep in mind that most heuristics are imperfect and that,
Xinevitably, the search process will be affected by this. In general, a search
Xalgorithm is called {\em admissible\,} if for any graph it terminates in an
Xoptimal path to a goal whenever a path exists. Using a heuristic function
Xto conduct the search process we cannot always make this claim because the
Xbehaviour of the search will depend on how accurately the function evaluates
Xnodes. If we use a perfect heuristic function we are guaranteed to find an
Xoptimal solution, but heuristics having this property are hard to find.
XFurthermore, the difficulty of computing the function's result affects the
Xtotal computational effort of the search process. Also, it may be less
Ximportant to find a solution whose cost is absolutely minimal than to find a
Xsolution of reasonable cost within a reasonable amount of time. In this case
Xone may prefer a heuristic function that evaluates nodes more accurately in
Xmost cases, but sometimes overestimates the distance to the goal, thus resulting
Xin an inadmissible algorithm. Most of the time we need to make this sort of
Xcompromise: the efficiency of the search process needs to be improved at the
Xsacrifice of admissibility (see Barr(1981), p.65/66, Nilsson(1971), p.59ff.)
X
X
X\section{The search class library}
X
X\subsection{Why C$^{++}$?}
X
XOne of the things to be explained will be the reason why we decided to use C$^{++}$
Xfor programming an AI-type problem while so many specialized AI programming
Xlanguages are available. For one thing, we wanted to know how much more effort
Xit would be to use a lower level programming language (lower compared to AI
Xprogramming languages like Prolog, that is) to program this type of problem.
XC$^{++}$ seemed excellent for this job because it is based on C, a third
Xgeneration programming language, and also because it follows the object
Xoriented paradigm, meaning that it supports a higher level of abstraction, in
Xthe case of OOP: the combination of procedural and data abstraction. But the
Xmain reason why we decided to use C$^{++}$ is that it supports {\em inheritance\,}.
XThis feature makes it possible to easily make use of existing software when
Xdeveloping new applications. Combined with the possibility to define {\em virtual\,}
Xfunctions this makes it possible to design foundation classes that are of no
Xuse in themselves, but can be easily extended for real applications.
X
XThe main objective was to seperate the problem-solving process that we
Xdescribed above and the representation of the problem itself. In chapter 2 we
Xshowed that a lot of problems can be solved using standard techniques, e.g.,
Xthe state space representation and search. It seemed useful therefore, to
Xdevelop some basic routines offering a number of search methods that could
Xeasily be used when designing problem-solving software. And this is exactly
Xwhat the foundation classes are for. Each of them implements a particular search
Xalgorithm while leaving open the exact nature of the problem to be solved. So,
Xusing these classes it will be possible, just like in, e.g., Prolog, to
Xconcentrate on the representation of the problem at hand without worrying
Xabout how it has to be solved. But unlike Prolog the user need not make use
Xof a fixed search method (in Prolog: depth-first), but may choose one that
Xsuits the problem best.
X
X\subsection{Techniques used, hierarchy of the search classes.}
X
XIn this section we describe a basic technique used in the different search
Xclasses and explain how these classes relate to each other.
X
XIn writing the search engine we followed the procedure outlined in
Xsection~\ref{treeproc} except that we do not build an actual tree-like structure.
XInstead, we use two lists, called OPEN and CLOSED. OPEN is a list containing nodes
Xready for expansion and CLOSED a list of those nodes that already have had the
Xexpansion procedure applied to them. The algorithm forming the search procedure
Xconsists of the following steps:
X\begin{enumerate}
X    \item Put the start node on OPEN.
X    \item Get the first node from OPEN. If OPEN is empty exit with failure,
X    otherwise continue.
X    \item Remove this node from OPEN and put it on CLOSED; call this node
X    {\em n\,}.
X    \item Expand node {\em n\,}, generating all of its successors. This is done
X    by calling function do\_operator() or expand().
X    \item Provide every successor with a pointer back to {\em n\,} and pass it
X    to function add() that may or may not put the node on OPEN.
X    \item Check each successor to see if it is a goal node. If so exit,
X    otherwise go to 2.\footnote{This step is not done in the bidirectional and
X    AND/OR search algorithms. They have a different way of determining whether
X    the problem is solved or not.}
X\end{enumerate}
X
X\bigskip\noindent
XThe algorithm that we just described can be found in function solve() which is
Xa member-function of class {\em SEARCH\_\,} and also of class {\em BISEARCH\_\,}
Xand of class {\em AOSEARCH\_\,}. These three classes are the most important
Xclasses in the search class hierarchy, each implements basic routines
Xneeded by different search algorithms, as follows:
X\begin{itemize}
X    \item SEARCH\_ : basic class for uni-directional search routines.
X    \item BISEARCH\_ : basic class for bi-directional search routines.
X    \item AOSEARCH\_ : basic class for AND/OR search routines.
X\end{itemize}
X
X\bigskip\noindent
XThe names of these three classes correspond to three different {\em kinds \,}
Xof search techniques that are offered to the user to solve different kinds
Xof problems: uni-directional, i.e., normal search, bi-directional search and
XAND/OR search. However, these classes should never be used for direct derivation,
Xthey must be thought of as skeleton classes that outline the overall search
Xmethod. Other classes, derived from these three basic classes, implement the
Xactual search algorithms, but before we are going to describe these classes we
Xmust first introduce another important class, class {\em NODE\_,}.
X
XClass NODE\_ specifies a general structure that is to be processed by class SEARCH\_
X(and by class BISEARCH\_). Class NODE\_ is itself derived from class SVOBJECT\_
X(sortable object), which, in turn, is derived from class VOBJECT\_. Class
XNODE\_ may be thought of as an abstraction of the nodes in a search tree or,
Xequivalently, of the states in a state space. When designing problem-solving
Xsoftware most time will be spent in finding a good representation of these
Xnodes/states. Once this representation is found it must be turned into a class
Xthat is derived from class NODE\_ (or from one of its derivatives, depending on
Xthe search algorithm that is used, see later), like this:
X\begin{verbatim}
Xclass PNODE_ : public NODE_
X{
X   ...
X};
X\end{verbatim}
X
XAs said, class SEARCH\_, BISEARCH\_ and AOSEARCH\_ are the most fundamental
Xsearch classes and it should never be necessary to derive directly from these
Xclasses, but rather from one of the following classes, each derived from class
XSEARCH\_:
X\begin{itemize}
X    \item DEPTH\_TREE\_ and DEPTH\_GRAPH\_. These two classes implement a
X    depth-first search, by creating a search tree or graph, respectively.
X    \item BREADTH\_TREE\_ and BREADTH\_GRAPH\_. These two classes implement a
X    breadth-first search, by creating a search tree or graph, respectively.
X    \item UNICOST\_TREE\_ and UNICOST\_GRAPH\_. These two classes implement a
X    uniform-cost search, by creating a search tree or graph, respectively.
X    \item BEST\_. This class implements a best-first search.
X\end{itemize}
X
X\bigskip\noindent
XOr from one of the following classes, derived from class BISEARCH\_:
X\begin{itemize}
X    \item BIDEPTH\_TREE\_ and BIDEPTH\_GRAPH\_. These two classes implement a
X    depth-first bidirectional search, by creating two search trees or graphs,
X    respectively.
X    \item BIBREADTH\_TREE\_ and BIBREADTH\_GRAPH\_. These two classes implement
X    a bidirectional breadth-first search, by creating two search trees or graphs,
X    respectively.
X\end{itemize}
X
X\bigskip\noindent
XOr from one of the classes derived from class AOSEARCH\_:
X\begin{itemize}
X    \item AODEPTH\_TREE\_. This class implements a depth-first AND/OR search,
X    by creating a depth-first AND/OR tree.
X    \item AOBREADTH\_TREE\_. This class implements a breadth-first AND/OR
X    search, by creating a breadth-first AND/OR tree.
X\end{itemize}
X
X\bigskip\noindent
XTo make use of any of the search algorithms that the search class library offers
Xthe user must derive a class from one of the classes above, for instance:
X\begin{verbatim}
Xclass PUZZLE_ : public DEPTH_GRAPH_
X{
X   ...
X};
X\end{verbatim}
X
XThe first four sets of classes, DEPTH\_TREE\_, DEPTH\_GRAPH\_, BREADTH\_TREE\_
Xand BREADTH\_GRAPH\_ and also the the classes derived from BISEARCH\_, i.e.,
XBIDEPTH\_TREE\_, BIDEPTH\_GRAPH\_, BIBREADTH\_TREE\_ and BIBREADTH\_TREE\_
Xmust be used in conjuntion with class NODE\_. This means that when performing,
Xfor instance, a depth-first search the class that is used to represent the nodes
Xin the search tree must be derived from NODE\_ (see first example above and also
Xdemo one and demo two).
X
XClass UNICOST\_TREE\_, UNICOST\_GRAPH\_ and BEST\_ require the nodes to have
Xsome special features. They must be used in conjunction with a derivative
Xof class NODE\_, class UNI\_NODE\_ or class BEST\_NODE\_, respectively (see
Xdemo four and five for classes that are derived from one of these two).
X
XLastly, class AODEPTH\_TREE\_ and AOBREADTH\_TREE\_ must be used in
Xconjunction with classes ORNODE\_, a derivative from class AONODE\_, which is
Xderived from class NODE\_ (see demo seven for a class derived from class
XORNODE\_). Another derivative from class AONODE\_ is class ANDNODE\_, but this
Xclass should never be used for derivation, its use will be explained later.
X
XTo summarize:
X\begin{itemize}
X    \item The depth-first and breadth-first search routines (both
X    uni-directional and bi-directional) must be used in combination with
X    class NODE\_.
X    \item The uniform-cost search routines must be used in combination with
X    class UNI\_NODE\_.
X    \item The best-first search routine must be used in combination with class
X    BEST\_NODE\_.
X    \item The AND/OR search routines must be used in combination with class
X    ORNODE\_.
X\end{itemize}
X
X\bigskip\noindent
X
X\subsection{How to use the search class library.}
X
XNow that we have introduced the search classes and have outlined their
Xhierarchy we will explain how they can and should be used. As said, class
XSEARCH\_\footnote{we will take this class as an example, what we tell here
Xapplies also to class BISEARCH\_ and class AOSEARCH\_; important differences
Xwill be discussed later.} is one of the most important and most basic classes.
XOne of the tasks of class SEARCH\_ is to keep track of the number of operators
Xthat may be applied to the nodes (in the expansion procedure). It receives this
Xinformation through its constructor, therefore, every class that is derived from SEARCH\_
Xmust call SEARCH\_'s constructor, passing to it the number of operators, as an
Xinteger. The node representing the initial state and the node representing the
Xgoal state must also be passed to this constructor, except when deriving from
Xclass AOSEARCH\_, in this case only the start node and number of operators
Xshould be passed\footnote{A problem that is to be solved using the problem reduction
Xrepresentation, i.e., using an AND/OR search algorithm, does not have a goal
Xstate, because to solve the problem we do not look for a goal state, but need to
Xdivide the problem into sub-problems that may or may not be solvable.}.
XBut as we never derive directly from class SEARCH\_ we do not pass this
Xinformation to SEARCH\_ directly, but through one of its derivatives,
Xusing the constructor of the derived class. Suppose we build a class called
XPUZZLE\_, derived from class DEPTH\_GRAPH\_, then this could be a constructor
Xof PUZZLE\_:
X\begin{verbatim}
XPUZZLE_::PUZZLE_(PNODE_ *start, PNODE_ *goal)
X    :DEPTH_GRAPH_(start, goal, 4)
X{                // pass start node, goal node and number of
X}                // of operators to DEPTH_GRAPH_ 's construc-
X                 // tor (that will pass them on to SEARCH_)
X\end{verbatim}
X
XAs PUZZLE\_ is ultimately derived from SEARCH\_ it must implement all
Xvirtual functions (in SEARCH\_) that are still left undefined (i.e., that are
Xnot instantiated by one of SEARCH\_'s derivatives). In the case of the DEPTH\_
Xand BREADTH\_ classes there are none. But some of the other search classes have
Xa couple of virtual functions that must implemented by the user. Class UNICOST\_TREE\_
Xand UNICOST\_GRAPH\_ require the implementation of funcion compute\_g() and class
XBEST\_ of both this function and of function compute\_h(). Both of these functions
Xserve to compute a cost associated with a node: compute\_g() computes the cost
Xof getting from a node's parent to the node itself, i.e. the cost associated
Xwith the arc connecting both nodes, and compute\_h() computes the
Xheuristic value of a node (see section~\ref{gfunc} and section~\ref{ffunc}, but
Xnote that function compute\_g() must only compute the second half of g(n)):
X\begin{verbatim}
Xint compute_g(const NODE_ &)   // computes cost of getting from
X                               // node's parent to node itself
Xint compute_h(const NODE_ &)   // computes heuristic value of
X                               // a node
X\end{verbatim}
X
XThe search classes derived from BISEARCH\_ do not have any non-defined virtual
Xfunctions left. But the last set of classes, AODEPTH\_TREE\_ and AOBREADTH\_TREE\_,
Xrequire the implementation of function is\_terminal() which checks whether a
Xnode represents a terminal node:\footnote{a terminal node is a node that
Xrepresents a primivite problem in a problem reduction presentation, see
Xsection~\ref{primprob}}
X\begin{verbatim}
Xint is_terminal(const AONODE_ &)    // node is terminal node?
X                                    // 1 : yes, 0 : no
X\end{verbatim}
X
XJust like class SEARCH\_ class NODE\_ also has a number of virtual functions
Xthat must be implemented by the user. One of the most important of these is
Xdo\_operator() that is used for node expansion (step 4 in the algorithm).
X\begin{verbatim}
XNODE_ *do_operator(int) const   // apply operator n and
X                                // return new node or NULL
X\end{verbatim}
XNote that the object returned by do\_operator() must have been allocated in memory.
XFunction do\_operator() is called by SEARCH\_::solve(), that passes do\_operator()
Xan integer representing one of the operators. This way the operators are numbered,
Xstarting at 0 and ending at number of operators minus 1. If the operator can be
Xapplied do\_operator() should return a new node (allocated by new), if not, it
Xshould return NULL. This is one way a node may be expanded. Another possibility
Xis by use of funtion expand(). This function is similar to do\_operator(), except
Xthat it returns a linked list of all of its successors, instead of one
Xsuccessor at a time. This is useful when dealing with problems that do not use
Xoperators or that have a variable number of operators.
X\begin{verbatim}
XNODE_ *expand(int) const  // expand node and return all of
X                          // its successors in a linked list
X\end{verbatim}
XThe linked list that expand() returns must be built using the next-pointer
Xfield in NODE\_ (NODE\_ *next). An example of how funtion expand() may be used
Xand how to build the linked list is given in demo five.
X
XApart from do\_operator() there are two other functions, which are virtual in
Xclass NODE\_, that must be implemented. One of these, equal(), tests whether
Xtwo nodes are the same, it must return 1 if true and 0 if not. The other one,
Xdisplay() is used to display a node:
X\begin{verbatim}
Xint equal(const VOBJECT_ &) const  // nodes are the same node?
X                                   // 1 : true, 0 : false
Xvoid display() const               // display the node
X\end{verbatim}
XNote that the argument in equal() is VOBJECT\_ and not NODE\_, this is because
Xequal() is inherited by NODE\_ from VOBJECT\_.
X
XUsing these funtions the implementation of user-defined problems should be
Xstraightforward. Still, it will be helpful to make some remarks concerning the
Xthe AND/OR search classes. In section~\ref{andorgraph} we explained how an
XAND/OR graph may be created and we introduced the concept of AND-nodes and
XOR-nodes. The meaning of these terms is slightly different in the
Ximplementation of the AND/OR search classes. Here we will call all nodes OR-nodes,
Xexcept those nodes that connect a set of sub-problems (nodes N and M in
Xfig.~\ref{figtree_3}), which are to be called AND-nodes. This relates to the
XAND/OR search classes in the following way. As said, the user-definable objects
Xthat serve to represent the nodes in the search tree must be derived from
Xclass ORNODE\_. But now suppose that some node A may be reduced to the set of
Xsub-problems \{B,C,D\}. Normally we would call B, C and D AND-nodes, but here,
Xas said, they are called OR-nodes. The next step is to create a node that
Xconnects nodes B, C and D and this node is called an AND-node. This AND-node
Xmust created by calling {\bf new ANDNODE\_() } and adding to this node all of its
Xsuccessors, in this case node B, C and D, by calling addsucc(), like this:
X\begin{verbatim}
XANDNODE_ *andnode;
X
Xandnode = new ANDNODE_;      // it must be allocated
Xandnode->addsucc(node_a);
Xandnode->addsucc(node_b);
Xandnode->addsucc(node_c);
X
Xreturn(andnode);
X\end{verbatim}
X
XWhen the number of successors is known in advance a different possibility is to
Xpass this number to the constructor of ANDNODE\_ and then using setsucc() to pass
Xthe successors, like this:
X\begin{verbatim}
XAND_NODE_ *andnode;
X
Xandnode = new ANDNODE_(3);      // we will add 3 nodes
Xandnode->setsucc(0, node_a);    // we start counting at 0
Xandnode->setsucc(1, node_b);
Xandnode->setsucc(2, node_c);
X
Xreturn(andnode);
X\end{verbatim}
X
XThe only problem that may, and most of the time will, arise is that we don't
Xknow before hand what kind of node will be produced, an AND-node or and OR-node,
Xso we do not know if we need and AND\_NODE\_ or an OR\_NODE\_ pointer (this is
Xespecially true when building a linked list of nodes as in expand()). But this
Xis easily solved when we use a AONODE\_ pointer, because both AND\_NODE\_ and
XOR\_NODE\_ are derived from this class, and next casting the result if needed.
XAn example of this technique is given in demo seven.
X
XOne thing has not been mentioned yet: how must the search be started? This is
Xdone by a call to function generate(), a member function of class SEARCH\_. For
Xexample:
X\begin{verbatim}
XPUZZLE_
X    puzzle;
X....
Xpuzzle.generate();      // start looking for a solution
X\end{verbatim}
X
X\subsection{Include and library files.}
X
XIn this section we describe which files must be included and which files must
Xbe linked when developing problem solving software using the search class
Xlibrary.
X
XAll include files needed by the search class library are in directory /include.
XMost of these are used internally and the only two files the user needs to
Xconsult are tree.h and graph.h:
X\begin{itemize}
X    \item tree.h. Include this file when using one of the tree search
X    algorithms.
X    \item graph.h. Include this file when using one of the graph search
X    algorithms.
X\end{itemize}
X
X\bigskip\noindent
X
XLibrary files are located in directory /lib which contains two library files
X(only one in UNIX):
X\begin{itemize}
X    \item searchs.lib. Library containing all objects needed by the different
X    search classes, compiled in the small memory model.
X    \item searchc.lib. Idem, but compiled in the compact memory model.
X\end{itemize}
X
X\bigskip\noindent
X
X
X\section{Bibliography}
X
XWinston, P.H. (1984), {\em Artificial Intelligence\,} (2nd ed.), London:
XAddison-Wesley.\\
XBarr, A., Feigenbaum, E.A. (1983), {\em The Handbook of Artificial
XIntelligence}, Los Altos: Kaufmann.\\
XNillson, N.J. (1971), {\em Problem Solving Methods in Artificial
XIntelligence\,}, New York: McGraw-Hill.\\
X              (1986), {\em Principles of Artifial Intelligence\,}, Los Altos:
XKaufmann.\\
XKnuth, D.E. (1979), {\em The Art of Computer Programs\,} (2nd ed.). London:
XAddison-Wesley.\\
XPearl, J. (1984), {\em Heuristics: Intelligent Strategies for Computer Problem
XSolving\,}, London: Addison-Wesley.\\
XRich, E. (1983), {\em Artificial Intelligence\,}, New York: McGraw-Hill.
X
X\end{document}
X
END_OF_FILE
  if test 43426 -ne `wc -c <'doc/search.tex'`; then
    echo shar: \"'doc/search.tex'\" unpacked with wrong size!
  fi
  # end of 'doc/search.tex'
fi
if test -f 'include/list.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'include/list.h'\"
else
  echo shar: Extracting \"'include/list.h'\" \(4228 characters\)
  sed "s/^X//" >'include/list.h' <<'END_OF_FILE'
X#ifndef _list_H_
X#define _list_H_
X
X#include <stdio.h>
X#include "object.h"
X
X
X/*                    LIST_NODE_
X
X    Class LIST_NODE_ defines objects that make up a linked list, it should
X    be used in conjuntion with class LIST_. Class LIST_NODE_ stores data
X    in the form of pointers to VOBJECT_'s. A special feature of this class
X    is that the data may or may not be deleted when the LIST_NODE_ pointing
X    to this data gets destroyed. This behaviour depends on the value of
X    the static variable NODE_::destroy, which is set by class LIST_.
X
X*/
X
X#define DEALLOC 0
X#define NODEALLOC 1
X
Xclass LIST_NODE_
X{
X    public:
X        LIST_NODE_();
X        LIST_NODE_(VOBJECT_ &);
X        LIST_NODE_(VOBJECT_ &, LIST_NODE_ *, LIST_NODE_ *);
X        ~LIST_NODE_();
X        void setdata(VOBJECT_ &);
X        VOBJECT_ *getdata() const;
X        void setnext(LIST_NODE_ *);
X        LIST_NODE_ *getnext() const;
X        void setprev(LIST_NODE_ *);
X        LIST_NODE_ *getprev() const;
X        static int destroy;            // should data be deleted when
X    private:                // listnode is destroyed?
X        VOBJECT_ *data;            // pointer to data field
X        LIST_NODE_ *next,
X                   *prev;
X};
X
X
X/*
X            LIST_
X
X    Class LIST_ creates an un-ordered list of (pointers to) VOBJECT_'s.
X    This means that objects that are to be stored in a LIST_ object must
X    derived from class VOBJECT_.
X
X    When objects are removed from a list (by calling, e.g, remove_head())
X    they may be kept or destroyed, i.e., get deallocated. This behaviour
X    depends on the value passed to the remove_ and clear() functions, the
X    default value is NODEALLOC: don't destroy the object.
X
X    Similarly, objects may be kept or destroyed when the destructor of the
X    list is called, this behaviour depends on the value that is initially
X    passed to LIST_'s constructor, or on the value passed to setdestruct(int):
X    DEALLOC_ON_DESTRUCT or NO_DEALLOC_ON_DESTRUCT, by default the objects
X    in the list will get deallocated when LIST_'s destructor is called.
X
X*/
X
X#define DEALLOC_ON_DESTRUCT 0
X#define NO_DEALLOC_ON_DESTRUCT 1
X
Xclass LIST_
X{
X    friend class LIST_ITERATOR_;
X
X    public:
X        LIST_(int dstr = DEALLOC_ON_DESTRUCT);
X              // deallocate objects on destruct, default
X        ~LIST_();
X
X        void addtohead(VOBJECT_ &);
X        void addtotail(VOBJECT_ &);
X
X        VOBJECT_ *gethead() const;
X    VOBJECT_ *gettail() const;
X    int getcount() const;
X        VOBJECT_ *lookup(VOBJECT_ &);
X
X        void remove_head(int destroy = NODEALLOC);
X               // destroy : DEALLOC = object gets deallocated
X               // NODEALLOC = don't deallocate object, default
X        void remove_tail(int destroy = NODEALLOC);
X        void remove_found(int destroy = NODEALLOC);
X    void clear(int destroy = NODEALLOC);
X
X    void setdestruct(int);          // get value of deallocondestr
X    int getdestruct() const;    // set value of deallocondestr
X
X    protected:         // protected because SORTEDLIST_ needs access
X    void remove_node(LIST_NODE_ *, int dstr);
X
X    LIST_NODE_ *head,
X                   *tail,
X                   *found;
X        int nodecount,
X        deallocondestr;
X};
X
X
X
X/*
X                  SORTEDLIST_
X
X   Class SORTEDLIST_ creates an ordered list of (pointers to) SVOBJECT_ 's.
X   Therefore, objects to be stored in a SORTEDLIST_ object muct be derived
X   from class SVOBJECT_. Class SORTEDLIST_ is derived from class LIST_.
X
X*/
X
Xclass SORTEDLIST_ : public LIST_
X{
X    public:
X        SORTEDLIST_(int dstr = DEALLOC_ON_DESTRUCT);
X        void insert(SVOBJECT_ &);
X};
X
X
X
X/*
X          LIST_ITERATOR_
X
X    Class LIST_ITERATOR_ iterates through the objects stored in a list.
X    While walking through the list objects may be removed, by calling
X    remove(), see also list.h! When an object is removed the current
X    pointer of the list iterator moves on one node (or back one node if it
X    is located on the last node).
X
X*/
X
Xclass LIST_ITERATOR_
X{
X    public:
X    LIST_ITERATOR_(LIST_ &);
X    VOBJECT_ *getfirst();
X    VOBJECT_ *getlast();
X    VOBJECT_ *getnext();
X    VOBJECT_ *getprev();
X    VOBJECT_ *getitem();
X    void remove(int destroy = NODEALLOC);
X        // remove current object and move on one node
X    private:
X    LIST_ *mine;
X    LIST_NODE_ *current;
X};
X
X#endif
END_OF_FILE
  if test 4228 -ne `wc -c <'include/list.h'`; then
    echo shar: \"'include/list.h'\" unpacked with wrong size!
  fi
  # end of 'include/list.h'
fi
if test -f 'include/nodes.h' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'include/nodes.h'\"
else
  echo shar: Extracting \"'include/nodes.h'\" \(6434 characters\)
  sed "s/^X//" >'include/nodes.h' <<'END_OF_FILE'
X#ifndef _nodes_H_
X#define _nodes_H_
X
X#include <stdio.h>
X#include <stdlib.h>
X#include "object.h"
X
X/*                        NODE_
X
X    The base class NODE_ is derived from class SVOBJECT_ (sortable object)
X    and defines basic states that will be generated during the search process.
X    In other words, it defines the (abstract, since we're dealing with a base
X    class) objects that the search space consists of. Every class that is
X    derived from NODE_ must have the following functions:
X
X    do_operator(): generates and returns one successor, i.e., a new state,
X                   when operator n is applied. Returns NULL when operator n
X                   cannot be applied.
X    or expand():   returns a linked list of successors (the linked list must
X                   be built by using the NODE_ *next field). This function
X                   is an alternative for do_operator(), either one has to be
X                   implemented!
X    equal():       determines if 2 objects are the same, must return 1 if
X                   true and 0 if false.
X    display():     displays the object.
X
X    Note that the virtual function eval() that is used to determine the order
X    of objects is not actually used in class NODE_, therefore it just
X    returns 1 (it can't be pure virtual because is it called in solve()).
X    For a real usage of this function see class BEST_NODE_ and UNI_NODE_.
X
X*/
X
Xclass NODE_ : public SVOBJECT_
X{
X    public:
X        NODE_();
X
X        virtual NODE_ *do_operator(int) const;
X    virtual NODE_ *expand(int) const;
X         // both of these not pure virtual since either may be implemented
X    virtual int equal(const VOBJECT_ &) const = 0;
X        virtual int eval(const SVOBJECT_ &) const;
X             // not pure virtual since it's only needed in shortest path search
X    virtual void display() const = 0;
X
X    NODE_ *getnext() const;
X    void setnext(NODE_ *);
X        void setparent(NODE_ *);
X        NODE_ *getparent() const;
X    private:
X        NODE_ *parent,     // to trace the solution path
X              *next;
X};
X
X
X
X/*                        UNI_NODE_
X
X    The base class UNI_NODE_ is derived from class NODE_ and defines
X    a special kind of NODE_'s: nodes that will be generated during the
X    search process of a uniform cost search. These nodes will be placed in
X    an ordered list, the order of 2 nodes is determined by eval() based
X    on their 'g-values'.
X
X    G is a cost associated with the node: it's a measure of the cost
X    of getting from the start node to the current node. This value is computed
X    by compute_g().
X
X*/
X
Xclass UNI_NODE_ : public NODE_
X{
X    public:
X        UNI_NODE_();
X        int eval(const SVOBJECT_ &) const;
X        int get_g() const;
X        void set_g(int);
X    private:
X        int g;        // cost of getting from the start node to this node
X};
X
X
X
X/*                       BEST_NODE_
X
X    The base class BEST_NODE_ is derived from class UNI_NODE_ which in
X    turn is derived from class NODE_. Class BEST_NODE_  defines
X    a special kind of NODE_'s: nodes that will be generated during the
X    search process of a best first search. These nodes will be placed in
X    an ordered list, the order of 2 nodes is determined by eval() based
X    on their 'f-values'.
X
X    G (see unode.h) and F are costs associated with the node. G is a
X    measure of the cost of getting from the start node to the current node
X    and F the sum of G and H, the estimated cost of getting from the current
X    node to the goal node. These values are computed by compute_g() and
X    compute_h() respectively.
X
X*/
X
Xclass BEST_NODE_ : public UNI_NODE_
X{
X    public:
X        BEST_NODE_();
X        int eval(const SVOBJECT_ &) const;
X        int get_f() const;
X        void set_f(int);
X    private:
X        int
X            f;          // f is g + h
X};
X
X
X
X/*                       AONODE_
X
X    Class AONODE_ defines nodes that will be generated in an AND-OR search
X    process. It is derived from class NODE_. AONODE_ is a base class for
X    class ORNODE_ and ANDNODE_ and should never be used for direct derivation.
X
X*/
X
X#define OR 0
X#define AND 1
X#define UNSOLVABLE 0
X#define SOLVED 1
X#define DUNNO -1
X
Xclass AONODE_ : public NODE_
X{
X    public:
X    AONODE_();
X    AONODE_(int);
X    AONODE_(int, int);
X
X        void settype(int);
X        void setsolved(int);
X        int getsolved() const;
X        int gettype() const;
X        int getn_left() const;
X    void incn_left();
X        void decn_left();
X    private:
X        int type,        // is this an AND node or OR node?
X            solved,      // is the node labeled SOLVED, UNSOLVED or DUNNO?
X            n_left;      // number of successors left to be solved (AND node),
X                         // or: number of successors that may be still be
X                         // solved (OR node)
X};
X
X
X/*                     ANDNODE_
X
X    Class ANDNODE_ is derived from class AONODE_. It must be used in a
X    AND-OR search when a set of sub-problems, i.e, a set of new nodes,
X    is generated that ALL have to be solved. In this case the user should
X    create an ANDNODE_, by new ANDNODE_(), and pass every node representing
X    a sub-problem to this ANDNODE_: ANDNODE_::addsucc(some_ornode)).
X    Alternatively, an ANDNODE_ may be created by calling the second
X    constructor: new ANDNODE_(no_of_nodes) and then the successor nodes
X    may be passed by calling ANDNODE_::setsucc(n, node_n).
X
X*/
X
Xclass ANDNODE_ : public AONODE_
X{
X    public:
X    ANDNODE_();
X    ANDNODE_(int no_nodes);
X    ~ANDNODE_();
X
X    void setsucc(int, AONODE_ *);    // set successor n in succlist to...
X    void addsucc(AONODE_ *);         // add a successor to succlist
X        int getn_nodes() const;
X    AONODE_ *getsucc(int) const;     // get successor n from succlist
X
X    void display() const;
X        int equal(const VOBJECT_ &) const;
X    private:
X    int n_nodes;                     // number of nodes in succlist
X    AONODE_ **succlist;         // this node's successors
X};
X
X
X
X/*                        ORNODE_
X
X    Class ORNODE_ is derived from class AONODE_, which in turn is derived
X    from class NODE_. It is used in the process of an AND-OR search and
X    should be used in conjunction with class AOSEARCH_. Nodes that are meant
X    to be generated in an AND-OR search should be derived from class ORNODE_.
X
X*/
X
X
Xclass ORNODE_ : public AONODE_
X{
X    public:
X    ORNODE_();
X
X    void setsucc(AONODE_ *);
X    AONODE_ *getsucc() const;
X    private:
X    AONODE_ *succ;            // this node's successor
X};
X
X#endif
X
END_OF_FILE
  if test 6434 -ne `wc -c <'include/nodes.h'`; then
    echo shar: \"'include/nodes.h'\" unpacked with wrong size!
  fi
  # end of 'include/nodes.h'
fi
if test -f 'src/bisear/bisearch.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'src/bisear/bisearch.cpp'\"
else
  echo shar: Extracting \"'src/bisear/bisearch.cpp'\" \(5681 characters\)
  sed "s/^X//" >'src/bisear/bisearch.cpp' <<'END_OF_FILE'
X#include <new.h>
X#include "bisearch.h"
X
X/*                      BISEARCH_
X
X    The constructor puts the start node on s_open, the goal node on
X    t_open and sets the number of operators to the specified value.
X
X*/
X
XBISEARCH_::BISEARCH_(NODE_ *start, NODE_ *goal, int num)
X{
X    s_open.addtohead(*start);   // add start node to the head of s_open
X    t_open.addtohead(*goal);    // add goal node to the head of t_open
X    num_op = num;
X}
X
X
X
X/*                      ~BISEARCH_
X
X    We don't make the destructor pure virtual because we can't be sure
X    a destructor will be defined in the derived class.
X
X*/
X
XBISEARCH_::~BISEARCH_()
X{
X}
X
X
X
X/*                      GENERATE
X
X    Start looking for a solution and print it if found.
X
X*/
X
X#ifdef MSC
X    extern int no_mem(size_t);
X#else
X    extern void no_mem();
X#endif
X
Xvoid BISEARCH_::generate()
X{
X    NODE_
X        *node,
X        *s_node,
X        *t_node;
X
X#ifdef MSC
X    _set_new_handler(no_mem);
X#else
X    set_new_handler(no_mem);
X#endif
X
X    if (!(node = bisolve()))
X    {
X        puts("No solution found");
X        return;
X    }
X
X/* solve() stores the node that connects x_open with y_closed, i.e., the node
X   that is on both of these lists, at the head of x_open and of y_closed. */
X
X    s_node = (NODE_ *) s_open.gethead();
X    t_node = (NODE_ *) t_open.gethead();
X
X/* now find out on which list the node is stored: s_open or t_open. */
X
X    if (node->equal(*s_node))
X    {
X/* first we print the first half of the path. Next we check if s_node
X   matches the tail node of t_closed, that is the goal node. If it does,
X   the search paths didn't connect and this means we already printed the
X   entire solution path. If it doesn't we still need to print the second
X   half of the solution path, starting with the parent of the first node
X   on y_closed. */
X
X        print_sol(s_node);
X
X        if (!s_node->equal(*t_closed.gettail()))
X            print_sol_2(((NODE_ *) t_closed.gethead())->getparent());
X              // as we searched backward we need a different printing routine
X    }
X    else   // apply the same procedure, but reversed
X    {
X        if (!t_node->equal(*s_closed.gettail()))
X            print_sol(((NODE_ *) s_closed.gethead())->getparent());
X
X        print_sol_2(t_node);
X    }
X}
X
X
X
X/*                      PRINT_SOL
X
X    Trace back the solution path through the parent *'s. Recursively
X    prints that part of the solution path that reaches from the node
X    that connects both search paths back to the start.
X
X*/
X
Xvoid BISEARCH_::print_sol(NODE_ *sol) const
X{
X    if (!sol)
X        return;
X    print_sol(sol->getparent());
X    sol->display();
X}
X
X
X
X/*                   PRINT_SOL_2
X
X    Prints that part of the solution path that reaches from the node
X    connecting both search paths to the goal node.
X
X*/
X
Xvoid BISEARCH_::print_sol_2(NODE_ *sol) const
X{
X    while (sol)
X    {
X        sol->display();
X        sol = sol->getparent();
X    }
X}
X
X
X
X/*                     BISOLVE
X
X   This routine determines if the search will be continued backward or
X   forward. If s-open contains fewer nodes than t-open the search will
X   proceed forward, otherwise backward. If both lists are empty the
X   process ends with failure.
X
X*/
X
XNODE_ *BISEARCH_::bisolve()
X{
X    NODE_
X        *node = NULL;
X
X    while (node == NULL)
X    {
X        if(s_open.gethead() == NULL || t_open.gethead() == NULL)
X            break;    // no more nodes left in either list
X
X        if (s_open.getcount() <= t_open.getcount())
X            node = solve(&s_open, &s_closed, &t_closed);  // search forward
X        else
X            node = solve(&t_open, &t_closed, &s_closed);  // search backward
X    }
X    return(node);
X}
X
X
X
X/*                      SOLVE
X
X    This routines implements the actual search engine. It takes the first
X    node from xOPEN, if xOPEN is empty the search process fails. If not,
X    the node is moved to xCLOSED. Next, the node's successors are generated
X    by calling NODE_::expand(). Then, every successor is made to point
X    back to its parent, so that the solution path may be traced back once
X    the solution is found. Next, the routine checks for every successor if
X    it is also on yClosed, i.e., if it is part of the other path of the
X    search process. If so, this means that the particular node connects
X    both paths and the search process halts. Each successor is passed to add()
X    for further processing, if add() returns 0 this means that the
X    successor already was on xOPEN and consequently it can be thrown away,
X    i.e. it gets deallocated.
X
X    Solve() return the node that connects both paths if found and NULL
X    otherwise.
X
X*/
X
XNODE_ *BISEARCH_::solve(SORTEDLIST_ *x_open, SORTEDLIST_ *x_closed, SORTEDLIST_ *y_closed)
X{
X    NODE_
X        *connect,
X        *father,
X        *child;
X
X    father = (NODE_ *) x_open->gethead();   // get first node from open
X    x_open->remove_head();
X    x_closed->addtohead(*father);           // move it to closed
X
X    child = father->expand(num_op);         // expand node
X    while (child)
X    {
X        child->setparent(father);           // sets up solution path
X
X        if ((connect = (NODE_ *) y_closed->lookup(*child)) != NULL)
X        {                                 // here the paths connect
X            x_open->addtohead(*child);      // we store both of the nodes
X            y_closed->remove_found();       // at the start of the lists
X            y_closed->addtohead(*connect);  // so we can easily find them back
X            return(child);                // return node connecting both paths
X        }
X
X        if (!add(x_open, x_closed, child))
X            delete(child);
X        child = child->getnext();
X    }
X    return(NULL);
X}
END_OF_FILE
  if test 5681 -ne `wc -c <'src/bisear/bisearch.cpp'`; then
    echo shar: \"'src/bisear/bisearch.cpp'\" unpacked with wrong size!
  fi
  # end of 'src/bisear/bisearch.cpp'
fi
if test -f 'src/unisear/gbest.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'src/unisear/gbest.cpp'\"
else
  echo shar: Extracting \"'src/unisear/gbest.cpp'\" \(3188 characters\)
  sed "s/^X//" >'src/unisear/gbest.cpp' <<'END_OF_FILE'
X#include "graph.h"
X
X/*            BEST_NODE_
X
X    The constructor passes the start node, goal node and the number of
X    operators to SEARCH_.
X
X*/
X
XBEST_::BEST_(BEST_NODE_ *start, BEST_NODE_ *goal, int op)
X    :SEARCH_(start, goal, op)
X// This way the G- and F-values of the start node won't be computed,
X// but this is not very problematic.
X{
X}
X
X
X
X/*                        ADD
X
X    This functions examines each node that it is offered and decides
X    wether or not it should be added to OPEN.
X    First, it fills in the node's G- and F-values by calling compute_g()
X    and compute_f(). Next, it tries to lookup this node in OPEN and/or
X    in CLOSED. If the node is already on OPEN, but it's F-value is worse
X    than the older node (this is determined by eval()) it can simply be
X    thrown away, if it's better, the older node will be thrown away
X    (by remove_found()) and the new node will be added to OPEN
X    (by insert()). The same goes if a node is found to be already on
X    CLOSED. A node that is neither on OPEN nor on CLOSED can simply be
X    added to OPEN (by insert(), which creates an ordered list).
X
X*/
X
Xint BEST_::add(NODE_ *succ)
X{
X    BEST_NODE_
X    *parent,
X        *old = NULL,
X        *bsucc = (BEST_NODE_ *) succ;
X
X    int
X        g;
X
X    parent = (BEST_NODE_ *) bsucc->getparent();
X
X    g = parent->get_g() + compute_g(*bsucc);
X       /* a node's g-value is composed of the overall cost so far, i.e, the
X          the cost of getting from the start node to the parent of this node
X          and the added cost of getting from the parent to this node. */
X    bsucc->set_g(g);
X    bsucc->set_f(g + compute_h(*bsucc));
X       /* a node's f-value consists of its g-value and the value returned by
X          the heurisctic function compute_h(). */
X
X    if ((old = (BEST_NODE_ *) open.lookup(*succ)) != NULL)
X    {                         // node already on open
X        if (bsucc->eval(*old) < 0)            // new node better
X        {
X            open.remove_found(DEALLOC);       // remove & destroy old node
X            open.insert(*bsucc);              // add this node to the graph
X            return(1);
X        }
X        return(0);
X    }
X    if ((old = (BEST_NODE_ *) closed.lookup(*succ)) != NULL)
X    {                       // node already on closed
X        if (bsucc->eval(*old) < 0)            // new node better
X        {
X            closed.remove_found(DEALLOC);     // remove  & destroy old node
X            open.insert(*bsucc);
X            return(1);
X        }
X        return(0);
X    }
X// node neither on open nor on closed
X    open.insert(*bsucc);
X    return(1);
X}
X/*
X   A disadvantage of this method is that if a node is found to be
X   already on CLOSED and if it's better than the old node it will again
X   be added to OPEN, meaning that it will re-examined: its successors
X   will be again be generated etc, which may result in a lot of work being
X   done twice. A better solution that circumvents this problem is described
X   by Rich, 80/81 (note that in the algorithm that Ritch describes nodes
X   also have a pointer to their successors beside a pointer to their parent,
X   meaning that the algorithm we use would have to undergo major changes to
X   support this solution).
X*/
END_OF_FILE
  if test 3188 -ne `wc -c <'src/unisear/gbest.cpp'`; then
    echo shar: \"'src/unisear/gbest.cpp'\" unpacked with wrong size!
  fi
  # end of 'src/unisear/gbest.cpp'
fi
if test -f 'src/unisear/search.cpp' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'src/unisear/search.cpp'\"
else
  echo shar: Extracting \"'src/unisear/search.cpp'\" \(3065 characters\)
  sed "s/^X//" >'src/unisear/search.cpp' <<'END_OF_FILE'
X#include <new.h>
X#include "search.h"
X
X/*                      SEARCH_
X
X    The constructor puts the start node on open, saves the goal node
X    and sets the number of operators to the specified value.
X
X*/
X
XSEARCH_::SEARCH_(NODE_ *start, NODE_ *goal, int op)
X{
X    open.addtohead(*start);    // put the start node on open
X    num_op = op;
X    goalnode = goal;
X}
X
X
X
X/*                      ~SEARCH_
X
X    The destructor only deallocates the memory occupied by the goalnode.
X
X*/
X
XSEARCH_::~SEARCH_()
X{
X    delete(goalnode);
X}
X
X
X
X/*                    PRINT_SOL
X
X    Prints the solution by tracing back through the parent *'s. So, we
X    recurse a little (well...)
X
X*/
X
Xvoid SEARCH_::print_sol(NODE_ *sol) const
X{
X    if (!sol)
X        return;
X    print_sol(sol->getparent());
X    sol->display();
X}
X
X
X
X/*                   GENERATE
X
X    Starts the search process by calling solve() and prints the
X    solution if found by calling print_sol().
X
X*/
X
X#ifdef MSC
X    extern int no_mem(size_t);
X#else
X    extern void no_mem();
X#endif
X
Xvoid SEARCH_::generate()
X{
X    NODE_
X        *sol;
X
X#ifdef MSC
X    _set_new_handler(no_mem);
X#else
X    set_new_handler(no_mem);
X#endif
X
X    if (!(sol = solve()))
X    {
X        puts("No solution found");
X        return;
X    }
X
X    print_sol(sol);
X}
X
X
X
X/*                      SOLVE
X
X    This routines implements the actual search engine. It takes the first
X    node from OPEN, if OPEN is empty the search process fails. If not, the
X    node is moved to CLOSED. Next, the node's successors are generated by
X    calling NODE_::expand(). Then, every successor is made to point
X    back to its parent, so that the solution path may be traced back once
X    the solution is found. Each successor is passed to add() for further
X    processing, if add() returns 0 this means that the the successor
X    already was on OPEN and consequently it can be thrown away, i.e. it gets
X    deallocated.
X
X    Solve() returns the goal node if found and NULL otherwise.
X*/
X
XNODE_ *SEARCH_::solve()
X{
X    NODE_
X        *father,
X        *child,
X        *goal = NULL;
X
X    while((father = (NODE_ *) open.gethead()) != NULL)
X    {                                          // get first node from open
X        open.remove_head();
X        closed.addtohead(*father);             // put it on closed
X
X        child = father->expand(num_op);        // expand the node
X        while (child)
X        {
X            child->setparent(father);          // so I can remember my daddie
X
X            if (goalnode->equal(*child))       // found a goal node
X                goal = (goal == NULL || goal->eval(*child)) < 0 ?
X                       goal : child;
X/* We don't stop immediately after finding the goal node, because we may be
X   looking for the best or cheapest path and a better/cheaper goal node may
X   still be ahead in the list */
X            if (!add(child))
X                delete(child);               // child aready in graph: kill it!
X            child = child->getnext();
X        }
X        if (goal)
X            return(goal);
X    }
X    return(NULL);
X}
X
END_OF_FILE
  if test 3065 -ne `wc -c <'src/unisear/search.cpp'`; then
    echo shar: \"'src/unisear/search.cpp'\" unpacked with wrong size!
  fi
  # end of 'src/unisear/search.cpp'
fi
echo shar: End of archive 4 \(of 5\).
cp /dev/null ark4isdone
MISSING=""
for I in 1 2 3 4 5 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 5 archives.
    rm -f ark[1-9]isdone
else
    echo You still must unpack the following archives:
    echo "        " ${MISSING}
fi
exit 0
exit 0 # Just in case...