Content deleted Content added
→Definition: relevant constraints |
new section "efficiency" |
||
Line 19:
| If the algorithm reaches the same values of <math>x_1</math> and <math>x_4</math> again, the new constraint blocks the search.
|}
==Efficiency of constraint learning==
The efficiency of constraint learning algorithm is balanced between two factors. On one hand, the more often a recorded constraint is violated, the more often backtracking avoids doing useless search. Small inconsistent subsets of the current partial solution are usually better than large ones, as they correspond to constraints that are easier to violate. On the other hand, finding a small inconsistent subset of the current partial evaluation may require time, and the benefit may not be balanced by the subsequent reduction of the search time.
Line 24 ⟶ 26:
Size is however not the only feature of learned constraints to take into account. Indeed, a small constraint may be useless in a particular state of the search space because the values that violate it will not be encountered again. A larger constraint whose violating values are more similar to the current partial assignment may be preferred in such cases.
Various constraint learning
==Graph-based learning==
| |||