inria-00291550, version 1
Réordonnancement de domaines dans les réseaux de contraintes
Christian Bessiere
1Thierry Petit 2Bruno Zanuttini 3
JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes (2008) 133-142
Résumé : Dans le but d'accélérer la résolution d'un CSP, nous nous intéressons au problème consistant à modifier l'ordre sur les valeurs qui est induit par la définition de chaque domaine. Nous discutons de l'intérêt de cette technique de reformulation et définissons les problèmes pertinents. Nous montrons qu'on peut trouver un ordre rendant un réseau de contraintes monotone (s'il en existe un) en temps polynomial, mais que le même problème est NP-difficile pour la classe des contraintes min-closes. Enfin, nous montrons en quoi nos résultats s'appliquent au maintien de diverses consistances aux bornes.
- 1 : Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier (LIRMM)
- CNRS : UMR5506 – Université Montpellier II - Sciences et Techniques du Languedoc
- 2 : Laboratoire d'Informatique de Nantes Atlantique (LINA)
- CNRS : UMR6241 – Université de Nantes – Ecole des Mines de Nantes
- 3 : Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen (GREYC)
- CNRS : UMR6072 – Université de Caen – Ecole Nationale Supérieure d'Ingénieurs de Caen
- Collaboration : Session 05 : CSP (Christophe Lecoutre)
- Domaine : Informatique/Langage de programmation
- inria-00291550, version 1
- http://hal.inria.fr/inria-00291550
- oai:hal.inria.fr:inria-00291550
- Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s
- Soumis le : Vendredi 27 Juin 2008, 13:35:03
- Dernière modification le : Vendredi 11 Juillet 2008, 18:18:39
Documents associés
Exporter