home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / tlx501.zip / SRC / VARSELCT.CPP < prev    next >
C/C++ Source or Header  |  1996-07-08  |  9KB  |  314 lines
  1. /****************************************************************************
  2.     $Id: varselct.cpp 501.0 1995/03/07 12:26:26 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 several TLVarSelector classes.
  10.  
  11.     $Log: varselct.cpp $
  12.     Revision 501.0  1995/03/07 12:26:26  RON
  13.     Updated for TLX 5.01
  14.     Revision 1.4  1995/02/22 12:23:10  RON
  15.     Update for release 012
  16.     Added partial support for SunPro C++ compiler
  17. //Revision 1.3  1995/01/16  12:26:44  ron
  18. //Added subproblem parameter to varselectors
  19. //
  20. //Revision 1.2  1995/01/12  13:42:20  ron
  21. //Adapted to previous Searcher/ProblemRep model
  22. //
  23. //Revision 1.1  1995/01/06  15:58:43  ron
  24. //Corrected Revision keyword
  25. //
  26. ****************************************************************************/
  27.  
  28. #include <tlx\501\_build.h>
  29.  
  30. TLX_MODULE_INFO("$Revision: 501.0 $");
  31.  
  32. #include <stdlib.h>
  33.  
  34. #include <tlx\501\solve\stdcsp.h>
  35.  
  36. #if defined(__IBMCPP__) || defined(_MSC_VER) || defined(__WATCOMC__)
  37.     // IBM, Microsoft, Watcom C++ have no random(int) function
  38.  
  39.     inline int random(int __num)
  40.         { return(int)(((long)rand()*__num)/(RAND_MAX+1)); }
  41. #endif
  42.  
  43. /*-------------------------------------------------------------------------*/
  44.     TLVarSelector::~TLVarSelector()
  45.  
  46. /*  Destructor. Does nothing, but is declared virtual for derivation.
  47. ---------------------------------------------------------------------------*/
  48. {
  49. }
  50.  
  51. /*-------------------------------------------------------------------------*/
  52.     TLVSRandom::TLVSRandom()
  53.  
  54. /*  Constructor. Provided for completeness only.
  55. ---------------------------------------------------------------------------*/
  56. {
  57. }
  58.  
  59. /*-------------------------------------------------------------------------*/
  60.     const char *TLVSRandom::Description() const
  61.  
  62. /*  Returns a description of the selection strategy.
  63. ---------------------------------------------------------------------------*/
  64. {
  65.     return "Random order";
  66. }
  67.  
  68. /*-------------------------------------------------------------------------*/
  69.     TLVariable *TLVSRandom::SelectVariable(
  70.     TLCSProblemState *,
  71.         TLCSProblemRep *,
  72.     const TLVarList &aList)
  73.  
  74. /*  Selects a variable by picking one pseudo-randomly from the given list.
  75. ---------------------------------------------------------------------------*/
  76. {
  77.     TLX_ASSERT(!aList.IsEmpty());
  78.  
  79.     index_t rindex = random(aList.Count());
  80.     return aList[rindex + 1];
  81. }
  82.  
  83. /*-------------------------------------------------------------------------*/
  84.     TLVSSmallestDomain::TLVSSmallestDomain()
  85.  
  86. /*  Constructor. Provided for completeness only.
  87. ---------------------------------------------------------------------------*/
  88. {
  89. }
  90.  
  91. /*-------------------------------------------------------------------------*/
  92.     const char *TLVSSmallestDomain::Description() const
  93.  
  94. /*  Returns a description of the selection strategy.
  95. ---------------------------------------------------------------------------*/
  96. {
  97.     return "Smallest domain first";
  98. }
  99.  
  100. /*-------------------------------------------------------------------------*/
  101.     TLVariable *TLVSSmallestDomain::SelectVariable(
  102.     TLCSProblemState *,
  103.         TLCSProblemRep *,
  104.     const TLVarList &aList)
  105.  
  106. /*  Selects a variable by picking the (first) one with the smallest domain.
  107. ---------------------------------------------------------------------------*/
  108. {
  109.     TLX_ASSERT(!aList.IsEmpty());
  110.  
  111.     TLVariable *v = aList.PeekFirst();
  112.     size_t dsize   = v->DomainSize();
  113.  
  114.     for (index_t i = aList.Mini() + 1; i <= aList.Maxi(); i++)
  115.     {
  116.     TLVariable *var = aList.PeekAt(i);
  117.     TLX_ASSERT_PTR(var);
  118.  
  119.     if (var->DomainSize() < dsize)
  120.     {
  121.         v       = var;
  122.         dsize = v->DomainSize();
  123.     }
  124.     }
  125.     return v;
  126. }
  127.  
  128. /*-------------------------------------------------------------------------*/
  129.     TLVSLargestDomain::TLVSLargestDomain()
  130.  
  131. /*  Constructor. Provided for completeness only.
  132. ---------------------------------------------------------------------------*/
  133. {
  134. }
  135.  
  136. /*-------------------------------------------------------------------------*/
  137.     const char *TLVSLargestDomain::Description() const
  138.  
  139. /*  Returns a description of the selection strategy.
  140. ---------------------------------------------------------------------------*/
  141. {
  142.     return "Largest domain first";
  143. }
  144.  
  145. /*-------------------------------------------------------------------------*/
  146.     TLVariable *TLVSLargestDomain::SelectVariable(
  147.     TLCSProblemState *,
  148.         TLCSProblemRep *,
  149.     const TLVarList &aList)
  150.  
  151. /*  Selects a variable by picking the (first) one with the largest domain.
  152. ---------------------------------------------------------------------------*/
  153. {
  154.     TLX_ASSERT(!aList.IsEmpty());
  155.  
  156.     TLVariable *v = aList.PeekFirst();
  157.     size_t dsize   = v->DomainSize();
  158.  
  159.     for (index_t i = aList.Mini() + 1; i <= aList.Maxi(); i++)
  160.     {
  161.     TLVariable *var = aList.PeekAt(i);
  162.     TLX_ASSERT_PTR(var);
  163.  
  164.     if (var->DomainSize() > dsize)
  165.     {
  166.         v       = var;
  167.         dsize = v->DomainSize();
  168.     }
  169.     }
  170.     return v;
  171. }
  172.  
  173. /*-------------------------------------------------------------------------*/
  174.     TLVSMostConstrained::TLVSMostConstrained()
  175.  
  176. /*  Constructor. Provided for completeness only.
  177. ---------------------------------------------------------------------------*/
  178. {
  179. }
  180.  
  181. /*-------------------------------------------------------------------------*/
  182.     const char *TLVSMostConstrained::Description() const
  183.  
  184. /*  Returns a description of the selection strategy.
  185. ---------------------------------------------------------------------------*/
  186. {
  187.     return "Most constrained first";
  188. }
  189.  
  190. /*-------------------------------------------------------------------------*/
  191.     TLVariable *TLVSMostConstrained::SelectVariable(
  192.     TLCSProblemState *,
  193.         TLCSProblemRep *,
  194.     const TLVarList &aList)
  195.  
  196. /*  Selects a variable by picking the (first) one with the most constraints.
  197. ---------------------------------------------------------------------------*/
  198. {
  199.     TLX_ASSERT(!aList.IsEmpty());
  200.  
  201.     TLVariable *v = aList.PeekFirst();
  202.     size_t ccnt       = v->ConstraintCount();
  203.  
  204.     for (index_t i = aList.Mini() + 1; i <= aList.Maxi(); i++)
  205.     {
  206.     TLVariable *var = aList.PeekAt(i);
  207.     TLX_ASSERT_PTR(var);
  208.  
  209.     if (var->ConstraintCount() > ccnt)
  210.     {
  211.         v      = var;
  212.         ccnt = v->ConstraintCount();
  213.     }
  214.     }
  215.     return v;
  216. }
  217.  
  218. /*-------------------------------------------------------------------------*/
  219.     TLVSLeastConstrained::TLVSLeastConstrained()
  220.  
  221. /*  Constructor. Provided for completeness only.
  222. ---------------------------------------------------------------------------*/
  223. {
  224. }
  225.  
  226. /*-------------------------------------------------------------------------*/
  227.     const char *TLVSLeastConstrained::Description() const
  228.  
  229. /*  Returns a description of the selection strategy.
  230. ---------------------------------------------------------------------------*/
  231. {
  232.     return "Least constrained first";
  233. }
  234.  
  235. /*-------------------------------------------------------------------------*/
  236.     TLVariable *TLVSLeastConstrained::SelectVariable(
  237.     TLCSProblemState *,
  238.         TLCSProblemRep *,
  239.     const TLVarList &aList)
  240.  
  241. /*  Selects a variable by picking the (first) one with the least constraints.
  242. ---------------------------------------------------------------------------*/
  243. {
  244.     TLX_ASSERT(!aList.IsEmpty());
  245.  
  246.     TLVariable *v = aList.PeekFirst();
  247.     size_t ccnt       = v->ConstraintCount();
  248.  
  249.     for (index_t i = aList.Mini() + 1; i <= aList.Maxi(); i++)
  250.     {
  251.     TLVariable *var = aList.PeekAt(i);
  252.     TLX_ASSERT_PTR(var);
  253.  
  254.     if (var->ConstraintCount() < ccnt)
  255.     {
  256.         v      = var;
  257.         ccnt = v->ConstraintCount();
  258.     }
  259.     }
  260.     return v;
  261. }
  262.  
  263. /*-------------------------------------------------------------------------*/
  264.     TLVSDomConMix::TLVSDomConMix()
  265.  
  266. /*  Constructor. Provided for completeness only.
  267. ---------------------------------------------------------------------------*/
  268. {
  269. }
  270.  
  271. /*-------------------------------------------------------------------------*/
  272.     const char *TLVSDomConMix::Description() const
  273.  
  274. /*  Returns a description of the selection strategy.
  275. ---------------------------------------------------------------------------*/
  276. {
  277.     return "|C| / (|D|^2)";
  278. }
  279.  
  280. /*-------------------------------------------------------------------------*/
  281.     TLVariable *TLVSDomConMix::SelectVariable(
  282.     TLCSProblemState *,
  283.         TLCSProblemRep *,
  284.     const TLVarList &aList)
  285.  
  286. /*  Selects a variable by picking the (first) one with the most constraints.
  287. ---------------------------------------------------------------------------*/
  288. {
  289.     TLX_ASSERT(!aList.IsEmpty());
  290.  
  291.     TLVariable *v   = aList.PeekFirst();
  292.     size_t dsize     = v->DomainSize();
  293.     size_t maxweight = (dsize > 0) ? v->ConstraintCount() /
  294.                   (dsize * dsize) : kMaxSize;
  295.  
  296.     for (index_t i = aList.Mini() + 1; i <= aList.Maxi(); i++)
  297.     {
  298.     TLVariable *var = aList.PeekAt(i);
  299.     TLX_ASSERT_PTR(var);
  300.  
  301.     dsize     = var->DomainSize();
  302.     size_t w = (dsize > 0) ? v->ConstraintCount() /
  303.               (dsize * dsize) : kMaxSize;
  304.  
  305.     if (w > maxweight)
  306.     {
  307.         v           = var;
  308.         maxweight = w;
  309.     }
  310.     }
  311.     return v;
  312. }
  313.  
  314.