|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectnet.sf.cpsolver.ifs.extension.Extension<V,T>
net.sf.cpsolver.ifs.extension.MacPropagation<V,T>
public class MacPropagation<V extends Variable<V,T>,T extends Value<V,T>>
MAC propagation.
During the arc consistency maintenance, when a value is deleted from a
variable�s domain, the reason (forming an explanation) can be computed and
attached to the deleted value. Once a variable (say Vx with the assigned
value vx) is unassigned during the search, all deleted values which contain a
pair Vx = vx in their explanations need to be recomputed. Such value can be
either still inconsistent with the current (partial) solution (a different
explanation is attached to it in this case) or it can be returned back to its
variable's domain. Arc consistency is maintained after each iteration step,
i.e., the selected assignment is propagated into the not yet assigned
variables. When a value vx is assigned to a variable Vx, an explanation Vx !=
vx' ← Vx = vx is attached to all values vx' of the variable Vx,
different from vx.
In the case of forward checking (only constraints going from assigned
variables to unassigned variables are revised), computing explanations is
rather easy. A value vx is deleted from the domain of the variable Vx only if
there is a constraint which prohibits the assignment Vx=vx because of the
existing assignments (e.g., Vy = vy, � Vz = vz). An explanation for the
deletion of this value vx is then Vx != vx ← (Vy = vy & ... Vz = vz),
where Vy = vy & ... Vz = vz are assignments contained in the prohibiting
constraint. In case of arc consistency, a value vx is deleted from the domain
of the variable Vx if there is a constraint which does not permit the
assignment Vx = vx with other possible assignments of the other variables in
the constraint. This means that there is no support value (or combination of
values) for the value vx of the variable Vx in the constraint. An explanation
is then a union of explanations of all possible support values for the
assignment Vx = vx of this constraint which were deleted. The reason is that
if one of these support values is returned to its variable's domain, this
value vx may be returned as well (i.e., the reason for its deletion has
vanished, a new reason needs to be computed).
As for the implementation, we only need to enforce arc consistency of the
initial solution and to extend unassign and assign methods. Procedure
afterAssigned(long, Value)
enforces arc consistency of
the solution with the selected assignment variable = value and the procedure
afterUnassigned(long, Value)
"undoes" the assignment
variable = value. It means that explanations of all values which were deleted
and which contain assignment variable = value in their explanations need to
be recomputed. This can be done via returning all these values into their
variables� domains followed by arc consistency maintenance over their
variables.
Parameters:
Parameter | Type | Comment |
---|---|---|
MacPropagation.JustForwardCheck | Boolean |
If true, only forward checking instead of full arc consistency is maintained during the search. |
Field Summary | |
---|---|
protected List<Constraint<V,T>> |
iConstraints
List of constraints on which arc-consistency is to be maintained |
protected long |
iIteration
Current iteration |
Constructor Summary | |
---|---|
MacPropagation(Solver<V,T> solver,
DataProperties properties)
Constructor |
Method Summary | |
---|---|
void |
addConstraint(Constraint<V,T> constraint)
Adds a constraint on which arc-consistency is to be maintained |
void |
afterAssigned(long iteration,
T value)
After a value is assigned: explanations of other values of the value's variable are reset (to contain only the assigned value), propagation over the assigned variable takes place. |
void |
afterUnassigned(long iteration,
T value)
After a value is unassigned: explanations of all values of unassigned variable are recomputed ( Value.conflicts() ), propagation undo
over the unassigned variable takes place. |
void |
beforeAssigned(long iteration,
T value)
Before a value is unassigned: until the value is inconsistent with the current solution, an assignment from its explanation is picked and unassigned. |
boolean |
contains(Constraint<V,T> constraint)
Returns true, if arc-consistency is to be maintained on the given constraint |
Set<T> |
goodValues(V variable)
good values of a variable (values not removed from variables domain) |
boolean |
init(Solver<V,T> solver)
Initialization. |
boolean |
isGood(T value)
is variable good |
Set<T> |
noGood(T value)
variables explanation |
protected void |
propagate(Queue<V> queue)
Propagation over the queue of variables. |
protected void |
propagate(V variable)
Propagation over the given variable. |
protected boolean |
propagate(V aVariable,
V anotherVariable)
|
protected boolean |
propagate(V aVariable,
V anotherVariable,
List<T> adepts)
|
protected void |
setGood(T value)
sets value to be good |
void |
setNoGood(T value,
Set<T> reason)
sets value's explanation |
void |
undoPropagate(V variable)
Propagation undo over the given variable. |
Methods inherited from class net.sf.cpsolver.ifs.extension.Extension |
---|
beforeUnassigned, constraintAdded, constraintRemoved, getModel, getProperties, getSolver, isRegistered, register, unregister, useValueExtra, useVariableExtra, variableAdded, variableRemoved |
Methods inherited from class java.lang.Object |
---|
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
---|
protected List<Constraint<V extends Variable<V,T>,T extends Value<V,T>>> iConstraints
protected long iIteration
Constructor Detail |
---|
public MacPropagation(Solver<V,T> solver, DataProperties properties)
Method Detail |
---|
public void addConstraint(Constraint<V,T> constraint)
public boolean contains(Constraint<V,T> constraint)
public void beforeAssigned(long iteration, T value)
beforeAssigned
in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
beforeAssigned
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
iteration
- current iterationvalue
- value to be assignedpublic void afterAssigned(long iteration, T value)
afterAssigned
in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
afterAssigned
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
iteration
- current iterationvalue
- value to be assignedpublic void afterUnassigned(long iteration, T value)
Value.conflicts()
), propagation undo
over the unassigned variable takes place.
afterUnassigned
in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
afterUnassigned
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
iteration
- current iterationvalue
- value to be unassignedpublic boolean init(Solver<V,T> solver)
init
in interface ModelListener<V extends Variable<V,T>,T extends Value<V,T>>
init
in class Extension<V extends Variable<V,T>,T extends Value<V,T>>
solver
- IFS solverprotected void propagate(V variable)
protected void propagate(Queue<V> queue)
public void undoPropagate(V variable)
protected boolean propagate(V aVariable, V anotherVariable, List<T> adepts)
protected boolean propagate(V aVariable, V anotherVariable)
public Set<T> goodValues(V variable)
public Set<T> noGood(T value)
public boolean isGood(T value)
protected void setGood(T value)
public void setNoGood(T value, Set<T> reason)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |