Lazy arc consistency - INRAE - Institut national de recherche pour l’agriculture, l’alimentation et l’environnement Accéder directement au contenu
Communication Dans Un Congrès Année : 1996

Lazy arc consistency

Résumé

Arc consistency filtering is widely used in the framework of binary constraint satisfaction problems : with a low complexity, inconsistencymay be detected and domains are filtered. In this paper, we show that when detecting inconsistency is the objective, a systematic domain filtering is useless and a lazy approach is more adequate. Whereas usual arc consistency algorithms produce the maximum arc consistent sub-domain, when it exists, we propose a method, called LAC_7, which only looks for any arc consistent sub-domain. The algorithm is then extended to provide the additional service of locating one variable with a minimum domain cardinality in the maximum arc consistent sub-domain, without necessarily computing all domain sizes. Finally, we compare traditional AC enforcing and lazy AC enforcing using several benchmark problems, both randomly generated CSP and real life problems.
Fichier non déposé

Dates et versions

hal-02771457 , version 1 (04-06-2020)

Identifiants

  • HAL Id : hal-02771457 , version 1
  • PRODINRA : 136085

Citer

Thomas Schiex, J.C. Régin, Christine Gaspin, G. Verfaillie. Lazy arc consistency. National American Conference on Artificial Intelligent, 1996, Portland, United States. ⟨hal-02771457⟩
8 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More