home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / SRC / UNISEAR / GBEST.CPP next >
Encoding:
C/C++ Source or Header  |  1994-08-12  |  3.2 KB  |  91 lines
  1. #include "graph.h"
  2.  
  3. /*            BEST_NODE_
  4.  
  5.     The constructor passes the start node, goal node and the number of
  6.     operators to SEARCH_.
  7.  
  8. */
  9.  
  10. BEST_::BEST_(BEST_NODE_ *start, BEST_NODE_ *goal, int op)
  11.     :SEARCH_(start, goal, op)
  12. // This way the G- and F-values of the start node won't be computed,
  13. // but this is not very problematic.
  14. {   
  15. }
  16.  
  17.  
  18.  
  19. /*                        ADD
  20.  
  21.     This functions examines each node that it is offered and decides
  22.     wether or not it should be added to OPEN.
  23.     First, it fills in the node's G- and F-values by calling compute_g()
  24.     and compute_f(). Next, it tries to lookup this node in OPEN and/or
  25.     in CLOSED. If the node is already on OPEN, but it's F-value is worse
  26.     than the older node (this is determined by eval()) it can simply be
  27.     thrown away, if it's better, the older node will be thrown away
  28.     (by remove_found()) and the new node will be added to OPEN
  29.     (by insert()). The same goes if a node is found to be already on
  30.     CLOSED. A node that is neither on OPEN nor on CLOSED can simply be
  31.     added to OPEN (by insert(), which creates an ordered list).
  32.  
  33. */
  34.  
  35. int BEST_::add(NODE_ *succ)
  36. {
  37.     BEST_NODE_
  38.     *parent,
  39.         *old = NULL,
  40.         *bsucc = (BEST_NODE_ *) succ;
  41.  
  42.     int
  43.         g;
  44.  
  45.     parent = (BEST_NODE_ *) bsucc->getparent();
  46.  
  47.     g = parent->get_g() + compute_g(*bsucc);
  48.        /* a node's g-value is composed of the overall cost so far, i.e, the
  49.           the cost of getting from the start node to the parent of this node
  50.           and the added cost of getting from the parent to this node. */
  51.     bsucc->set_g(g);
  52.     bsucc->set_f(g + compute_h(*bsucc));
  53.        /* a node's f-value consists of its g-value and the value returned by
  54.           the heurisctic function compute_h(). */
  55.  
  56.     if ((old = (BEST_NODE_ *) open.lookup(*succ)) != NULL)
  57.     {                         // node already on open
  58.         if (bsucc->eval(*old) < 0)            // new node better
  59.         {
  60.             open.remove_found(DEALLOC);       // remove & destroy old node
  61.             open.insert(*bsucc);              // add this node to the graph
  62.             return(1);
  63.         }
  64.         return(0);
  65.     }
  66.     if ((old = (BEST_NODE_ *) closed.lookup(*succ)) != NULL)
  67.     {                       // node already on closed
  68.         if (bsucc->eval(*old) < 0)            // new node better
  69.         {
  70.             closed.remove_found(DEALLOC);     // remove  & destroy old node
  71.             open.insert(*bsucc);
  72.             return(1);
  73.         }
  74.         return(0);
  75.     }
  76. // node neither on open nor on closed
  77.     open.insert(*bsucc);
  78.     return(1);
  79. }
  80. /*
  81.    A disadvantage of this method is that if a node is found to be
  82.    already on CLOSED and if it's better than the old node it will again
  83.    be added to OPEN, meaning that it will re-examined: its successors
  84.    will be again be generated etc, which may result in a lot of work being
  85.    done twice. A better solution that circumvents this problem is described
  86.    by Rich, 80/81 (note that in the algorithm that Ritch describes nodes
  87.    also have a pointer to their successors beside a pointer to their parent,
  88.    meaning that the algorithm we use would have to undergo major changes to
  89.    support this solution).
  90. */
  91.