A Greedy Approach to Establish Singleton Arc Consistency
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 199-203.
Abstract
In this paper, we propose a new approach to establish Singleton Arc Consistency (SAC) on constraint networks. While the principle of existing SAC algorithms involves performing a breadth-first search up to a depth equal to 1, the principle of the two algorithms introduced in this paper involves performing several runs of a greedy search (where at each step, arc consistency is maintained). It is then an original illustration of applying inference (i.e. establishing singleton arc consistency) by search. Using a greedy search allows benefiting from the incrementality of arc consistency, learning relevant information from conflicts and, potentially finding solution(s) during the inference process. Furthermore, both space and time complexities are quite competitive.
@inproceedings{ijcai2005p119,
title = {A Greedy Approach to Establish Singleton Arc Consistency},
author = {Lecoutre, Christophe and Cardon, Stéphane},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
pages = {199--203},
year = {2005},
url = {https://ijcai.org/proceedings/2005/119},
}
TY - CPAPER TI - A Greedy Approach to Establish Singleton Arc Consistency AU - Lecoutre, Christophe AU - Cardon, Stéphane T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 199 EP - 203 UR - https://ijcai.org/proceedings/2005/119 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
