Question

Section C. Arc Consistency

Consider the following constraint network.

10. If the variables A, B and C each have the domain {1,2,3,4} before arc consistency is run, indicate what their domains will be after arc consistency has finished:

A = {               }

B = {    }

C = {                         }

11. If we have just considered the edge <B, A < B> and reduce the domain of B as a result, do we need to add any arcs back to the To-Do Arcs list? If not, why not? If so, which edges?

Answer 1

assuming the constraint network as (as it is not provided):

• dom(A) = {1, 2, 3, 4}; dom(B) = {1, 2, 3, 4}; dom(C) = {1, 2, 3, 4}
• Suppose you first select the arc <A, A < B>.
  • Remove A = 4 from the domain of A.
  • Add nothing to To-Do Arcs list.
• Suppose that <B, B < C> is selected next.
  • Prune the value 4 from the domain of B.
  • Add <A, A < B> back into the To-Do Arcs list.
• Suppose that <B, A < B> is selected next.
  • Prune 1 from the domain of B.
  • Add no element to To-Do Arcs list.
• Suppose the arc hA, A < Bi is selected next.
  • The value A = 3 can be pruned from the domain of A.
  • Add no element to To-Do Arcs list.
• Select <C, B < C> next.
  • Remove 1 and 2 from the domain of C.
  • Add <B, B < C> back into the To-Do Arcs list.

The other two edges are arc consistent, so the algorithm terminates with

dom(A) = {1, 2},

dom(B) = {2, 3},

dom(C) = {3, 4}.