Arc Consistency Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint(an arc) V {1,2, {1,2} Directed arc ( Vi, vi is arc consistent if VXED,EyED, such that (x,y)is allowed by constraint Ci Example: Given: Variables V, and v2 with Domain (1, 2, 3, 4) Constraint:{(1,3)(1,4)(2,1)} What is the result of arc consistency? Achieving Arc Consistency via Constraint Propagation Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc Directed arc(Vi, vi is arc consistent if WXED; EyeD. such that(x,y) is allowed by constraint Cil Constraint propagation: To achieve arc consistency Delete every value from each tail domain d of each arc that fails this condition Repeat until quiescence If element deleted from D then .check directed arc consistency for each arc with head d Maintain arcs to be checked on FiFo queue(no duplicates)5 Arc Consistency • Directed arc (Vi , Vj ) is arc consistent if • ∀x∈Di ∃y∈Dj such that (x,y) is allowed by constraint Cij Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). Vi Vj {1,2,3} {1,2} = Example: Given: Variables V1 and V2 with Domain {1,2,3,4} Constraint: {(1, 3) (1, 4) (2, 1)} What is the result of arc consistency? 6 Achieving Arc Consistency via Constraint Propagation • Directed arc (Vi , Vj ) is arc consistent if ∀x∈Di ∃y∈Dj such that (x,y) is allowed by constraint Cij Arc consistency eliminates values of each variable domain that can never satisfy a particular constraint (an arc). Constraint propagation: To achieve arc consistency: • Delete every value from each tail domain Di of each arc that fails this condition, • Repeat until quiescence: • If element deleted from Di then •check directed arc consistency for each arc with head Di • Maintain arcs to be checked on FIFO queue (no duplicates)