#include <RP.h>
Inheritance diagram for RP:
Public Member Functions | |
| RP (Problem &problem, Retraction &retraction) | |
| virtual bool | restoresArcConsistency () const |
| virtual bool | propagate (const vlist_type &uninstantiatedVariables, const vlist_type &modifiedVariables, const bool keepChanges=true) |
|
||||||||||||||||
|
This method does the actual constraint propagation. The `modifiedVariables' list has a crucial role in the structure of a filter. Forward pruning removes from the domains of the uninstantiated variables all the values inconsistent with the variables that have just been instantiated/modified (which should be in `modifiedVariables'). Backward checking works by ensuring that the variables that have just been instantiated are consistent with all the variables instantiated before it. Without `modifiedVariables', none of these filters would work. Even more advanced filters (like AC-3) might use it, for instance if it is possible to restore arc consistency only locally. Note that propagate() should check constraints between instantiated variables too, if those instantiated variables are marked as current. See Decomposition::autoSelectVariables() for details. Variables whose domains get reduced to a single value in propagate() will not be considered instantiated until Decomposition::decompose() is called recursively. This function shouldn't attempt to modified instantiated variables. They can inspect them, their domains and/or constraints, but it's not allowed to change them. Finally, if propagate() is called and all the variables have their domains reduced to a single value, the filter should be able to say whether or not we have a solution. FIXME: really? This should not be a guarantee in the filter, but rather in the way it is used.
Implements Filter. |
|
|
Return `true' if this is an `AC' filter, i.e. it always restores full arc consistency. This is a very important characteristic of a filter, mainly because the decomposition needs to know whether or not the filter does that. If the filter restores arc consistency, the decomposition can deactivate constraints that connect current variables with past ones (thus avoiding unnecessary constraint checks). To better understand the problem, you have to remember that the library allows the decomposition to modify more than one variable at a given depth. That is, there is no guarantee that there will be a unique `current' variable at any given depth. One could presumably write a decomposition where at every depth it instantiates an arbitrary number of variables. The reason backward constraints cannot be deactivated in filters that do not restore full arc consistency has to do with the case when more than one variable is modified at a given depth (and the filter is ran with `modified' containing more than one variable. Take `forward pruning' for an example. In theory, it is a forward filter, so we don't need to look back at the past variables. But if more than one variable is modified at a given depth, then we can come up with a small example where forward prunning would allow the decomposition to add to the partial solution instantiations that are not consistent with each other (even though they are consistent with all the past and future variables). This can happen for instance if at depth `d' we select variable X and Y, run the `forward pruning' filter and if that succedes, we add X and Y to the partial solution. If X and Y are indirectly linked one iteration through (X Y) might not make the subproblem consistent. `backward checking' works by verifying after each instantiation that the instantiation of the currently selected variable is consistent with the instantiations of all the previously instantiated variables. Thus, if we remove the back constraints, `backward checking' will not work. `backward checking' and `forward pruning' are not `AC' filters. filters because they do not restore arc consistency. Implements Filter. |
1.3.9.1