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.
Type de document :
Communication dans un congrès
Christine Solnon. Premières Journées Francophones de Programmation par Contraintes, Jun 2005, Lens, France, pp.277-286, 2005
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00378944
Contributeur : Isabelle Gouat <>
Soumis le : lundi 27 avril 2009 - 13:14:49
Dernière modification le : mardi 4 décembre 2018 - 01:21:40

Identifiants

  • HAL Id : lirmm-00378944, version 1

Citation

Christian Bessière, Romuald Debruyne. Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc. Christine Solnon. Premières Journées Francophones de Programmation par Contraintes, Jun 2005, Lens, France, pp.277-286, 2005. 〈lirmm-00378944〉

Partager

Métriques

Consultations de la notice

160