home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / SRC / AOSEAR / AOSEARCH.CPP next >
Encoding:
C/C++ Source or Header  |  1994-08-12  |  9.4 KB  |  320 lines
  1. #include <new.h>
  2. #include "aosearch.h"
  3.  
  4. /*                      AOSEARCH_
  5.  
  6.     The constructor puts the start node on open and sets the number
  7.     of operators to the specified value.
  8.  
  9. */
  10.  
  11. AOSEARCH_::AOSEARCH_(AONODE_ *start, int num)
  12. {
  13.     open.addtohead(*start);       // put start node on open
  14.     startnode = start;            // needed to print solution afterwards
  15.     num_op = num;
  16. }
  17.  
  18.  
  19.  
  20. /*                      ~AOSEARCH_
  21.  
  22.     We don't make the destructor pure virtual because we can't be sure
  23.     a destructor will be defined in the derived class.
  24.  
  25. */
  26.  
  27. AOSEARCH_::~AOSEARCH_()
  28. {
  29. }
  30.  
  31.  
  32.  
  33. /*                      GENERATE
  34.  
  35.     Calls solve() and if it returns success prints the solution by
  36.     calling print_sol().
  37.  
  38. */
  39.  
  40. #ifdef MSC
  41.     extern int no_mem(size_t);
  42. #else
  43.     extern void no_mem();
  44. #endif
  45.  
  46. void AOSEARCH_::generate()
  47. {
  48. #ifdef MSC
  49.     _set_new_handler(no_mem);
  50. #else
  51.     set_new_handler(no_mem);
  52. #endif
  53.  
  54.     if (!solve())
  55.     {
  56.         puts("No solution found");
  57.         return;
  58.     }
  59.  
  60.     print_sol(startnode);
  61. }
  62.  
  63.  
  64.  
  65. /*               PRINT_SOL
  66.  
  67.     Traverses the solution path from the start and prints every node
  68.     it finds on its way. When it finds a node of type AND if calls
  69.     itself recursively, passing every successor node in turn.
  70.  
  71. */
  72.  
  73. void AOSEARCH_::print_sol(AONODE_ *node)
  74. {
  75.     AONODE_
  76.         *cur = node;
  77.  
  78.     int
  79.         i,
  80.         num;
  81.  
  82.     while (1)
  83.     {
  84.         if (cur->gettype() == AND)
  85.         {
  86.             num = ((ANDNODE_ *) cur)->getn_nodes();
  87.             for (i = 0; i < num; i++)
  88.                 print_sol(((ANDNODE_ *) cur)->getsucc(i));    // recurse
  89.             break;
  90.         }
  91.         else
  92.         {
  93.             cur->display();     // we suppose everything should be printed
  94.                                 // not just terminal nodes
  95.             if (!(cur = ((ORNODE_ *) cur)->getsucc()))  // end of branch
  96.                 break;
  97.         }
  98.     }
  99. }
  100.  
  101.  
  102.  
  103. /*                     SOLVABLE
  104.  
  105.     This routine applies a solve labeling procedure to the search tree.
  106.     First, the terminal node that it gets passed is labelled solved. Next,
  107.     the search tree is traversed upwards through all of the node's ancestors
  108.     to see if they can be labelled solved. An AND node may be labelled
  109.     solved iff all of its successors are labelled solved, i.e., n_left
  110.     is 0. An OR node may be labelled solved iff any of its successors is
  111.     labelled solved. Also, when an OR node is labelled solved we make it
  112.     point to its successor that was just labelled solved (an AND node
  113.     already points to all of its successors), so we can find back the
  114.     solution path afterwards.
  115.  
  116.     Solvable() returns 1 if the start node is labelled solved (meaning that
  117.     the search process ends with success), and 0 if not.
  118.  
  119. */
  120.  
  121. int AOSEARCH_::solvable(AONODE_ *node)
  122. {
  123.     AONODE_
  124.         *parent;
  125.  
  126.     node->setsolved(SOLVED);
  127.  
  128.     for ( ; (parent = (AONODE_ *) node->getparent()) != NULL;
  129.              node = (AONODE_ *) node->getparent())
  130.     {
  131.         if (parent->gettype() == AND)   // parent is AND node
  132.         {
  133.             parent->decn_left();
  134.             if (parent->getn_left() != 0)  // more successors to be solved left
  135.                 return(0);
  136.             parent->setsolved(SOLVED);
  137.         }
  138.         else    // parent is OR node, so parent is now solved too
  139.         {
  140.             parent->setsolved(SOLVED);
  141.             ((ORNODE_ *)parent)->setsucc(node);
  142.                         // make parent point to its successor
  143.         }
  144.     }
  145.     return(!parent);
  146. }
  147.  
  148.  
  149.  
  150. /*                     UNSOLVABLE
  151.  
  152.     This routine applies an unsolvable labeling procedure to the search
  153.     tree. First, the terminal node that it gets passed is labelled
  154.     unsolvable. Next, the search tree is traversed upwards through all of
  155.     the node's ancestors to see if they can be labelled unsolvable. An AND
  156.     node may be labelled unsolvable iff one of its successors is labelled
  157.     unsolvable. An OR node may be labelled unsolvable iff all of its
  158.     successors are labelled unsolvable.
  159.  
  160.     Unsolvable() returns 1 if the start node is labelled unsolvable (meaning
  161.     that the search process ends with failure), and 0 if not.
  162.  
  163. */
  164.  
  165. int AOSEARCH_::unsolvable(AONODE_ *node)
  166. {
  167.     AONODE_
  168.         *parent;
  169.  
  170.     node->setsolved(UNSOLVABLE);
  171.  
  172.     for (parent = (AONODE_ *) node->getparent(); parent;
  173.             parent = (AONODE_ *) parent->getparent())
  174.     {
  175.         if (parent->gettype() == AND)     // parent is AND node
  176.             parent->setsolved(UNSOLVABLE);   // so it is unsolvable too
  177.         else            // OR node
  178.         {
  179.             parent->decn_left();
  180.             if (parent->getn_left() == 0)      // no more successors left?
  181.                 parent->setsolved(UNSOLVABLE);
  182.             else
  183.                 return(0);
  184.         }
  185.     }
  186.     return(!parent);
  187. }
  188.  
  189.  
  190.  
  191. /*                      DELETABLE
  192.  
  193.     This routine determines if a node can be pruned. A node may be
  194.     pruned when itself or one of its ancestors is labelled solved
  195.     or unsolved (depending on what kind of nodes need to be pruned)
  196.     so we traverse the tree upwards through the parent *'s.
  197.  
  198. */
  199.  
  200. int AOSEARCH_::deletable(AONODE_ *node, int s)
  201. {
  202.     AONODE_
  203.         *parent;
  204.  
  205.     for (parent = node; parent; parent = (AONODE_ *) parent->getparent())
  206.         if (parent->getsolved() == s)
  207.             return(1);
  208.     return(0);
  209. }
  210.  
  211.  
  212.  
  213. /*                   PRUNE
  214.  
  215.     This routine prunes nodes from open. This is done using a list
  216.     iterator and calling deletable() for each node.
  217.  
  218. */
  219.  
  220. void AOSEARCH_::prune(int s)
  221. {
  222.     AONODE_
  223.         *node;
  224.     LIST_ITERATOR_
  225.         iter(open);
  226.  
  227.     node = (AONODE_ *)iter.getfirst();
  228.  
  229.     while (node)
  230.     {
  231.         if (deletable(node, s))         // may node be pruned?
  232.         {
  233.             iter.remove(DEALLOC);       // remove & destroy node
  234.             node = (AONODE_ *)iter.getitem();
  235.         }
  236.         else
  237.             node = (AONODE_ *)iter.getnext();
  238.     }
  239. }
  240.  
  241.  
  242.  
  243. /*                       SOLVE
  244.  
  245.     This routines implements the actual search engine. It takes the first
  246.     node from OPEN, if OPEN is empty the search process fails. If not, the
  247.     node is moved to CLOSED. Next, it checks if the node is a terminal node.
  248.     If so, it starts the solved labelling procedure, if this procedure returns
  249.     1 (meaning that the start node is labelled solved) the search process ends
  250.     with success, if not, prune() is called to prune all nodes on open that
  251.     are labelled solved or that have a solved ancestor.
  252.  
  253.     Next, the node's successors are generated by calling NODE_::expand(). If
  254.     expand() returns NULL this means that the node has no successors and,
  255.     therefore, is unsolvable; then, the unsolvable labelling is called, if it
  256.     returns success (meaning that the start node is labelled unsolvable) the
  257.     search process ends with failure, if not, prune() will be called to prune
  258.     from open all nodes that are labelled unsolvable or that have an
  259.     unsolvable ancestor.
  260.  
  261.     Next, every successor is made to point back to its parent, so that the
  262.     solution path may be traced once the solution is found and to enable
  263.     the solved and unsolvable labelling routines to get to the ancestors of
  264.     a node. Also the value of n_left of the parent node is incremented,
  265.     denoting the number of paths leading downward from it, i.e., denoting the
  266.     number of possibilities left by which the parent can be solved. Each
  267.     successor is passed to add() for further processing.
  268.  
  269.     Solve() returns 1 if the start node is labelled solved and 0 if it's
  270.     labelled unsolvable or if there are no more nodes left on open.
  271.  
  272. */
  273.  
  274. int AOSEARCH_::solve()
  275. {
  276.     AONODE_
  277.         *father,
  278.         *child;
  279.  
  280.     while((father = (AONODE_ *) open.gethead()) != NULL)
  281.     {                                    // get first node from open
  282.         open.remove_head();
  283.         closed.addtohead(*father);       // move it to closed
  284.  
  285.         if (is_terminal(*father))        // terminal node
  286.         {
  287.             if (solvable(father))        // apply solved-labeling procedure
  288.                 return(1);               // start node is solved: success
  289.             prune(SOLVED);               // prune solved nodes from open
  290.             continue;
  291.         }
  292.  
  293.         child = (AONODE_ *) father->expand(num_op);     // expand node
  294.  
  295.         if (child == NULL)             // no successors
  296.         {
  297.             if (unsolvable(father))    // apply unsolvable-labelling procedure
  298.                 return(0);             // start node unsolvable: fail
  299.             prune(UNSOLVABLE);         // prune unsolvable nodes from open
  300.             continue;
  301.         }
  302.  
  303.         while (child)
  304.         {
  305.             child->setparent(father);   // so I can remember my daddie
  306.             father->incn_left();        // increase branches pointing downward
  307.  
  308.             if (child->gettype() == AND)   // since an AND node serves no
  309.                 closed.addtohead(*child);  // further purpose (it can't be
  310.                                            // expanded) it is moved to closed
  311. /* remember that our terminology for AND and OR nodes differs from
  312.    normal usage */
  313.             add(child);              // add node (or in case of an AND node:
  314.                                      // its successor nodes) to open
  315.             child = (AONODE_ *) child->getnext();
  316.         }
  317.     }
  318.     return(0);
  319. }
  320.