AC3
AC3 is one of many algorithms (1 - 7 and lots more!)
Only consider binary constraints with 2 variables
For this algorithm, we revise directed arcs
- I.e. when considering constraint x-y we remove values from y
- when considering y-x we remove values from x
- of course both constraints are really the same one
AC3 can be done in polynomial time, em3
- (e = number of constraints in problem, m = domain size)
- emphasises that AC does not solve CSP’s