Constraint learning: Difference between revisions

Revision as of 15:46, 10 February 2006

Revision as of 15:54, 10 February 2006

Line 20:

|}

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 block backtracking fromavoids doing useless search. As a result, algorithms search for small inconsistent subsetsubsets of the current partial solution are preferred over 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.

Various constraint learning technique exist, differing in strictness of recorded constraints and cost of finding them.