Skip to Main content Skip to Navigation
Conference papers

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).
Document type :
Conference papers
Complete list of metadata

Cited literature [5 references]  Display  Hide  Download

https://hal.inria.fr/inria-00151220
Contributor : Sylvain Soliman <>
Submitted on : Friday, June 1, 2007 - 6:13:01 PM
Last modification on : Thursday, January 21, 2021 - 10:54:03 PM
Long-term archiving on: : Thursday, April 8, 2010 - 5:06:30 PM

File

49.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00151220, version 1

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. ⟨inria-00151220⟩

Share

Metrics

Record views

129

Files downloads

108