Sur la complexité des algorithmes de backtracking et quelques nouvelles classes polynomiales pour CSP

Achref El Mouelhi 1 Philippe Jégou 1 Cyril Terrioux 1 Bruno Zanuttini 2
2 Equipe MAD - Laboratoire GREYC - UMR6072
GREYC - Groupe de Recherche en Informatique, Image, Automatique et Instrumentation de Caen
Résumé : L'étude des classes polynomiales, pour les problèmes de satisfaction de contraintes (CSP), constitue depuis longtemps un domaine de recherche important qui s'avère aujourd'hui très actif. Cependant, les travaux réalisés jusqu'à présent se sont révélés pour l'essentiel théoriques. En effet, ils se cantonnent en général à la définition de classes d'instances pour lesquelles des algorithmes polynomiaux ad hoc, à la fois pour la reconnaissance et pour la résolution, sont proposes. Ces algorithmes ne peuvent être, en fait, utilisés que pour le traitement d'une classe d'instances donnée. Ils s'avèrent ainsi difficilement exploitables en pratique, et ne sont donc pas exploités au sein de solveurs généraux. L'intérêt pratique des classes polynomiales est ainsi très limitée. Dans cet article, nous abordons la question des classes polynomiales CSP d'un point de vue différent de l'approche classique, en nous intéressant aux algorithmes que l'on peut retrouver dans les systèmes de résolution opérationnels. Pour cela, nous _étudions d'abord la complexité d'algorithmes génériques de résolution de CSP tels que le Forward-Checking par exemple. Cette étude s'appuie sur l'exploitation d'un paramètre issu de la théorie des graphes, et qui permet de proposer de nouvelles bornes de complexité. La mise en relation de ces nouvelles bornes avec certains résultats issus de la théorie des graphes nous permet d'exhiber de nouvelles classes polynomiales. De cette façon, nous montrons comment des algorithmes classiques de résolution de CSP peuvent traiter efficacement en pratique ainsi qu'en théorie, des instances de CSP, sans devoir reconnaître au préalable leur appartenance à d'éventuelles classes polynomiales.
Type de document :
Communication dans un congrès
Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes
Liste complète des métadonnées

Littérature citée [18 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00830458
Contributeur : Ist Inria Saclay <>
Soumis le : mercredi 5 juin 2013 - 10:31:00
Dernière modification le : mardi 5 juin 2018 - 10:14:42
Document(s) archivé(s) le : mardi 4 avril 2017 - 17:06:10

Fichier

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

Identifiants

  • HAL Id : hal-00830458, version 1

Citation

Achref El Mouelhi, Philippe Jégou, Cyril Terrioux, Bruno Zanuttini. Sur la complexité des algorithmes de backtracking et quelques nouvelles classes polynomiales pour CSP. Simon de Givry. Huitièmes Journées Francophones de Programmation par Contraintes - JFPC 2012, May 2012, Toulouse, France. 2012, Actes des Huitièmes Journées Francophones de Programmation par Contraintes. 〈hal-00830458〉

Partager

Métriques

Consultations de la notice

523

Téléchargements de fichiers

381