L' élargissement aléatoire progressif

Résumé : Nous présentons un algorithme qui permet de résoudre efficacement les problèmes de complétion de quasi-groupes. Il se greffe sur un algorithme de Forward- Checking. Il élargit progressivement le nombre de valeurs à explorer. Pour un nombre donné de valeurs à explorer, et pour chaque variable, il choisit aléatoirement entre le nombre de valeurs à explorer et ce nombre moins un. La probabilité de choisir le nombre de valeurs à explorer est elle aussi augmentée progressivement. Sur 9900 problèmes de complétion de quasi-groupes d'ordre 20 et pour une bonne heuristique d'ordonnancement des valeurs utilisant une modélisation duale, notre algorithme donne de meilleurs résultats que le Forward-Checking, que les recommencements rapides aléatoires (Rapid Randomized Restarts), que l'élargissement itératif (Iterative Broadening) et que la recherche avec déviations limitées (Limited Discrepancy Search).
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 [5 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00151220
Contributeur : Sylvain Soliman <>
Soumis le : vendredi 1 juin 2007 - 18:13:01
Dernière modification le : mardi 22 mai 2018 - 20:40:06
Document(s) archivé(s) le : jeudi 8 avril 2010 - 17:06:30

Fichier

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

Identifiants

  • HAL Id : inria-00151220, version 1

Collections

Citation

Tristan Cazenave. L' élargissement aléatoire progressif. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France, 2007, JFPC07. 〈inria-00151220〉

Partager

Métriques

Consultations de la notice

91

Téléchargements de fichiers

81