Constraint learning: Difference between revisions

Revision as of 19:21, 9 February 2006

Revision as of 19:28, 9 February 2006

Line 15:

==Graph-based learning==

Graph-based learning uses the same rationale of graph-based [[backjumping]]: if the algorithm proves all values of <math>x_{k+1}</math> to be inconsistent with <math>x_1=a_1,\ldots,x_k=a_k</math>, then <math>x_1,\ldots,x_k</math>this evaluation was consistent, as (otherwise the algorithm would not hadhave evaluated <math>x_{k+1}</math>) at all; as a result, butthe eachconstraints violated by a value of <math>x_{k+1}</math> violatestogether somewith constraints<math>x_1=a_1,\ldots,x_k=a_k</math> all contain <math>x_{k+1}</math>.

As Aa result, a small inconsistent partial evaluation can be found by restricting <math>x_1,\ldots,x_k</math> to variables that are in a constraint with <math>x_{k+1}</math>, ifprovided that this constraint contains no unassigned variable.

This method is called "graph-based" because the information on which pairs of variables are in the same constraint can be found out from the graph associated to the constraint satisfaction problem.