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, v) is arc consistent if VXED, 3yED, such that(x, y) is allowed by constraint C 12队 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 Di then check directed arc consistency for each arc with head d Maintain arcs to be checked on FIFo queue(no duplicates). 3 Constraint Propagation Example RG Graph coloring xgtDifferent-color constraint ( R,66 Arc examined value deleted V2(G) V,(R) Arcs to examine none V3>V1 none F examination queue is empty THEN arc(pairwise) consistent3 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). Vi Vj {1,2,3} {1,2} = 4 Constraint Propagation Example R,G,B R, G G Different-color constraint V1 V2 V3 V3>V1 none V2>V1 none V1 V (R) 2-V1 V2 V (G) 2 -V3 V1 V (G) 1-V3 V1 – V2 none Arc examined Value deleted Graph Coloring Initial Domains B R G V2 V3 V1 Arcs to examine IF examination queue is empty THEN arc (pairwise) consistent