Propagation de Contraintes et Listes Tabou pour le CSP

Mohammad Dib 1 Alexandre Caminada 1 Hakim Mabed 1
1 SET - Laboratoire Systèmes et Transports
Résumé : Dans ce papier nous nous intéressons à la gestion de l'arbre de décision dans un algorithme hybride pour le CSP. Nous proposons une méthode déterministe qui permet de gérer dynamiquement des coupes dans l'arbre de recherche et l'accès aux variables de décision. Les deux principes sont basés sur la découverte et la mémorisation des associations variables/valeurs qui conduisent à des solutions infaisables. Il s'agit donc d'un système d'apprentissage qui enrichit la connaissance de l'algorithme sur le problème et augmente son efficacité au fur et à mesure de sa progression. Nous avons testé la méthode sur les benchmarks d'affectation de fréquences GRAPH et CELAR. Les premiers résultats obtenus sont au niveau des meilleurs connus actuellement sur les problèmes Min-SPAN et améliorent sensiblement les pourcentages de réussite.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.409-413, 2008
Liste complète des métadonnées

Littérature citée [27 références]  Voir  Masquer  Télécharger
https://hal.inria.fr/inria-00293730
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : lundi 7 juillet 2008 - 14:37:08
Dernière modification le : mercredi 29 novembre 2017 - 14:34:43
Document(s) archivé(s) le : vendredi 28 mai 2010 - 23:13:24

Fichier

pages-409-413-article33.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00293730, version 1

Collections

JFPC08 | UNIV-BM | UNIV-BM-THESE

Citation

Mohammad Dib, Alexandre Caminada, Hakim Mabed. Propagation de Contraintes et Listes Tabou pour le CSP. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.409-413, 2008. 〈inria-00293730〉

Exporter

BibTeX TEI DC DCterms EndNote

Partager

Métriques

Consultations de la notice

147

Téléchargements de fichiers

341

Contact


archive-ouverte@inria.fr