ROUGH DRAFT authorea.com/104070
Main Data History
Export
Show Index Toggle 0 comments
  •  Quick Edit
  • 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\}\)