Consider a CSP with three variables and three binary constraints:
\(X < Y\)
\(Y < Z\)
\(Z < X\)
and initial domains \(D(X)=D(Y)=D(Z)=[0..100]\).
Also assume that all the three constraints are in the propagation queue initially.
Select all the true statements
The CSP is consistent, it has at least one solution
The fix-point algorithm does not detect the inconsistency, it finishes with more than one value in the domain of each variable, we will need to branch and explore a search tree to realize the domain is inconsistent.
The CSP is inconsistent, it does not contain any solution
The fix-point algorithm will eventually detect a domain wipe-out and report an inconsistency but this will take O(n) iterations (execution of prpagators) where n is the size of the initial domains of the CSP.
The fix-point will detect that the CSP is inconsistent in O(1)
Select all the true statements regarding the fix-point computation and implementation in Mini-CP.
The number of iterations of each execution of the fix-point does depend on the order in which the constraints are executed
Assuming monotonic propagators, for two different order of execution of the constraints, the fix-point computes the same domains.
Assuming monotonic propagators, for two different order of execution of the constraints, the fix-point may compute different domains for the two executions.
In Mini-CP the order in which the constraints are executed in the fix-point depend on the order in which the user has posted the constraints
Mini-CP has some strategies/heuristics implemented to reduce the length and computation cost of the fix-point computation.
The number of iterations of each execution of the fix-point does not depend on the order in which the constraints are executed
A good heuristic to reduce computation cost of the fix-point is to execute first the cheap (low complexity) constraints that propagate a lot
© 2014-2018 Université catholique de Louvain
INGInious is distributed under AGPL license