Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Communication Dans Un Congrès Année : 2005

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

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.
Fichier principal
Vignette du fichier
58.pdf (568.51 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)

Dates et versions

lirmm-00378944 , version 1 (11-10-2019)

Identifiants

  • HAL Id : lirmm-00378944 , version 1

Citer

Christian Bessiere, Romuald Debruyne. Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc. JFPC 2005 - 1res Journées Francophones de Programmation par Contraintes, CRIL - CNRS FRE 2499, Jun 2005, Lens, France. pp.277-286. ⟨lirmm-00378944⟩
447 Consultations
125 Téléchargements

Partager

More