AC-3_d an Efficient Arc-Consistency Algorithm with a Low Space-complexity

Arc-consistency algorithms are widely used to prune the search-space of Constraint Satisfaction Problems (CSPs). They use support-checks to find out about the properties of CSPs. They use arc-heuristics to select the constraint and domain-heuristics to select the values for their next support-check. We will demonstrate that domain-heuristics can significantly enhance the average time-complexity of existing arc-consistency algorithms. We will combine Alan Mackworth’s AC-3 and John Gaschnig’s DEE and equip the resulting hybrid with a double-support domain-heuristic thereby creating an arc-consistency algorithm called AC-3_d, which has an average time-complexity which can compete with AC-7 and which improves on AC-7’s space-complexity. AC-3_d is easy to implement and requires the same data structures as AC-3. We will present experimental results to justify our average time-complexity claim