Speeding up the Arc Consistency algorithm in Constraint Satisfaction Problems: A New Modification of AC-3

Document Type : Research Paper

Author

Department of Advanced Technologies, University of Mohaghegh Ardabili.

10.22059/jac.2022.88375

Abstract

Dealing with constraints is always very common in real-world implementation issues. Search algorithms for real problems are also no exception. Because of the constraints in search problems (named Constraint Satisfaction Problems (CSPs)), their main solving algorithm is presented in backtracking form. The constraint propagation algorithm is an auxiliary tool to avoid facing constraint conditions as well as reducing search options. This algorithm has been presented in almost seven versions so far. In this paper, we have updated the third version of this algorithm, which is presented under the title of AC-3, from five aspects and have increased its capabilities. The most important feature of our proposed algorithm is its low time complexity. This feature has been made possible by two auxiliary criteria introduction for detecting more critical binary constraints. Faster investigation of critical constraints leads to early detection of dead-end in the search path and the search continues in this direction stops.

Keywords

Journal of Algorithms and Computation
Volume 54, Issue 1
June 2022
Pages 125-138

Files

Share

How to cite

Statistics