Voisinage consistant pour le problème de satisfaisabilité - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2007

Voisinage consistant pour le problème de satisfaisabilité

Résumé

La plupart des méthodes de recherche locale pour le problème de satisfaisabilité traitent une interprétation complète et souvent inconsistante des variables du problème, et essaient de la réparer en changeant la valeur de vérité de certaines variables jusqu'à atteindre une solution. Nous proposons une nouvelle méthode de recherche locale qui gère des interprétations incomplètes, mais toujours consistantes, au lieu de complètes et inconsistantes. Cette méthode tente de prolonger l'interprétation partielle courante comme le ferait une méthode complète. Cependant, au lieu de déclencher un retour arrière (backtrack) lorsqu'un conflit sur vient, elle libère au moins une variable impliqué dans chaque clause falsifiée a in de restaurer la consistance. Ainsi, le voisinage exploré est toujours consistant alors que ce n'est pas le cas pour les algorithmes de recherche locale classiques. Notre méthode peut aussi tirer profit de certaines techniques efficaces issues des méthodes complètes comme la propagation unitaire et les heuristiques de choix de variables. Les résultats expérimentaux montrent la compétitivité de notre méthode par rapport à d'autres méthodes de recherche locale.
Fichier principal
Vignette du fichier
47.pdf (135.77 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

inria-00151061 , version 1 (01-06-2007)

Identifiants

  • HAL Id : inria-00151061 , version 1

Citer

Lionel Paris, Djamal Habet, Belaïd Benhamou. Voisinage consistant pour le problème de satisfaisabilité. Troisièmes Journées Francophones de Programmationpar Contraintes (JFPC07), Jun 2007, INRIA, Domaine de Voluceau, Rocquencourt, Yvelines France. ⟨inria-00151061⟩
63 Consultations
79 Téléchargements

Partager

Gmail Facebook X LinkedIn More