CODEWITHSUNDEEP
mathartificial-intelligenceconstraint-programming
Torben G
Torben G

Reputation: 790

Find Constraint network - arc-consistency

I have a question about an arc consistency network example. its nothing with code.

i have a network R with Variables X = {x1, x2, x3, x4, x5, x6, x7, x8} and Domains D = {1,2,3,4}. This are my constraints:

enter image description here

I have the solution fromy my professor. But i dont understand what happend with C24 / why nothing happend with C24.

enter image description here

I think D2 is 2,3,4 and D4 is default 1,2,3,4. If x2 is not equal x4 (C24), x4 should be 1. I hope someone could help me.

Upvotes: 0

Views: 141

Answers (1)

jschimpf
jschimpf

Reputation: 5034

A constraint c(xi,xj) is arc-consistent iff for every value a∈Di there exists a value b∈Dj such that c(a,b) is true (and vice versa with i and j swapped).

If your constraint is xi < xj, then the situation Di={1,2,3}, Dj={1,2,3,4} is not arc-consistent because there is no xi∈{1,2,3} that makes xi < 1 true. To get arc-consistency, you must eliminate 1 from Dj.

However, with the constraint xi ≠ xj and Di={1,2,3}, Dj={1,2,3,4} you already have arc-consistency, because for every xj∈{1,2,3,4} there exists an xi∈{1,2,3} that makes xi ≠ xj true (and for every xi∈{1,2,3} there exists an xj∈{1,2,3,4} that makes xi ≠ xj true).

Upvotes: 2

Related Questions