Main Page | Class Hierarchy | Class List | File List | Class Members

ValueOH Class Reference

#include <ValueOH.h>

Inheritance diagram for ValueOH:

OrderingHeuristic Branching Conflicts Failures Lexical MinDomain Predefined Random SolutionProbability List of all members.

Public Member Functions

 ValueOH (const wstring &name, Decomposition &decomposition, const vector< pair< double, double > > &intervals, double quality=1, bool analysis=false)
virtual void init (const vlist_type &)
virtual void done ()
 Clean up the work done by `init()'.
void solutionFound (const Solution &solution)
virtual void dynamicInit (Variable &, Domain &)
virtual void dynamicDone (Variable &)
virtual void select (Domain &selectable, Domain &selected, Variable &variable)=0
virtual bool better (const Value &value0, const Value &value1)
virtual bool equal (const Value &value0, const Value &value1)
virtual void sort (Domain &original, Domain &sorted, Variable &variable)
virtual long double score (Variable &variable, const Value &value)=0
void setDistance (size_t distance)
bool analysisFlag () const
 Return `true' if the analysis flag is turned on.
virtual wostream & print (wostream &wos) const

Protected Member Functions

void selectByQuality (const Variable &variable, Domain &selectable, Domain &selected, StrictWeakValueOrdering &better, StrictWeakValueOrdering &equal)
void selectByDistance (const Variable &variable, Domain &selectable, Domain &selected, StrictWeakValueOrdering &better)
void sort (Domain &original, Domain &sorted, Variable &variable, StrictWeakValueOrdering &better, StrictWeakValueOrdering &equal)
int distance (vector< Value * > &preferred, hash_set< const Value * > &perfect) const
void printPerfectPositions (vector< Value * > &preferred, hash_set< const Value * > &perfect) const
wostringstream & printScores (wostringstream &wos, Variable &variable, vector< Value * > &preferred)
 Generate a string with the scores of all the values.

Protected Attributes

bool m_analysis
size_t m_distance
 The distance to be used in selectByDistance().

Friends

CSP_API wostream & operator<< (wostream &wos, const ValueOH &valueOH)

Detailed Description

The super class of all the value ordering heuristics.

Constructor & Destructor Documentation

ValueOH::ValueOH (  const wstring &  name,
Decomposition &  decomposition,
const vector< pair< double, double > > &  intervals,
double  quality = 1,
bool  analysis = false
) 
 

Constructor for various value ordering heuristics.

Parameters:
name the name of the heuristic.
decomposition the decomposition using this heuristic.
intervals the depth intervals where the heuristic is active; if no intervals are given, the heuristic is always active.
quality the heuristic's quality, in the [0-1] range.
analysis flag turning the heuristic analysis code on/off.

Member Function Documentation

bool ValueOH::better (  const Value &  value0,
const Value &  value1
)  [virtual]
 

Compare two values. FIXME: The default implementation of this function simply aborts. Normally, this function should be pure virtual, but not all value ordering heuristics implement the quality based selection mechanism yet.

Parameters:
value0 the first value.
value1 the second value.
Returns:
`true' if value0 is strictly better than value1, `false' otherwise.

Reimplemented in Branching, Conflicts, Failures, Lexical, MinDomain, Random, and SolutionProbability.

int ValueOH::distance (  vector< Value * > &  preferred,
hash_set< const Value * > &  perfect
)  const [protected]
 

Return the distance between the first preferred value and the first preferred one that is perfect.

Parameters:
preferred the set of preferred values.
perfect the set of perfect values.
Returns:
the distance between the first preferred value and the first preferred one that is perfect.

virtual void ValueOH::dynamicDone (  Variable &   )  [inline, virtual]
 

Any dynamic clean up of the data structures required by the value selection should be performed here.

Parameters:
variable the variable for which the selection is done.

Reimplemented in Branching, Conflicts, MinDomain, and Random.

virtual void ValueOH::dynamicInit (  Variable &  ,
Domain & 
)  [inline, virtual]
 

Any dynamic initializations required by the value selection should be performed here.

Parameters:
variable the variable for which the selection is done.
selectable the domain to select values from.

Reimplemented in Branching, Conflicts, MinDomain, and Random.

bool ValueOH::equal (  const Value &  value0,
const Value &  value1
)  [virtual]
 

Compare two values for equality. FIXME: The default implementation of this function simply aborts. Normally, this function should be pure virtual, but not all value ordering heuristics implement the quality based selection mechanism yet.

Parameters:
value0 the first value.
value1 the second value.
Returns:
`true' if value0 is as good as value1, `false' otherwise.

Reimplemented in Branching, Conflicts, Failures, Lexical, MinDomain, Random, and SolutionProbability.

virtual void ValueOH::init (  const vlist_type &   )  [inline, virtual]
 

If any static computations or initializations are needed, they should be done here. Doing the static computations in the constructor would limit the heuristic to working only on the complete `Problem'. Doing it here allows the heuristic to be reused.

Parameters:
uninstantiatedVariables the list of variables that have not yet been instantiated in the decomposition.

Reimplemented in Conflicts, Predefined, and Predefined.

wostream & ValueOH::print (  wostream &  wos  )  const [virtual]
 

Print information about the heuristic at the given stream.

Parameters:
wos the output stream to print to.

Reimplemented from OrderingHeuristic.

void ValueOH::printPerfectPositions (  vector< Value * > &  preferred,
hash_set< const Value * > &  perfect
)  const [protected]
 

Print the index of each perfect value in the domain.

Parameters:
preferred the values from which the selection is to be made, sorted according to the heuristic's preference.
perfect the set of values whose selection would lead to a solution.

virtual long double ValueOH::score (  Variable &  variable,
const Value &  value
)  [pure virtual]
 

Return the score of a value. The score is a number based on which the value's position is determined. The better the value, the greater the score should be.

Parameters:
variable the variable to which the value belongs.
value the value whose score is to be calculated.
Returns:
the value's score, as a floating point number.

Implemented in Branching, Conflicts, Failures, Lexical, MinDomain, Predefined, Random, and SolutionProbability.

virtual void ValueOH::select (  Domain &  selectable,
Domain &  selected,
Variable &  variable
)  [pure virtual]
 

Each value ordering heuristic object should implement this method which is supposed to get a domain of values and return another domain containing only the "preferred" values among those in the original domain. This method should NEVER return an empty list. The selected values are removed from the original domain. If the library's `g_predictable' flag is turned on, this function should expect the original domain to be sorted by ID and should preserve that upon return. The list of selected values should also be returned sorted if `g_predictable' is on. Note that when this function is called, the domain of `variable' is empty.

Parameters:
selectable the domain to select values from.
selected the selected values should be moved here.
variable the variable for which the selection is done.

Implemented in Branching, Conflicts, Failures, Lexical, MinDomain, Predefined, Random, and SolutionProbability.

void ValueOH::selectByDistance (  const Variable &  variable,
Domain &  selectable,
Domain &  selected,
StrictWeakValueOrdering &  better
)  [protected]
 

Select the best values according to the current preference and distance setting. Values are sorted according to the heuristic's preferrence, then the one at index `m_distance' is chosen.

Parameters:
selectable the list of variables to select from.
selected selected variables should be moved here.
better the functor used to determine if an element should precede another one.

void ValueOH::selectByQuality (  const Variable &  variable,
Domain &  selectable,
Domain &  selected,
StrictWeakValueOrdering &  better,
StrictWeakValueOrdering &  equal
)  [protected]
 

Select the best values according to the current preference and quality setting.

Parameters:
selectable the list of variables to select from.
selected selected variables should be moved here.
better the functor used to determine if an element should precede another one.
equal the functor used to determine if two elements are equal.

void ValueOH::setDistance (  size_t  distance  )  [inline]
 

Set the distance to be used by the next call to selectByDistance(). If set to 0, heuristics will not use distance-based selection.

void ValueOH::solutionFound (  const Solution &  solution  ) 
 

Let this value ordering heuristic know that a solution has been found.

Parameters:
solution the solution found.

void ValueOH::sort (  Domain &  original,
Domain &  sorted,
Variable &  variable,
StrictWeakValueOrdering &  better,
StrictWeakValueOrdering &  equal
)  [protected]
 

Compute a sorted copy of a domain of a variable. Values are sorted based on how good the heuristic considers them to be.

Parameters:
original the values in the domain of a variable.
sorted the sorted values should be put here.
variable the variable whose domain we want to sort.
better the functor used to determine if an element should precede another one.
equal the functor used to determine if two elements are equal.

void ValueOH::sort (  Domain &  original,
Domain &  sorted,
Variable &  variable
)  [virtual]
 

Compute a sorted copy of a domain of a variable. Values are sorted based on how good the heuristic considers them to be. FIXME: This function's default implementation simply aborts. Normally, this function should be pure virtual, but not all value ordering heuristics implement the quality based selection mechanism yet.

Parameters:
original the values in the domain of a variable.
sorted the sorted values should be put here.
variable the variable whose domain we want to sort.

Reimplemented in Branching, Conflicts, Failures, Lexical, MinDomain, Random, and SolutionProbability.

Member Data Documentation

bool ValueOH::m_analysis [protected]
 

`true' if the heuristic's quality is to be analyzed. Requires preloading of all known problem solutions. See Decomposition::getPerfectValues() & Problem::add(Solution&).

The documentation for this class was generated from the following files:
Generated on Wed May 25 12:21:22 2005 for csp.kdevelop by  doxygen 1.3.9.1