Constraint Processing

Wiki-Quelltext dieser Seite.

<language>Java</language>
=== Introduction ===
In out lecture you already learned about a generic backtracking algorithm that is able to solve any Constraint Satisfaction Problem (CSP) with ''variables'', ''domains'' and ''constraints''. In order to reduce the search space, we used forward checking and arc consistency methods. These algorithms remove inconsistent values from the domains of the variables, that are not yet part of the partial solution. They work for ''binary constraints'' as well as for ''non-binary constraints''. For the latter, just recapitulate one possible ''generic arc consistency algorithm'':

 '''procedure GAC(G)'''
  Let Q be the set of (undirected) constraints of G 
  '''while Q not empty do'''
   select and remove any constraint c from Q;
   '''for each variable x participating in c'''
     REVISE(x,c)
     '''if REVISE(x,c) changed the domain of x then'''
       add to Q the set of all constraints that include x (except c);


  '''procedure REVISE (x,c)'''
      '''for each value a in domain of x do'''
        '''if there is no tuple in the relation of c that includes (x,a) and is valid'''
            then delete a from the domain of x

We could reuse this algorithm to check any constraint that comes to our mind. Just look at each tuple in the relation of c and decide, if it is valid or not. Notice that you need a ''check''-procedure for each constraint that decides whether a tuple fulfills this constraint or not. Although this always works, it can be very ineffective. For example, consider a constraint ''alldifferent($x_1,..,x_n$)'' with n variables each having a domain of size d. Then the GAC algorithm runs in $O(n*d^n)$ (for each variable we have to check $d^n$ tuples). It is possible to design specialized algorithms that perform faster.

Of course, we really want to remove exactly those inconsistent values the REVISE-procedure is looking for. However, it is often better not to take the procedure literally! Instead we want to write constraint-specific filtering methods, that exploit the ''semantics of a constraint''. 

What I mean is, each constraint should be responsible for maintaining a consistent state of the domains of the variables in its scope. Each constraint should be associated with a specific procedure, that removes values from the domains that are not part of a valid tuple in the relation. We call this procedure ''propagator''. Our constraint solver doesn't need to know more about our constraint than its propagator method. We say: ''The propagator implements a constraint''. As with other consistency methods (FC, AC, GAC) we do not need a constraint checking method or something like that, because the propagators ensure, that the solver can only assign values to variables, that are valid with regard to the state of the partial solution.