Un modèle markovien pour GSAT et WalkSAT résultats préliminaires

Charlotte Truchet 1 Damien Noguès 1, 2 Narendra Jussien 3
3 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Résumé : Les algorithmes GSAT et WalkSAT ont un comportement, bien connu expérimentalement, mais relativement peu étudié théoriquement. Nous étudions ici un modèle de GSAT et WalkSAT sous la forme de chaînes de Markov, modèle exact pour la partie gloutonne, approché pour la version avec random restart. Les résultats classiques sur les chaînes de Markov permettent d'en déduire deux nouvelles majorations de l'espérance du temps de calcul de WalkSAT sans random restart, en fonction des valeurs propres de la matrice de transition associée. Nous montrons expérimentalement sur de petites instances que cette borne permet de retrouver le paramétrage optimal observé dans la littérature. Nous donnons ensuite deux résultats sur l'espérance de GSAT ou Walk-SAT avec random restart en fonction du nombre d'itérations avant random restart (entre autres). Même si les résultats restent à approfondir, ce modèle donne une piste vers une étude théorique du paramétrage optimal et, au delà, du comportement de ces algorithmes.
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.327-336, 2008
Liste complète des métadonnées

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

https://hal.inria.fr/inria-00292691
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : mercredi 2 juillet 2008 - 14:13:39
Dernière modification le : lundi 16 juillet 2018 - 11:06:02
Document(s) archivé(s) le : vendredi 28 mai 2010 - 23:05:34

Fichier

pages-327-336-article50.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00292691, version 1

Citation

Charlotte Truchet, Damien Noguès, Narendra Jussien. Un modèle markovien pour GSAT et WalkSAT résultats préliminaires. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.327-336, 2008. 〈inria-00292691〉

Partager

Métriques

Consultations de la notice

297

Téléchargements de fichiers

135