home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 27 / IOPROG_27.ISO / SOFT / GRAPH.ZIP / AI / SRC / UNISEAR / SEARCH.CPP < prev    next >
Encoding:
C/C++ Source or Header  |  1995-05-22  |  2.8 KB  |  128 lines
  1. #include <new.h>
  2. #include "search.h"
  3.  
  4. /*                      SEARCH_
  5.  
  6.     The constructor puts the start node on open, saves the goal node
  7.     and sets the number of operators to the specified value.
  8.  
  9. */
  10.  
  11. SEARCH_::SEARCH_(NODE_ *start, NODE_ *goal, int op)
  12. {
  13.     open.addtohead(*start);    // put the start node on open
  14.     num_op = op;
  15.     goalnode = goal;
  16. }
  17.  
  18.  
  19.  
  20. /*                      ~SEARCH_
  21.  
  22.     The destructor only deallocates the memory occupied by the goalnode.
  23.  
  24. */
  25.  
  26. SEARCH_::~SEARCH_()
  27. {
  28.     delete(goalnode);
  29. }
  30.  
  31.  
  32.  
  33. /*                    PRINT_SOL
  34.  
  35.     Prints the solution by tracing back through the parent *'s. So, we
  36.     recurse a little (well...)
  37.  
  38. */
  39.  
  40. void SEARCH_::print_sol(NODE_ *sol) const
  41. {
  42.     if (!sol)
  43.         return;
  44.     print_sol(sol->getparent());
  45.     sol->display();
  46. }
  47.  
  48.  
  49.  
  50. /*                   GENERATE
  51.  
  52.     Starts the search process by calling solve() and prints the
  53.     solution if found by calling print_sol().
  54.  
  55. */
  56.  
  57. #ifdef MSC
  58.     extern int no_mem(size_t);
  59. #else
  60.     extern void no_mem();
  61. #endif
  62.  
  63. void SEARCH_::generate()
  64. {
  65.     NODE_
  66.         *sol;
  67.  
  68. #ifdef MSC
  69.     _set_new_handler(no_mem);
  70. #else
  71.     set_new_handler(no_mem);
  72. #endif
  73.  
  74.     if (!(sol = solve()))
  75.     {
  76.         puts("No solution found");
  77.         return;
  78.     }
  79.  
  80.     print_sol(sol);
  81. }
  82.  
  83.  
  84.  
  85. /*                      SOLVE
  86.  
  87.     This routines implements the actual search engine. It takes the first
  88.     node from OPEN, if OPEN is empty the search process fails. If not, the
  89.     node is moved to CLOSED. Next, the node's successors are generated by
  90.     calling NODE_::expand(). Then, every successor is made to point
  91.     back to its parent, so that the solution path may be traced back once
  92.     the solution is found. Each successor is passed to add() for further
  93.     processing, if add() returns 0 this means that the the successor
  94.     already was on OPEN and consequently it can be thrown away, i.e. it gets
  95.     deallocated.
  96.  
  97.     Solve() returns the goal node if found and NULL otherwise.
  98. */
  99.  
  100. NODE_ *SEARCH_::solve()
  101. {
  102.     NODE_
  103.         *father,
  104.         *child,
  105.     *next;
  106.  
  107.     while((father = (NODE_ *) open.gethead()) != NULL)
  108.     {                                          // get first node from open
  109.         open.remove_head();
  110.         closed.addtohead(*father);             // put it on closed
  111.  
  112.     if (goalnode->equal(*father))          // found a goal node
  113.         return(father);
  114.  
  115.         child = father->expand(num_op);        // expand the node 
  116.         while (child)
  117.         {
  118.             child->setparent(father);          // so I can remember my daddie
  119.             next = child->getnext();
  120.             if (!add(child))
  121.                 delete(child);               // child aready in graph: kill it!
  122.             child = next;        
  123.         }
  124.     }
  125.     return(NULL);
  126. }
  127.  
  128.