Skip to Main content Skip to Navigation
Conference papers

Une étude des supports résiduels pour la consistance d'arc

Résumé : Pour un algorithme établissant la consistance d'arc (AC), un support résiduel, ou résidu, est un support qui a été trouvé et enregistré lors d'une exécution de la procédure qui détermine si une valeur est supportée par une contrainte. Le point important est qu'un résidu n'offre pas la garantie de représenter un minorant du plus petit support courant de la valeur en question. Dans cet article, nous étudions l'impact théorique d'exploiter des résidus au niveau de l'algorithme élémentaire AC3. Tout d'abord, nous prouvons que AC3r(m) (i.e. AC3 exploitant des résidus) est optimal pour une dureté de contrainte faible ou élevée. Ensuite, nous montrons que MAC2001 présente, par rapport à MAC3r(m), un sur-coût en O(μed) par branche de l'arbre binaire construit par MAC, avec μ représentant le nombre de réfutations de la branche, e le nombre de contraintes et d la taille du plus grand domaine. L'une des conséquences est que, MAC3r(m) admet une complexité temporelle (dans le pire des cas) meilleure que MAC2001 pour une branche impliquant μ réfutations lorsque μ > d2 ou lorsque μ > d et que la dureté de chaque contrainte est soit faible soit élevée. Nos résultats expérimentaux montrent clairement que le fait d'exploiter des résidus permet d'améliorer l'efficacité des algorithmes MAC et SAC embarquant des algorithmes AC à gros grain.
Complete list of metadata

Cited literature [14 references]  Display  Hide  Download

https://hal.inria.fr/inria-00085771
Contributor : Laurent Henocque <>
Submitted on : Friday, July 14, 2006 - 8:56:06 AM
Last modification on : Thursday, January 11, 2018 - 6:19:28 AM
Long-term archiving on: : Tuesday, April 6, 2010 - 12:07:51 AM

File

Identifiers

  • HAL Id : inria-00085771, version 1

Collections

Citation

Christophe Lecoutre, Fred Hemery. Une étude des supports résiduels pour la consistance d'arc. Journées Francophones de Programmation par Contraintes, 2006, Nîmes - Ecole des Mines d'Alès. ⟨inria-00085771⟩

Share

Metrics

Record views

140

Files downloads

185