An Optimal Algorithm based on the Solution to the Coarse-Grained Arc Consistency Algorithms of the Constraint Satisfaction Problems

DOI

10.2991/csic-15.2015.4How to use a DOI?

Keywords

Constraint satisfaction problem, Maintaining arc consistency, the Coarse-grained algorithms, Revise, Degree is 1, Domain is 1

Abstract

Constraint satisfaction problem are widely used in the artificial intelligence field. We study the coarse-grained arc consistency algorithms of the Constraint satisfaction Problems. We find that variables whose degrees or domains are 1 have invalid revises which can be removed in the process. We demonstrate that these revises are redundant. We also provide an improved method to avoid the redundancy. The improved framework of the constraint problemsAC3 algorithms contain the ignorance of degree is 1, and domain is 1.The improved framework can be used on all of the coarse-grained arc consistency algorithms. The result of the test shows that we can save up to 65% revise times and 10% execution time after using the improved algorithms AC3 algorithms containing the ignorance of degree is 1, and domain is 1.

Copyright

© 2015, the Authors. Published by Atlantis Press.

Open Access

This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

TY  - CONF
AU  - Gang Yang
AU  - Huifeng Li
AU  - Can Cao
AU  - Siyuan Chen
AU  - Yubo Zhao
PY  - 2015/07
DA  - 2015/07
TI  - An Optimal Algorithm based on the Solution to the Coarse-Grained Arc Consistency Algorithms of the Constraint Satisfaction Problems
BT  - Proceedings of the 2015 International Conference on Computer Science and Intelligent Communication
PB  - Atlantis Press
SP  - 12
EP  - 17
SN  - 2352-538X
UR  - https://doi.org/10.2991/csic-15.2015.4
DO  - 10.2991/csic-15.2015.4
ID  - Yang2015/07
ER  -