Narrowing Support Searching Range in Maintaining Arc Consistency for Solving Constraint Satisfaction Problems
2017
Arc consistency is the most popular filtering technique for solving constraint satisfaction problems. Constraint check plays a central role in establishing arc consistency. In this paper, we propose a method to save constraint checks in maintaining coarse-grained arc consistency during backtracking search for solving the constraint satisfaction problems. We reduce the support searching range by utilizing the information generated by an AC3.1 algorithm at preprocessing step. Compared with the existing maintaining arc consistency (MAC) algorithms, the proposed MAC $3_{be}$ algorithm saves constraint checks without maintaining additional data structures at each search tree node. Our experimental results show that MAC $3_{be}$ saves both constraint checks and CPU time while solving some benchmark problems.
Keywords:
- Complexity of constraint satisfaction
- Backtracking
- Constraint learning
- Mathematical optimization
- Computer science
- Local consistency
- Hybrid algorithm (constraint satisfaction)
- Constraint logic programming
- Constraint satisfaction problem
- AC-3 algorithm
- Algorithm
- Constraint programming
- Constraint graph
- Constraint satisfaction
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
31
References
4
Citations
NaN
KQI