Skip to Main content Skip to Navigation
Conference papers

Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc

Christian Bessière 1 Romuald Debruyne 2
1 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Résumé : La singleton consistance d'arc (SAC) permet de filtrer bien plus que la consistance d'arc en s'assurant qu'aucune affectation ne puisse rendre le réseau de contraintes arc inconsistant. Des algorithmes ont été proposés pour réaliser la fermeture par singleton consistance d'arc mais avec des complexités temporelles clairement non optimales. Dans cet article, nous donnons une borne inférieure de la complexité temporelle dans le pire des cas des algorithmes de singleton consistance d'arc. Nous proposons un algorithme possédant cette borne pour complexité temporelle. Cet algorithme optimal est cependant coûteux en espace. C'est pourquoi nous proposons également un algorithme troquant l'optimalité temporelle pour une meilleure complexité spatiale. Bien que non optimal, ce dernier possède une complexité temporelle dans le pire des cas inférieure à celle de tous les algorithmes de singleton consistance d'arc déjà publiés. Une étude expérimentale met en valeur les bonnes performances des algorithmes proposés.
Complete list of metadatas

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00378944
Contributor : Isabelle Gouat <>
Submitted on : Friday, October 11, 2019 - 2:02:51 PM
Last modification on : Thursday, May 14, 2020 - 6:58:06 PM

File

58.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : lirmm-00378944, version 1

Citation

Christian Bessière, Romuald Debruyne. Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc. JFPC: Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, France. pp.277-286. ⟨lirmm-00378944⟩

Share

Metrics

Record views

260

Files downloads

16