home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / BTSRCHRC.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  6KB  |  194 lines
  1. /****************************************************************************
  2.     $Id: btsrchrc.cpp 501.0 1995/03/07 12:26:10 RON Exp $
  3.  
  4.     Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
  5.  
  6.     Project:    Tarma Library for C++ V5.0
  7.     Author:    Ron van der Wal
  8.  
  9.     Implementation of class TLBTSearcherRcsv. This class implements a
  10.     domain-independent recursive backtrack search process.
  11.  
  12.     $Log: btsrchrc.cpp $
  13.     Revision 501.0  1995/03/07 12:26:10  RON
  14.     Updated for TLX 5.01
  15.     Revision 1.16  1995/02/28 15:10:34  RON
  16.     Update for release 012
  17.     Added partial support for SunPro C++ compiler
  18.     Revision 1.15  1995/01/12  13:38:12  ron
  19.     Adapted to previous Searcher/ProblemRep model
  20.     Added check on initial problems
  21.  
  22.     Revision 1.14  1995/01/06  15:55:59  ron
  23.     Adapted to new Searcher/Problem model
  24.  
  25.     Revision 1.13  1995/01/05  15:21:56  ron
  26.     Formatting and naming changes
  27.  
  28.     Revision 1.12  1994/11/16  15:37:20  ron
  29.     Added module info; rearranged #include directives
  30.  
  31.     Revision 1.11  1994/10/11  19:04:17  ron
  32.     Replaced DeadEnd() + SolveProblem() by ProcessProblem()
  33.  
  34.     Revision 1.10  1994/10/10  16:54:08  ron
  35.     Added searcher description
  36.     Added termination routine & checks
  37.  
  38.     Revision 1.9  1994/10/07  17:03:47  ron
  39.     Removed direct references to problem representation and search statistics
  40.  
  41.     Revision 1.8  1994/10/05  18:42:05  ron
  42.     Added support for Watcom C++
  43.  
  44.     Revision 1.7  1994/09/28  14:20:35  ron
  45.     Removed Macintosh-style #include references
  46.  
  47.     Revision 1.6  1994/09/27  20:22:48  ron
  48.     Changed path separator from / to \
  49.  
  50.     Revision 1.5  1994/09/26  15:45:54  ron
  51.     Changed include file references
  52.  
  53.     Revision 1.4  1994/09/13  10:14:28  ron
  54.     Adapted to changes in the TLProblemRep hierarchy
  55.     Changed direct calls to problem representation EnterProblem()/LeaveProblem() to
  56.     calls to the TLSearcher-based versions.
  57.  
  58.     Revision 1.3  1994/09/12  14:55:34  ron
  59.     Adapted Search() implementation to changes in TLSearcher interface
  60.  
  61.     Revision 1.2  1994/09/06  14:09:00  ron
  62.     Adapted to changes in search framework
  63.  
  64.     Revision 1.1  1994/08/16  18:13:09  ron
  65.     Initial revision
  66.  
  67. ****************************************************************************/
  68.  
  69. #include <tlx\501\_build.h>
  70.  
  71. TLX_MODULE_INFO("$Revision: 501.0 $");
  72.  
  73. #include <iostream.h>
  74. #include <stdio.h>
  75. #include <tlx\501\solve\searcher.h>
  76.  
  77. /*---------------------------------------------------------------------------
  78.     Template instantiations
  79. ---------------------------------------------------------------------------*/
  80.  
  81. #if defined(THINK_CPLUS)
  82.     #include "pointer.cpp"
  83.     #pragma template TLCountedPtr<TLProblemState>;
  84. #elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__SC__) || defined(__WATCOMC__)
  85.     #include <tlx\501\template\pointer.cpp>
  86. #elif defined(__SUNPRO_CC)
  87.     #include <tlx\501\template\pointer.cpp>
  88. #elif defined(__IBMCPP__)
  89.   #if __IBMCPP__ < 300
  90.     #pragma implementation("tlx\\template\\pointer.cpp")
  91.   #else
  92.     #include <tlx\501\template\pointer.cpp>
  93.   #endif
  94. #else
  95.     #error Unsupported compiler; contact Tarma Software Research
  96. #endif
  97.  
  98. /*-------------------------------------------------------------------------*/
  99.     TLBTSearcherRcsv::TLBTSearcherRcsv()
  100.  
  101. /*  Default constructor.
  102. ---------------------------------------------------------------------------*/
  103. {
  104.     mTerminate = false;
  105. }
  106.  
  107. /*-------------------------------------------------------------------------*/
  108.     const char *TLBTSearcherRcsv::Description() const
  109.  
  110. /*  Returns a description of the searcher.
  111. ---------------------------------------------------------------------------*/
  112. {
  113.     return "Recursive backtrack searcher";
  114. }
  115.  
  116. /*-------------------------------------------------------------------------*/
  117.     void TLBTSearcherRcsv::Search()
  118.  
  119. /*  Perfoms the actual search process. The function assumes that all
  120.     parameters have been properly set up. It will find at most mMaxSol
  121.     solutions and return when the lesser of all or mMaxSol solutions has
  122.     been found.
  123. ---------------------------------------------------------------------------*/
  124. {
  125.     mTerminate = false;
  126.  
  127.     TLProblemList root(50, 50);
  128.     if (CreateInitialProblem(root) < 1)
  129.     {
  130.     TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
  131.     return;
  132.     }
  133.     StepForward(root);
  134. }
  135.  
  136. /*-------------------------------------------------------------------------*/
  137.     bool TLBTSearcherRcsv::StepForward(TLProblemList &aList)
  138.  
  139. /*  Performs a forward step in the search process. If the step succeeds,
  140.     it calls itself recursively to do the next step. If it fails, it
  141.     backtracks.
  142.  
  143.     If all variables have been instantiated when this function is called,
  144.     it reports the solution and either stops the search process if
  145.     sufficient solutions have been found, or continues with a backtrack to
  146.     find the next solution (if any).
  147.  
  148.     Returns nonzero if the search is successful and complete; zero if we
  149.     reach a dead end or want to backtrack to find subsequent solutions.
  150. ---------------------------------------------------------------------------*/
  151. {
  152.     while (!mTerminate && !aList.IsEmpty())
  153.     {
  154.     TLProblemState *curproblem = aList.ExtractFirst();
  155.     TLX_ASSERT_PTR(curproblem);
  156.     EnterState(curproblem);
  157.  
  158.     if (Process(curproblem))
  159.     {
  160.         TLProblemList branches(10, 10);
  161.  
  162.         if (!GenerateBranches(curproblem, branches))
  163.         {
  164.         // No further expansion possible --> we have a solution
  165.  
  166.         CreateSolution(curproblem);
  167.  
  168.         // If we return true, the search process stops; otherwise it
  169.         // moves on to search for the next solution. Therefore, we
  170.         // return true only if we have found all desired solutions.
  171.  
  172.             if (SolutionCount() >= GetStats().mMaxSol)
  173.             return true;
  174.         }
  175.         else if (!mTerminate && StepForward(branches))
  176.         return true;
  177.  
  178.         // TODO: check if there is a memory leak in TLProblemList branches
  179.     }
  180.     LeaveState(curproblem);
  181.     }
  182.     return false;
  183. }
  184.  
  185. /*-------------------------------------------------------------------------*/
  186.     void TLBTSearcherRcsv::Terminate()
  187.  
  188. /*  Sets the termination flag, which causes the searcher to terminate as
  189.     soon as possible.
  190. ---------------------------------------------------------------------------*/
  191. {
  192.     mTerminate = true;
  193. }
  194.