Recherche dirigée par le dernier conflit

Résumé : Dans ce papier, nous proposons une nouvelle approche pour guider la recherche vers la source des conflits. Son principe est le suivant : après chaque conflit, la dernière variable assignée est sélectionnée en priorité tant que le réseau de contraintes est inconsistant. Ceci permet de découvrir la variable coupable la plus récente (i.e. à l'origine de l'échec) en remontant la branche courante de la feuille vers la racine de l'arbre de recherche. Autrement dit, l'heuristique de choix de variables est violée jusqu'au moment où un retour-arrière sur la variable coupable est effectué et que l'on découvre une valeur singleton consistante. En conséquence, ce type de raisonnement, qui représente un moyen original d'éviter le thrashing, peut facilement être intégré à de nombreux algorithmes de recherche. Les expérimentations effectuées sur un large éventail d'instances démontrent l'efficacité de cette approche.
Type de document :
Communication dans un congrès
Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00085790
Contributeur : Laurent Henocque <>
Soumis le : vendredi 14 juillet 2006 - 10:55:08
Dernière modification le : jeudi 11 janvier 2018 - 06:19:28
Document(s) archivé(s) le : mardi 6 avril 2010 - 00:08:58

Fichier

Identifiants

  • HAL Id : inria-00085790, version 1

Collections

Citation

Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary, Vincent Vidal. Recherche dirigée par le dernier conflit. Deuxièmes Journées Francophones de Programmation par Contraintes (JFPC06), 2006, Nîmes - Ecole des Mines d'Alès / France, 2006. 〈inria-00085790〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

75