Proceedings of the 2015 International Conference on Computer Science and Intelligent Communication

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

Authors
Gang Yang, Huifeng Li, Can Cao, Siyuan Chen, Yubo Zhao
Corresponding Author
Gang Yang
Available Online July 2015.
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)

Volume Title
Proceedings of the 2015 International Conference on Computer Science and Intelligent Communication
Series
Advances in Computer Science Research
Publication Date
July 2015
ISBN
978-94-62520-84-4
ISSN
2352-538X
DOI
10.2991/csic-15.2015.4How to use a DOI?
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/).

Cite this article

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  -