Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2005

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

Abstract

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
Origin Files produced by the author(s)

Dates and versions

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

Identifiers

  • HAL Id : lirmm-00378944 , version 1

Cite

Christian Bessiere, Romuald Debruyne. Algorithmes Optimaux et Sous-optimaux de Singleton Consistance d'Arc. 1ères Journées Francophones de Programmation par Contraintes (JFPC 2005), CRIL - CNRS FRE 2499, Jun 2005, Lens, France. pp.277-286. ⟨lirmm-00378944⟩
425 View
69 Download

Share

More