home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
OS/2 Shareware BBS: 10 Tools
/
10-Tools.zip
/
tlx501.zip
/
SRC
/
BTSEARCH.CPP
< prev
next >
Wrap
C/C++ Source or Header
|
1996-07-08
|
27KB
|
786 lines
/****************************************************************************
$Id: btsearch.cpp 501.0 1995/03/07 12:26:10 RON Exp $
Copyright (c) 1991-95 Tarma Software Research. All rights reserved.
Project: Tarma Library for C++ V5.0
Author: Ron van der Wal
Implementation of class TLBTSearcher. Class TLBTSearcher implements a
non-recursive backtrack search algorithm with provisions for
backjumping.
$Log: btsearch.cpp $
Revision 501.0 1995/03/07 12:26:10 RON
Updated for TLX 5.01
Revision 1.10 1995/02/28 15:10:06 RON
Update for release 012
Added partial support for SunPro C++ compiler
Revision 1.9 1995/01/13 15:30:01 ron
Added extra ContinueSearch() check to replace termination by
number of solutions found
Revision 1.8 1995/01/12 13:38:01 ron
Adapted to previous Searcher/ProblemRep model
Revision 1.7 1995/01/06 15:55:56 ron
Adapted to new Searcher/Problem model
Revision 1.6 1995/01/05 15:21:38 ron
Formatting and naming changes
Revision 1.5 1994/11/16 15:37:00 ron
Adapted to group-style tracing
Added module info; rearranged #include directives
Revision 1.4 1994/10/11 19:02:04 ron
Replaced DeadEnd() + SolveProblem() by ProcessProblem()
Changed RestartAt...() slightly
Removed several Frame member functions
Revision 1.3 1994/10/10 16:46:23 ron
Added searcher description
Changed checking of actions to catch alternative actions sooner
Revision 1.2 1994/10/07 17:01:16 ron
Changed UnregisterSearcher() to DeregisterSearcher()
Changed direct references to problem representation to go through
searcher interface
Revision 1.1 1994/10/06 17:43:36 ron
Initial revision
****************************************************************************/
#include <tlx\501\_build.h>
TLX_MODULE_INFO("$Revision: 501.0 $");
#include <stdio.h>
#include <tlx\501\except.h>
#include <tlx\501\solve\csp.h>
#include <tlx\501\solve\searcher.h>
/*---------------------------------------------------------------------------
Template instantiations
---------------------------------------------------------------------------*/
#if defined(THINK_CPLUS)
#include "pointer.cpp"
#include "slstack.cpp"
#pragma template TLCountedPtr<TLProblemState>;
#pragma template TLSLStack<TLBTSearcher::Frame>;
#elif defined(__BORLANDC__) || defined(_MSC_VER) || defined(__SC__) || defined(__WATCOMC__)
#include <tlx\501\template\pointer.cpp>
#include <tlx\501\template\slstack.cpp>
#elif defined(__SUNPRO_CC)
#include <tlx\501\template\pointer.cpp>
#include <tlx\501\template\slstack.cpp>
#elif defined(__IBMCPP__)
#if __IBMCPP__ < 300
#pragma implementation("tlx\\template\\pointer.cpp")
#pragma implementation("tlx\\template\\slstack.cpp")
#else
#include <tlx\501\template\pointer.cpp>
#include <tlx\501\template\slstack.cpp>
#endif
#else
#error Unsupported compiler; contact Tarma Software Research
#endif
/****************************************************************************
Implementation of TLBTSearcher::Frame class
****************************************************************************/
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame::Frame()
/* Default constructor. Sets all data members to 0.
---------------------------------------------------------------------------*/
: mBranches(50, 50)
{
ResetProblem(); // Resets mCurProblem
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame::~Frame()
/* Destructor. Deletes associated branches (if any). The frame must have
been removed from the stack when the destructor is called.
---------------------------------------------------------------------------*/
{
// TODO: Clean up list of branches
}
/*-------------------------------------------------------------------------*/
TLProblemState *TLBTSearcher::Frame::CurrentProblem() const
/* Returns a pointer to the current subproblem amongst the branches in
the frame. It is an error to call this routine when the Next()
iterator has been exhausted.
---------------------------------------------------------------------------*/
{
TLX_ASSERT(mCurProblem >= mBranches.Mini());
TLX_ASSERT(mCurProblem <= mBranches.Maxi());
return mBranches.PeekAt(mCurProblem);
}
/*-------------------------------------------------------------------------*/
bool TLBTSearcher::Frame::NextProblem()
/* Advances the internal node iterator, returning true iff a valid search
node is available.
---------------------------------------------------------------------------*/
{
return --mCurProblem >= mBranches.Mini();
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::Frame::PrevProblem()
/* Moves the internal node iterator back to the previous node in the frame
(if any).
---------------------------------------------------------------------------*/
{
if (mCurProblem <= mBranches.Maxi()) mCurProblem++;
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::Frame::ResetProblem()
/* Resets the internal subproblem iterator. After a call to this routine,
a call to NextProblem() is necessary to point the iterator at the first
subproblem (if any) in the frame.
---------------------------------------------------------------------------*/
{
mCurProblem = mBranches.Maxi() + 1;
}
/****************************************************************************
Implementation of TLBTSearcher class
****************************************************************************/
/*-------------------------------------------------------------------------*/
TLBTSearcher::TLBTSearcher()
/* Default constructor. Initializes empty frame stack.
---------------------------------------------------------------------------*/
{
mNextAction = actStop;
mMark = 0;
mUndoAll = true;
mStack.BecomeOwner(); // Will discard frames on destruction
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::~TLBTSearcher()
/* Destructor. Cleans up whatever is left on the search frame stack.
---------------------------------------------------------------------------*/
{
// Performed automatically by mStack if it's the owner
TLX_ASSERT(mStack.IsOwner());
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::BackToLevel(int aLevel, bool aUndoAll)
/* Initiates a back-jump to the given search level. It is an error to
backjump if the search stack is empty.
---------------------------------------------------------------------------*/
{
BackToMark(FindLevel(aLevel), aUndoAll);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::BackToMark(tMark aMark, bool aUndoAll)
/* Jumps back to a previously obtained mark and continues searching from
there. This will only work if the search process is currently deeper
along the same search path than when the mark was first obtained. If
this is not the case, the entire search stack will unwind.
The optional 'aUndoAll' parameter indicates whether or not each level
between the current and the target must be individually undone. If this
parameter is true (the default), this is indeed the case. If the
parameter is false, only the last level before the target is undone;
all other undo buffers are ignored. This latter behavior is useful in
cases where each undo buffer contains a full snapshot of the
problem representation's state; in those cases, it is useless and
inefficient to undo more than the last level before the target.
The marker is simply a pointer to the current top of the stack.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aMark);
mMark = aMark;
mUndoAll = aUndoAll;
mNextAction = actBackjump;
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::BackToProblem(TLProblemState *aProblem, bool aUndoAll)
/* Initiates a back-jump to a given subproblem.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aProblem);
BackToMark(FindProblem(aProblem), aUndoAll);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::BackToVariable(TLVariable *aVar, bool aUndoAll)
/* Initiates a back-jump to a given variable, provided that the variable
has a link to the subproblem of which it is part.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aVar);
BackToMark(FindVariable(aVar), aUndoAll);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::BackTrack()
/* Indicates to the searcher that some dead-end has been reached, and that
a backtrack should be performed as the next action.
---------------------------------------------------------------------------*/
{
mNextAction = actBacktrack;
}
/*-------------------------------------------------------------------------*/
bool TLBTSearcher::ContinueProblem(TLProblemState *)
/* Called to check if the current node may be continued after it has been
entered by the searcher. In this implementation, the check will always
succeed.
---------------------------------------------------------------------------*/
{
return true;
}
/*-------------------------------------------------------------------------*/
bool TLBTSearcher::ContinueSearch()
/* Called to determine whether or not the search process at large must be
continued after finding a solution. The default version returns true
as long as not sufficient solutions are found.
---------------------------------------------------------------------------*/
{
return SolutionCount() < GetStats().mMaxSol;
}
/*-------------------------------------------------------------------------*/
const char *TLBTSearcher::Description() const
/* Returns a description of the searcher.
---------------------------------------------------------------------------*/
{
return "Nonrecursive backtrack searcher";
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame *TLBTSearcher::FindLevel(int aLevel)
/* Finds the frame corresponding to the given level. If the level is not
valid, 0 is returned.
---------------------------------------------------------------------------*/
{
// Find the frame that corresponds to the given level
TLX_ASSERT(GetLevel() == mStack.Count());
int level = GetLevel();
for (Frame *frame = mStack.PeekTop(); frame; frame = frame->GetParent(),
level--)
if (level == aLevel)
return frame;
// If we get here, the level wasn't found
TLX_TRACE_ERROR(TLX, ("Level %d not found (current=%d)", aLevel, level));
return 0;
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame *TLBTSearcher::FindProblem(TLProblemState *aProblem)
/* Finds the frame corresponding to a given subproblem. If the node is
not found, 0 is returned.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aProblem);
// Find the frame that holds the node
for (Frame *frame = mStack.PeekTop(); frame; frame = frame->GetParent())
if (frame->CurrentProblem() == aProblem)
return frame;
// If we get here, the problem wasn't found
TLX_TRACE_WARN(TLX, ("Subproblem not found"));
return 0;
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame *TLBTSearcher::FindVariable(TLVariable *aVar)
/* Finds the frame that corresponds to the given variable instantiation.
This will only work if the variable has a back link to its subproblem.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aVar);
if (!aVar->GetProblem())
{
TLX_TRACE_ERROR(TLX, ("Variable %s has no problem", aVar->GetName()));
return 0;
}
// Actual target is found by looking for the node
return FindProblem(aVar->GetProblem());
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::tMark TLBTSearcher::GetMark() const
/* Returns a marker for the current position on the search stack. The
marker can be used to jump back to the current state later on.
The marker is simply a pointer to the current top of the stack.
---------------------------------------------------------------------------*/
{
return mStack.IsEmpty() ? 0 : mStack.PeekTop();
}
#if defined(_MSC_VER) && _MSC_VER < 1011
// This version of MSVC generates erroneous code here
#pragma optimize("gia", off)
#endif
/*-------------------------------------------------------------------------*/
bool TLBTSearcher::NextSolution()
/* Searches for the next solution, returning true if it finds one. If a
solution is found, it is available through PeekSolution().
The search routine is implemented as a loop that attempts one
variable selection or value association per iteration, or backtracks
over previous assignments. The user can influence the search loop by
a selected number of functions:
- BackTrack() backtracks over the current selection and requests a new
- JumpToXXX() backjumps to a previous state
- Terminate() terminates the search process altogether
---------------------------------------------------------------------------*/
{
#if defined(_MSC_VER) && _MSC_VER < 1011
// This version of MSVC generates erroneous code here
#pragma message("This version of Microsoft Visual C++ generates faulty code")
#endif
while (mNextAction != actStop && !mStack.IsEmpty())
{
Frame *curframe = mStack.PeekTop();
switch (mNextAction)
{
case actExpand: // Try to advance the search process
{
TLX_TRACE(TLX, (50, "BTSearch: actExpand"));
// Default action after the branch is an assignment,
// but either the user or the search process itself may
// change that. We set the default action here to leave
// room for changes by routines that are called during
// the lines that follow.
mNextAction = actExplore;
// Create a new frame to hold the new branches. If we have
// a current frame, then expand its current subproblem,
// else create the initial branches.
Frame *newframe = new Frame;
TLX_ASSERT_PTR(newframe);
TLX_ASSERT_PTR(curframe);
TLX_ASSERT_PTR(curframe->CurrentProblem());
bool expansion = GenerateBranches(curframe->CurrentProblem(),
newframe->mBranches);
if (expansion)
{
// We have expanded: add the frame to the stack and
// continue the default action (actExplore) or whatever
// other action may be set in the meantime.
Push(newframe);
newframe->ResetProblem();
}
else
{
delete newframe;
newframe = 0;
// Cannot expand current node - assume solution found
CreateSolution(curframe->CurrentProblem());
TLX_TRACE(TLX, (40, "BTSearch: Solution %d found",
SolutionCount()));
// Next action is a backtrack to obtain the next solution
// (if we ever get called back again).
if (mNextAction == actExplore)
mNextAction = actBacktrack;
return true;
}
break;
}
case actExplore: // Explore branches of current frame
TLX_TRACE(TLX, (50, "BTSearch: actExplore"));
TLX_ASSERT_PTR(curframe);
mNextAction = actExpand;
if (curframe->NextProblem())
{
TLProblemState *curproblem = curframe->CurrentProblem();
TLX_ASSERT_PTR(curproblem);
EnterState(curproblem);
// Check if the problem's exploration may be continued.
// This may cause the next action to be changed from its
// default action (which is to branch). In any case,
// if the node cannot be continued, we make sure that
// the next action is *not* to branch.
if ((!Process(curproblem) ||
!ContinueProblem(curproblem)) &&
mNextAction == actExpand)
mNextAction = actBacktrack;
}
else
{
// No (more) branches in the frame -- discard the frame
// and return to one level up.
delete Pop();
if (mStack.IsEmpty())
mNextAction = actStop;
else if (mNextAction == actExpand)
mNextAction = actBacktrack;
}
break;
case actBacktrack: // Leave current subproblem
TLX_TRACE(TLX, (50, "BTSearch: actBacktrack"));
TLX_ASSERT_PTR(curframe);
TLX_ASSERT_PTR(curframe->CurrentProblem());
LeaveState(curframe->CurrentProblem());
mNextAction = actExplore;
break;
case actBackjump: // Backjump to a previous state
TLX_TRACE(TLX, (50, "BTSearch: actBackjump"));
if (UnwindToMark() != 0)
mNextAction = actExplore;
else
{
TLX_TRACE_ERROR(TLX, ("Bad backjump, search stopped"));
mNextAction = actStop;
}
break;
case actRestart: // Restart from a previous state
TLX_TRACE(TLX, (50, "BTSearch: actRestart"));
if ((curframe = UnwindToMark()) != 0)
{
// Go back one position, because exploration will start
// by advancing the node iterator.
curframe->PrevProblem();
mNextAction = actExplore;
}
else
{
TLX_TRACE_ERROR(TLX, ("Bad restart, search stopped"));
mNextAction = actStop;
}
break;
default:
TLX_ASSERT_UNREACHABLE;
break;
}
}
// If we get here, there were no more solutions
return false;
}
#if defined(_MSC_VER) && _MSC_VER < 1011
#pragma optimize( "", on)
#endif
/*-------------------------------------------------------------------------*/
TLSolution *TLBTSearcher::PeekSolution() const
/* Returns a pointer to the current (i.e. last obtained) solution. It is
an error to call this function if there are no solutions.
---------------------------------------------------------------------------*/
{
return GetSolutions().PeekLast();
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame *TLBTSearcher::Pop()
/* Removes the top level search frame from the search stack and returns
a pointer to it.
---------------------------------------------------------------------------*/
{
TLX_ASSERT(!mStack.IsEmpty());
return mStack.Pop();
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::PostProcess()
/* Called to clean up after the search is completed. It discards the
search stack, then calls the inherited postprocessing function.
---------------------------------------------------------------------------*/
{
TLSearcher::PostProcess();
}
/*-------------------------------------------------------------------------*/
bool TLBTSearcher::PreProcess()
/* Called to prepare for the search. It calls the inherited version, then
cleans up the search stack that might be left over from previous
searches (if any) and initializes the search state.
---------------------------------------------------------------------------*/
{
if (!TLSearcher::PreProcess())
return false;
mNextAction = actExplore; // Start with exploration of root
mUndoAll = true;
mMark = 0;
mStack.RemoveAll();
return true;
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::Push(Frame *aFrame)
/* Pushes a new frame on top of the search stack.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aFrame);
mStack.Push(aFrame);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::RestartAtLevel(int aLevel, bool aUndoAll)
/* Initiates a restart from the given search level. It is an error to
restart if the search stack is empty.
---------------------------------------------------------------------------*/
{
RestartAtMark(FindLevel(aLevel), aUndoAll);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::RestartAtMark(tMark aMark, bool aUndoAll)
/* Jumps back to a previously obtained mark, then restarts from scratch
at that point. This will only work if the search process is currently
deeper along the same search path than when the mark was first obtained.
If this is not the case, the entire search stack will unwind.
The optional 'aUndoAll' parameter indicates whether or not each level
between the current and the target must be individually undone. If this
parameter is true (the default), this is indeed the case. If the
parameter is false, only the last level before the target is undone;
all other undo buffers are ignored. This latter behavior is useful in
cases where each undo buffer contains a full snapshot of the
problem representation's state; in those cases, it is useless and inefficient to
undo more than the last level before the target.
The marker is simply a pointer to the current top of the stack.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aMark);
mMark = aMark;
mUndoAll = aUndoAll;
mNextAction = actRestart;
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::RestartAtProblem(TLProblemState *aProblem, bool aUndoAll)
/* Initiates a restart from a given node.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aProblem);
RestartAtMark(FindProblem(aProblem), aUndoAll);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::RestartAtVariable(TLVariable *aVar, bool aUndoAll)
/* Initiates a restart from a given variable, provided that the variable
has a link to the subproblem of which it is part.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aVar);
RestartAtMark(FindVariable(aVar), aUndoAll);
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::Search()
/* Searches up to a given maximum of solutions.
---------------------------------------------------------------------------*/
{
TLX_TRACE(TLX, (40, "BTSearch: Search starts"));
// Preprocessing must have been performed
TLX_ASSERT(mStack.IsEmpty());
TLX_ASSERT(mNextAction == actExplore);
// Create the initial set of problems
Frame *root = new Frame;
TLX_ASSERT_PTR(root);
if (CreateInitialProblem(root->mBranches) < 1)
{
TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
delete root;
return;
}
root->ResetProblem();
Push(root);
// Find the requested number of solutions
while (NextSolution() && ContinueSearch())
;
TLX_TRACE(TLX, (40, "BTSearch: Search stopped"));
}
/*-------------------------------------------------------------------------*/
bool TLBTSearcher::StartSearch(TLProblemRep *aRep)
/* Starts a new search process, returning true if it succeeds.
---------------------------------------------------------------------------*/
{
TLX_ASSERT_PTR(aRep);
RegisterProblemRep(aRep);
if (!PreProcess())
{
DeregisterProblemRep();
return false;
}
TLX_ASSERT(mStack.IsEmpty());
TLX_ASSERT(mNextAction == actExplore);
// Create the initial set of problems
Frame *root = new Frame;
TLX_ASSERT_PTR(root);
if (CreateInitialProblem(root->mBranches) < 1)
{
TLX_TRACE_WARN(TLX, ("No initial problems created - search aborted"));
delete root;
return false;
}
Push(root);
return true;
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::StopSearch()
/* Terminates the search process.
---------------------------------------------------------------------------*/
{
PostProcess();
DeregisterProblemRep();
}
/*-------------------------------------------------------------------------*/
void TLBTSearcher::Terminate()
/* Indicates to the searcher that the search process should be terminated
altogether.
---------------------------------------------------------------------------*/
{
mNextAction = actStop;
}
/*-------------------------------------------------------------------------*/
TLBTSearcher::Frame *TLBTSearcher::UnwindToMark()
/* Unwinds the current search stack until the current 'mMark' mark is
found. Intermediate nodes are left if the 'mUndoAll' flag is set; the
final node (i.e. the current node of the target frame) is always left.
Intermediate frames are discarded.
The function returns the target frame, or 0 if the stack was unwound
completely.
---------------------------------------------------------------------------*/
{
Frame *frame;
while ((frame = mStack.PeekTop()) != 0)
{
TLX_ASSERT_PTR(frame->CurrentProblem());
LeaveState(frame->CurrentProblem(), mUndoAll || mMark == frame);
// If we found the frame, we're done
if (mMark == frame)
return frame;
// Still not at the desired frame - discard current level
delete Pop();
}
// If we get here, the stack was unwound without finding the frame
TLX_TRACE_WARN(TLX, ("Stack unwinding completely unwound stack"));
return 0;
}