home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / SRC / UNISEAR / GUCOST.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1994-08-12  |  1.7 KB  |  62 lines
  1. #include "graph.h"
  2.  
  3. /*            UNICOST_GRAPH_
  4.  
  5.     The constructor passes the start node, goal node and number of
  6.     operators to SEACH_.
  7.  
  8. */
  9.  
  10. UNICOST_GRAPH_::UNICOST_GRAPH_(UNI_NODE_ *start, UNI_NODE_ *goal, int op)
  11.     :SEARCH_(start, goal, op)
  12. {
  13. }
  14.  
  15.  
  16.  
  17. /*                  ADD
  18.  
  19.     This routine works much the same as BEST_::add(), except for the
  20.     following. Since we don't use the heuristic estimate H nodes are
  21.     ordered based on their G-value. Secondly, when a node is found
  22.     to be already on CLOSED there's no need to check if the old node
  23.     or the current node is better, since we are guaranteed to always
  24.     find the cheapest node first (see Nilsson p.53).
  25.  
  26. */
  27.  
  28. int UNICOST_GRAPH_::add(NODE_ *succ)
  29. {
  30.     UNI_NODE_
  31.     *parent,
  32.         *old = NULL,
  33.         *bsucc = (UNI_NODE_ *) succ;
  34.  
  35.     int
  36.         g;
  37.  
  38.     parent = (UNI_NODE_ *) bsucc->getparent();
  39.     g = parent->get_g() + compute_g(*bsucc);
  40.        /* a node's g-value is composed of the overall cost so far, i.e, the
  41.           the cost of getting from the start node to the parent of this node
  42.           and the added cost of getting from the parent to this node. */
  43.     bsucc->set_g(g);
  44.  
  45.     if ((old = (UNI_NODE_ *) open.lookup(*succ)) != NULL)
  46.     {                    // node already on open
  47.         if (bsucc->eval(*old) < 0)             // new node better
  48.         {
  49.             open.remove_found(DEALLOC);        // remove & destroy old node
  50.             open.insert(*bsucc);
  51.             return(1);
  52.         }
  53.         return(0);
  54.     }
  55.     if ((old = (UNI_NODE_ *) closed.lookup(*succ)) != NULL)
  56.         return(0);   // no need for any further checks, see Nilsson 53!
  57.  
  58. // node neither on open nor on closed
  59.     open.insert(*bsucc);
  60.     return(1);
  61. }
  62.