Huang Lie Jun edited On_constraint_graph_begin_quote__.tex  about 8 years ago

Commit id: 5374f78e5e3155046682448dad15898447f7faec

deletions | additions      

       

\begin{quote}  The nodes of the graph correspond to variables of the problem, and a link connects any two variables that participate in a constraint.  \end{quote}Assuming that we have no other arcs to process, the following is the constraint graph constructed:  \begin{center}  [A]---[B]---[C]  \end{center}  \subsection{\( . (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\}\)  \subsection{\( . (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\}\)  \subsection{\( . (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.  State:  \(D_A = \{1, 2, 3, 4\}\)  \(D_B = \{0, 2\}\)  \(D_C = \{0, 1, 2, 3, 4\}\)  \subsection{\( . (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, 2, 3, 4\}\)  \(D_B = \{0, 2\}\)  \(D_C = \{0, 1\}\)