Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs

Wallace, Richard J.

Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs

Download BibTeX Cite

Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence. Constraint Satisfaction Problems. Pages 239-246.

Abstract

On the basis of its optimal asymptotic time complexity, AC-4 is often considered the best algorithm for establishing arc consistency in constraint satisfaction problems (CSPs). In the present work, AC3 was found to be much more efficient th~m AC-4, for CSPs with a variety of features. (Variable pairs were in lexical order, ~md in AC-3 they were added to the end of the list of pairs.) This is supported by arguments for the superiority of AC-3 over most of the nmge of constraint satisfiabilities ~md for the unlikelihood of conditions leading to worst-case perfonmmce. The efficiency of AC-4 is affected by the order of variable testing in Phase 1 ('setting up' phase); perform~mce in this phase can thus be enhanced, and this establishes initial conditions for Phase 2 that improve its performance. But, since AC-3 is improved by the smne orderings, it still outperforms AC-4 in most cases.

Richard J. Wallace. 1993. Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs. In Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93. IJCAI, 239–246. https://ijcai.org/proceedings/1993/34

@inproceedings{ijcai1993p34,
  title     = {Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs},
  author    = {Wallace, Richard J.},
  booktitle = {Proceedings of the Thirteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-93}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ruzena Bajcsy},
  pages     = {239--246},
  year      = {1993},
  note      = {Constraint Satisfaction Problems},
  url       = {https://ijcai.org/proceedings/1993/34},
}

TY  - CPAPER
TI  - Why AC-3 is Almost Always Better than AC4 for Establishing Arc Consistency in CSPs
AU  - Wallace, Richard J.
T2  - Proceedings of the Thirteenth International Joint Conference on Artificial Intelligence, IJCAI-93
PB  - International Joint Conferences on Artificial Intelligence
PY  - 1993
SP  - 239
EP  - 246
UR  - https://ijcai.org/proceedings/1993/34
ER  -