AI Search · Exam notes
One CSP comprehension per paper, five sub-questions on three variables: which tuples are in each relation? is it arc consistent? after enforcing it, is it path consistent? what is the solution? One chain answers all: build each relation value by value, delete unsupported values with revise until nothing changes, check witnesses on the triangle, read off the singletons.
| Term | Meaning |
|---|---|
| Variable, domain | A variable (A, B, C) with a set of possible values, here each \(\{1,2,3,4\}\). |
| Constraint, relation | A rule like \(A = mod(2C,3)\); the relation lists the allowed value pairs, e.g. \(R_{AC}\). |
| Constraint graph | Variables as nodes, constraints as edges. Here a triangle: A-B, B-C, A-C. |
| Matching diagram | Values as nodes, allowed pairs as links. Support = a link to the other side. |
| Arc consistent | Every value of every variable has a supporting value in each neighbor. One unsupported value breaks it. |
| Revise(X,Y) | Delete values of X with no support in Y. Repeat over all arcs (AC-3 queues them) until no change. |
| Path consistent | For every allowed pair on one edge, some value of the third variable completes both links of the triangle. |
3a. The data as tables (solve from this, then check the walkthrough)
| Constraint | Meaning |
|---|---|
| R_AC: A = mod(2C,3) | C=1 gives A=2; C=2 gives A=1; C=3 gives 0 (out); C=4 gives A=2 |
| R_BA: B = mod(3A,4) | A=1 gives B=3; A=2 gives B=2; A=3 gives B=1; A=4 gives 0 (out) |
| R_CB: C = mod(2B,3) | B=1 gives C=2; B=2 gives C=1; B=3 gives 0 (out); B=4 gives C=2 |
| Relation | Tuples |
|---|---|
| R_AC (A,C) | (1,2), (2,1), (2,4) |
| R_BA (B,A) | (1,3), (2,2), (3,1) |
| R_CB (C,B) | (1,2), (2,1), (2,4) |
Cover the walkthrough. Compute the three relations, revise each arc until the domains stop shrinking, check witnesses, read the answer.
3b. Walkthrough: one revise per step, deletions tracked
Why this step
Tracker
3c. The five questions
CSP on A, B, C with \(D_A = D_B = D_C = \{1,2,3,4\}\), \(R_{AC}\): \(A = mod(2C,3)\), \(R_{BA}\): \(B = mod(3A,4)\), \(R_{CB}\): \(C = mod(2B,3)\). \(mod(n,d)\) is the remainder, e.g. \(mod(8,3) = 2\).
3d. Answers first, then the working
\(R_{AC}\): (1,2), (2,1), (2,4). \(R_{BA}\): (1,3), (2,2), (3,1). Arc consistent? No. After enforcing: path consistent. Solution: 2,2,1.
| Revise step | Support rows | Domains after |
|---|---|---|
| A wrt C | 1 keeps (C=2); 2 keeps (C=1,4); 3 dead; 4 dead | A={1,2} |
| C wrt A | 1,2,4 keep; 3 dead (needs A=0) | C={1,2,4} |
| B wrt A | 2 keeps (A=2); 3 keeps (A=1); 1 dead (needs A=3); 4 impossible | B={2,3} |
| A wrt B | 1 keeps (B=3); 2 keeps (B=2): no change | - |
| C wrt B | 1 keeps (B=2); 2 dead (needs B=1,4); 4 impossible | C={1} |
| B wrt C | 2 keeps (C=1); 3 dead (needs C=0) | B={2} |
| A wrt B | 2 keeps (B=2); 1 dead (needs B=3) | A={2} |
| re-verify | no change anywhere: arc consistent | 2,2,1 |
Solve each with a pen before opening the answer. Each drill is self contained.
Variables A, B with \(D_A = D_B = \{1,2\}\), one constraint \(A < B\). Q1: is the CSP arc consistent? Q2: run revise both ways; Q3: solution?
Why this step
Tracker
Q1: No. A=2 has no B above it; B=1 has no A below it. Q2: revise A wrt B deletes 2 (\(D_A = \{1\}\)); revise B wrt A deletes 1 (\(D_B = \{2\}\)). Q3: singletons read off: A=1, B=2, and \(1 < 2\) holds.
Variables A, B with \(D_A = D_B = \{1,2,3\}\), one constraint \(B = mod(2A,3)\). Q1: list \(R_{BA}\) as (B,A) tuples. Q2: arc consistent? Q3: domains after enforcing? Q4: solution?
Why this step
Tracker
Q1: A=1 gives B=2; A=2 gives B=1; A=3 gives 0, out. So (2,1), (1,2). Q2: No, A=3 is dead. Q3: revise A wrt B drops 3 (\(D_A = \{1,2\}\)); B=1 keeps A=2, B=2 keeps A=1, B=3 was never producible (mod 3 yields 0,1,2) so it drops too (\(D_B = \{1,2\}\)). Q4: not unique: (A,B) = (1,2) or (2,1). Arc consistency shrinks domains; search picks the solution. That is the standard follow-up trap.