Content deleted Content added
No edit summary |
{{1r}} |
||
| (2 intermediate revisions by the same user not shown) | |||
Line 1:
{{mi|{{Nf|date=November 2024}}{{1r|date=November 2024}}}}
In [[constraint satisfaction problem|constraint satisfaction]] [[backtracking]] [[algorithm]]s, '''constraint learning''' is a technique for improving efficiency. It works by recording new constraints whenever an inconsistency is found. This new constraint may reduce the [[Candidate solution|search space]], as future partial evaluations may be found inconsistent without further search. '''Clause learning''' is the name of this technique when applied to [[propositional satisfiability]].
Line 22 ⟶ 23:
==Efficiency of constraint learning==
The efficiency gain of constraint learning is balanced between two factors. On one hand, the more often a recorded constraint is violated, the more often backtracking avoids doing useless
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.
Line 38 ⟶ 39:
==Jumpback learning==
Jumpback learning is based on storing as constraints the inconsistent assignments that would be found by [[conflict-based backjumping]]. Whenever a partial assignment is found inconsistent, this algorithm selects the violated constraint that is minimal according to an ordering based on the order of instantiation of variables. The evaluation restricted
The ordering on constraints is based on the order of assignment of
==Constraint maintenance==
| |||