
Bounds consistent distinct propagator. More...
#include <distinct.hh>
Public Member Functions | |
| virtual ExecStatus | propagate (Space &home, const ModEventDelta &med) |
| Perform propagation. More... | |
| virtual PropCost | cost (const Space &home, const ModEventDelta &med) const |
| Cost function. More... | |
| virtual Actor * | copy (Space &home, bool share) |
| Copy propagator during cloning. More... | |
| virtual size_t | dispose (Space &home) |
| Destructor. More... | |
Public Member Functions inherited from Gecode::Propagator | |
| ModEventDelta | modeventdelta (void) const |
| Return the modification event delta. More... | |
| virtual ExecStatus | advise (Space &home, Advisor &a, const Delta &d) |
| Advise function. More... | |
| double | afc (const Space &home) const |
| Return the accumlated failure count. More... | |
Public Member Functions inherited from Gecode::Actor | |
Static Public Member Functions | |
| static ExecStatus | post (Home home, ViewArray< View > &x) |
| Post propagator for view array x. More... | |
Static Public Member Functions inherited from Gecode::Actor | |
| static void * | operator new (size_t s, Space &home) |
| Allocate memory from space. More... | |
| static void | operator delete (void *p, Space &home) |
| No-op for exceptions. More... | |
Protected Member Functions | |
| Bnd (Home home, ViewArray< View > &x) | |
| Constructor for posting. More... | |
| Bnd (Space &home, bool share, Bnd< View > &p) | |
| Constructor for cloning p. More... | |
Protected Member Functions inherited from Gecode::Propagator | |
| Propagator (Home home) | |
| Constructor for posting. More... | |
| Propagator (Space &home, bool share, Propagator &p) | |
| Constructor for cloning p. More... | |
| Propagator * | fwd (void) const |
| Return forwarding pointer during copying. More... | |
Protected Attributes | |
| ViewArray< View > | x |
| Views on which to perform bounds-propagation. More... | |
| ViewArray< View > | y |
Views on which to perform value-propagation (subset of x) More... | |
| int | min_x |
| Minimum (approximation) of view in x. More... | |
| int | max_x |
| Maximum (approximation) of view in x. More... | |
Bounds consistent distinct propagator.
The propagator uses staging: first it uses naive value-based propagation and only then uses bounds consistent propagation. Due to using naive value-based propagation, the propagator might actually achieve stronger consistency than just bounds consistency.
The algorithm is taken from: A. Lopez-Ortiz, C.-G. Quimper, J. Tromp, and P. van Beek. A fast and simple algorithm for bounds consistency of the alldifferent constraint. IJCAI-2003.
This implementation uses the code that is provided by Peter Van Beek: http://ai.uwaterloo.ca/~vanbeek/software/software.html The code (originally by John Tromp) here has only been slightly modified to fit Gecode (taking idempotent/non-idempotent propagation into account) and uses a more efficient layout of datastructures (keeping the number of different arrays small).
Requires
Definition at line 129 of file distinct.hh.
|
inlineprotected |
|
inlineprotected |
|
static |
|
virtual |
|
virtual |
Cost function.
If in stage for naive value propagation, the cost is low linear. Otherwise it is low quadratic.
Implements Gecode::Propagator.
|
virtual |
|
inlinevirtual |
|
protected |
Views on which to perform bounds-propagation.
Definition at line 132 of file distinct.hh.
|
protected |
Views on which to perform value-propagation (subset of x)
Definition at line 134 of file distinct.hh.
|
protected |
Minimum (approximation) of view in x.
Definition at line 136 of file distinct.hh.
|
protected |
Maximum (approximation) of view in x.
Definition at line 138 of file distinct.hh.