Usenet 1994 October/usenetsourcesnewsgroupsinfomagicoctober1994disk2.iso/misc/volume42/aisearch/patch01

Internet Message Format | 1994-05-06 | 7.8 KB

From: [e-mail] (Peter Bouthoorn)
Newsgroups: comp.sources.misc
Subject: v42i068:  aisearch - C++ AI search class library, Patch01
Date: 6 May 1994 13:01:12 -0500
Organization: Sterling Software
Sender: [e-mail]
Approved: [e-mail]
Message-ID: <2qe0l8$[e-mail]>
X-Md4-Signature: f0c23121e3c6be5ec76bbebc3b5842d7

Submitted-by: [e-mail] (Peter Bouthoorn)
Posting-number: Volume 42, Issue 68
Archive-name: aisearch/patch01
Environment: C++ (UNIX, DOS)
Patch-To: aisearch: Volume 41, Issue 127-131

To install these patches cd to the directory where you unpacked
the AIsearch library and issue a

  patch -p0 < thisfile

command. Note that I changed a few lines in search.tex, but there are
no patches for the .dvi and .ps file (the changes aren't really essential,
but if you want the updated versions of these files just get the complete
package via anonymous ftp from obelix.icce.rug.nl:/pub/peter).

Cheers,
Peter

-----------------------------------------
--- src/bisear/bisearch.cpp    Fri Apr 15 18:32:16 1994
*** ../old/doc/search.tex    Fri May  6 12:51:58 1994
--- ./doc/search.tex    Fri May  6 12:50:50 1994
***************
*** 181,194 ****
  node, which has no parent). Searching a tree is easier than searching a graph,
  because when a new node is generated in the tree we can be sure it has not
  been generated before. This is true because every node has only one parent, so
! there cannot be two or more different paths leading to the same node. In a graph,
! however, nodes usually have more than one parent.  Therefore, when
! searching a graph one should make provisions to deal with these situations. For
! example, in the case of the 8-puzzle the same state may be generated by a
! different sequence of operators. That is, the same node may be part of several
! paths, e.g., when we apply operators 'move empty tile left, move empty tile down'
! we produce exactly the same node as in the sequence 'move empty tile down, move
! empty tile left'. Continuing the processing of both these nodes (which are
  really the same node) would be redundant and a waste of effort. This can be
  avoided at the price of additional bookkeeping. Instead of traversing a tree we
  traverse a {\em directed graph\,}\footnote{Knuth(1979), p.371.}: every time a
--- 181,192 ----
  node, which has no parent). Searching a tree is easier than searching a graph,
  because when a new node is generated in the tree we can be sure it has not
  been generated before. This is true because every node has only one parent, so
! there cannot be two or more different paths leading to the same node. In a
! graph, however, nodes usually have more than one parent.  Therefore, when
! searching a graph one should make provisions to deal with these situations.
! Saying that a node has more than one parent means that the node is generated
! by a different sequence of the same operators. That is, the same node may be
! part of several paths, and continuing the processing of both these nodes (which are
  really the same node) would be redundant and a waste of effort. This can be
  avoided at the price of additional bookkeeping. Instead of traversing a tree we
  traverse a {\em directed graph\,}\footnote{Knuth(1979), p.371.}: every time a
***************
*** 811,819 ****
  Intelligence}, Los Altos: Kaufmann.\\
  Nillson, N.J. (1971), {\em Problem Solving Methods in Artificial
  Intelligence\,}, New York: McGraw-Hill.\\
!               (1986), {\em Principles of Artifial Intelligence\,}, Los Altos:
  Kaufmann.\\
! Knuth, D.E. (1979), {\em The Art of Computer Programs\,} (2nd ed.). London:
  Addison-Wesley.\\
  Pearl, J. (1984), {\em Heuristics: Intelligent Strategies for Computer Problem
  Solving\,}, London: Addison-Wesley.\\
--- 809,817 ----
  Intelligence}, Los Altos: Kaufmann.\\
  Nillson, N.J. (1971), {\em Problem Solving Methods in Artificial
  Intelligence\,}, New York: McGraw-Hill.\\
! Nilsson, N.J. (1986), {\em Principles of Artifial Intelligence\,}, Los Altos:
  Kaufmann.\\
! Knuth, D.E. (1979), {\em The Art of Computer Programming\,} (2nd ed.). London:
  Addison-Wesley.\\
  Pearl, J. (1984), {\em Heuristics: Intelligent Strategies for Computer Problem
  Solving\,}, London: Addison-Wesley.\\
*** ../old/src/bisear/bisearch.cpp    Fri May  6 12:51:59 1994
--- ./src/bisear/bisearch.cpp    Fri May  6 12:50:49 1994
***************
*** 183,189 ****
  NODE_ *BISEARCH_::solve(SORTEDLIST_ *x_open, SORTEDLIST_ *x_closed, SORTEDLIST_ *y_closed)
  {
      NODE_
!         *connect,
          *father,
          *child;

--- 183,189 ----
  NODE_ *BISEARCH_::solve(SORTEDLIST_ *x_open, SORTEDLIST_ *x_closed, SORTEDLIST_ *y_closed)
  {
      NODE_
!         *aux,
          *father,
          *child;

***************
*** 196,212 ****
      {
          child->setparent(father);           // sets up solution path

!         if ((connect = (NODE_ *) y_closed->lookup(*child)) != NULL)
          {                                 // here the paths connect
              x_open->addtohead(*child);      // we store both of the nodes
              y_closed->remove_found();       // at the start of the lists
!             y_closed->addtohead(*connect);  // so we can easily find them back
              return(child);                // return node connecting both paths
          }

          if (!add(x_open, x_closed, child))
              delete(child);
!         child = child->getnext();
      }
      return(NULL);
  }
--- 196,213 ----
      {
          child->setparent(father);           // sets up solution path

!         if ((aux = (NODE_ *) y_closed->lookup(*child)) != NULL)
          {                                 // here the paths connect
              x_open->addtohead(*child);      // we store both of the nodes
              y_closed->remove_found();       // at the start of the lists
!             y_closed->addtohead(*aux);  // so we can easily find them back
              return(child);                // return node connecting both paths
          }

+     aux = child->getnext();
          if (!add(x_open, x_closed, child))
              delete(child);
!         child = aux;
      }
      return(NULL);
  }
*** ../old/src/list/list.cpp    Fri May  6 12:52:07 1994
--- ./src/list/list.cpp    Fri May  6 12:50:49 1994
***************
*** 27,39 ****

  VOBJECT_ *LIST_::gethead() const
  {
!     return(head->getdata());
  }


  VOBJECT_ *LIST_::gettail() const
  {
!     return(tail->getdata());
  }


--- 27,39 ----

  VOBJECT_ *LIST_::gethead() const
  {
!     return(head ? head->getdata() : NULL);
  }


  VOBJECT_ *LIST_::gettail() const
  {
!     return(tail ? tail->getdata() : NULL);
  }


*** ../old/src/unisear/search.cpp    Fri May  6 12:51:59 1994
--- ./src/unisear/search.cpp    Fri May  6 12:50:50 1994
***************
*** 102,107 ****
--- 102,108 ----
      NODE_
          *father,
          *child,
+     *next,
          *goal = NULL;

      while((father = (NODE_ *) open.gethead()) != NULL)
***************
*** 120,128 ****
  /* We don't stop immediately after finding the goal node, because we may be
     looking for the best or cheapest path and a better/cheaper goal node may
     still be ahead in the list */
              if (!add(child))
                  delete(child);               // child aready in graph: kill it!
!             child = child->getnext();
          }
          if (goal)
              return(goal);
--- 121,130 ----
  /* We don't stop immediately after finding the goal node, because we may be
     looking for the best or cheapest path and a better/cheaper goal node may
     still be ahead in the list */
+             next = child->getnext();
              if (!add(child))
                  delete(child);               // child aready in graph: kill it!
!             child = next;
          }
          if (goal)
              return(goal);
exit 0 # Just in case...