Constraint learning: Difference between revisions

Revision as of 11:22, 27 April 2006

Revision as of 20:16, 27 September 2006

Line 7:

If the partial solution <math>x_1=a_1,\ldots,x_k=a_k</math> is inconsistent, the problem instance implies the constraint stating that <math>x_i=a_i</math> cannot be true for all <math>i \in [1,k]</math> at the same time. However, recording this constraint is not useful, as this partial solution will not be encountered again due to the way backtracking proceed.

On the other hand, if a subset of this evaluation is inconsistent, the corresponding constraint may be useful in the subsequent search, as the same subset of the partial evaluation may occur again in the search. For example, the algorithm may enounterencounter an evaluation extending the subset <math>x_2=a_2, x_5=a_5, x_{k-1}=a_{k-1}</math> of the previous partial evaluation. If this subset is inconsistent and the algorithm has stored this fact in form of a constraint, no further search is needed to conclude that the new partial evaluation cannot be extended to form a solution.

{| cellpadding=20