3 ms·
Thank you for your explanation. However, as someone who has merely dabbled in Prolog (I've written less than 2000 lines of Prolog in total), I still don't under
by kccqzy 6y ago
Thank you for your explanation. However, as someone who has merely dabbled in Prolog (I've written less than 2000 lines of Prolog in total), I still don't understand the distinction between all_different/1 and all_distinct/1.
Even the documentation for all_different/1 https://www.swi-prolog.org/pldoc/man?predicate=all_different/1 https://www.swi-prolog.org/pldoc/man?predicate=all_different... asks the user to consider using all_distinct instead. I'm afraid I just don't have a mental model of how CLP(FD) works to understand what is meant to "stronger" or "weaker" propagation.
- mzl 6y agoSome terminology: a propagator is an implementation of a constraint, and is used to remove values from variable domains, by deducing that they are in no solution. In general, propagation strength is about how much a propagator can deduce, that is, how many values it can remove while still not removing a value that is in some solution to the constraint. As an example, consider the variables x=1, y in {2, 3}, z in {2, 3}, w in {1, 2, 3, 4} with the constraint all_different(x, y, z, w) added (note here that I will use that names for the constraint, and refer to the propagation strength of a propagator). With value-propagation (sometimes called forward-checking), a propagator would deduce the new domains x=1, y in {2, 3}, z in {2, 3}, w in {2, 3, 4} by simply removing assigned values from other variables domains. However, there are stronger propagators for the constraint. In particular, there is well-known and reasonably efficient (O(n^2.5)) propagator that is domain-consistent (also known as GAC or generalized arc consistent). That means that it can always remove _all_ values from variables that are in no solution. The above example with that propagator would deduce x=1, y in {2, 3}, z in {2, 3}, w=4 The reasoning is based on something called Hall-sets. In the above example, y and z form a Hall set of size 2, since they must take the values 2 and 3 in any solution. there are also other propagators with different propagation strengths. For all_different, there are also bounds-consistent propagators, that can do more than value propagation, but only on does advanced reasoning based on the bounds of variables. I think that SWI Prolog uses the all_different name for value propagation, and all_distinct for domain propagation. In the CP system Gecode that I'm most familiar with, we use an argument to the distinct-constraint (same constraint, different name) to indicate the desired level of propagation (https://www.gecode.org/doc-latest/reference/group__TaskModelIntDistinct.html https://www.gecode.org/doc-latest/reference/group__TaskModel...).