Un schéma générique d'algorithmes énumératifs avec (no)good recording pour la résolution bornée de CSP

Samba Ndiaye 1 Cyril Terrioux 1
1 LSIS - Laboratoire des Sciences de l'Information et des Systèmes
Résumé : Ce papier présente un schéma générique d'algorithmes énumératifs pour la résolution de CSP. Ce schéma exploite des propriétés sémantiques et topologiques du réseau de contraintes afin de produire des goods et des nogoods. Il repose sur un ensemble de séparateurs du graphe de contraintes et plusieurs fonctions et procédures paramétrables de sorte à exploiter des heuristiques, des méthodes de filtrage, des techniques de retour en arrière intelligent, d'enregistrement de nogoods classiques ou de (no)goods structurels et des bornes de complexité théorique héritées des méthodes basées sur les décompositions de graphes. Selon les choix effectués, nous obtenons une famille d'algorithmes dont la complexité en temps est comprise entre $O(exp(w+1))$ et $O(exp(n))$ avec $w$ la largeur d'arbre du graphe de contraintes et $n$ le nombre de variables.
Type de document :
Communication dans un congrès
Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07
Liste complète des métadonnées

Littérature citée [21 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00151213
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:04:21
Dernière modification le : jeudi 15 mars 2018 - 16:56:06
Document(s) archivé(s) le : jeudi 8 avril 2010 - 18:44:15

Fichier

16.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00151213, version 1

Collections

JFPC07 | LSIS | UNIV-AMU | UNIV-TLN | LIS-LAB

Citation

Samba Ndiaye, Cyril Terrioux. Un schéma générique d'algorithmes énumératifs avec (no)good recording pour la résolution bornée de CSP. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151213〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

145

Téléchargements de fichiers

66

Contact


archive-ouverte@inria.fr