CS3243 Introduction to AI Tutorial 4

Question 3

On arc-consistency:

\(X_{i}\) is arc-consistent with respect to another variable \(X_{j}\) if for every value in the current domain \(D_{i}\) there is some value in the domain \(D_{j}\) that satisfies the binary constraint on the arc (\(X_{i}, X_{j}\))

On constraint graph:

The nodes of the graph correspond to variables of the problem, and a link connects any two variables that participate in a constraint.

Constraint Graph

Assuming that we have no other arcs to process, the following is the constraint graph constructed:

[A]— \([A = B + 1]\) —[B]— \([B = 2C]\) —[C]

Tracing

\((A, B)\)

Since \(A = B + 1\) is the constraint, Domain \(D_A\) will be reduced to {1, 2, 3, 4} to be make arc \((A, B)\) arc-consistent.

State:

\(D_A = \{1, 2, 3, 4\}\)

\(D_B = \{0, 1, 2, 3, 4\}\)

\(D_C = \{0, 1, 2, 3, 4\}\)

\((B, A)\)

Since \(B = A - 1\) is the constraint, Domain \(D_B\) will be reduced to {0, 1, 2, 3} to be make arc \((B, A)\) arc-consistent.

State:

\(D_A = \{1, 2, 3, 4\}\)

\(D_B = \{0, 1, 2, 3\}\)

\(D_C = \{0, 1, 2, 3, 4\}\)

\((B, C)\)

Since \(B = 2C\) is the constraint, Domain \(D_B\) will be reduced to {0, 2} to be make arc \((B, C)\) arc-consistent. This change causes arc \((A, B)\) to be re-inserted to the arc queue.

State:

\(D_A = \{1, 2, 3, 4\}\)

\(D_B = \{0, 2\}\)

\(D_C = \{0, 1, 2, 3, 4\}\)

\((C, B)\)

Since \(C = \frac{B}{2}\) is the constraint, Domain \(D_C\) will be reduced to {0, 1} to be make arc \((C, B)\) arc-consistent.

State:

\(D_A = \{1, 3\}\)

\(D_B = \{0, 2\}\)

\(D_C = \{0, 1\}\)

\((A, B) : revise\)

Since Domain \(D_B\) has been changed, based on the constraint graph, Domain \(D_A\) will be reduced to {1, 3} to be make arc \((A, B)\) arc-consistent again.

State:

\(D_A = \{1, 3\}\)

\(D_B = \{0, 2\}\)

\(D_C = \{0, 1\}\)