Hybridation de prouveurs CSP et apprentissage

Résumé : À ce jour, l'algorithme MGAC-$dom/wdeg$, qui maintient l'Arc Consistance Généralisée pendant la recherche d'une solution, est considéré comme étant l'approche générique la plus efficace pour résoudre des Problèmes de Satisfaction de Contraintes (CSP) difficiles et de grande taille. Dans cet article, nous proposons une approche hybride capable de combiner des recherches systématiques et locales indépendantes tout en transférant des informations utiles d'un algorithme à l'autre. Nous proposons différentes interactions, et en particulier l'apprentissage de nogoods, la pondération de contraintes ainsi que des affectations gloutonnes. Sur un grand nombre d'instances de CSP structurés, les résultats expérimentaux montrent que notre approche donne des résultats intéressants en comparaison avec MGAC-$dom/wdeg$.
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-00151161
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 16:52:51
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : jeudi 8 avril 2010 - 17:18:34

Fichier

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

Identifiants

  • HAL Id : inria-00151161, version 1

Collections

Citation

Julien Vion. Hybridation de prouveurs CSP et apprentissage. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151161〉

Partager

Métriques

Consultations de la notice

127

Téléchargements de fichiers

135