Übung vom 07.06.2013

Consider a scheduling problem, where there are five variables A, B, C, D, and E, each with domain {1,2,3,4}. Suppose the constraints are:

E-A is odd, A < D, D < C, E > B, A != B, E != C, E != D.

Show how backtracking can be used to solve this problem, using the variable ordering A,B,C,D,E. To do this you should draw the search tree generated to find all answers. Indicate clearly the satisfying assignments.

To indicate the search tree, write it in text form with each branch on one line. For example, suppose we had variables X, Y and Z with domains t, f, and constraints X != Y, Y != Z. The corresponding search tree can be written as:

X=t Y=t failure
    Y=f Z=t solution
        Z=f failure
X=f Y=t Z=t failure
        Z=f solution
    Y=f failure 

Hint: this may be large! You do not need to write down the complete search tree.

Show how arc consistency can be used to solve this problem. To do this you need to:

1. draw the constraint graph,

2. show which elements of a domain are deleted at each step, and which arc is responsible for removing the element,

3. show explicitly the constraint graph after arc consistency has stopped.