Maintien asynchrone de la consistance d'arc dans la recherche distribuée synchrone - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier
Conference Papers Year : 2013

Maintien asynchrone de la consistance d'arc dans la recherche distribuée synchrone

Abstract

Nous avons proposé récemment Nogood-Based Asynchronous Forward Checking (AFC-ng), un algo-rithme efficace et robuste pour résoudre des Problèmes de Satisfaction de Contraintes Distribués (DisCSPs). AFC-ng exécute de manière asynchrone une phase de vérification en avant pendant la recherche synchrone. Dans ce papier, nous proposons deux nouveaux algorithmes basés sur le même mécanisme qu'AFC-ng. Cependant, au lieu d'utiliser le forward checking comme propriété de filtrage, nous proposons de maintenir d'une manière asynchrone la consistance d'arc (MACA). Le premier algorithme que nous proposons, MACA-del, maintient la consistance d'arc grâce à un type de messages supplé-mentaire, des messages de suppression. Le deuxième algorithme, MACA-not, réalise la consistance d'arc sans aucun nouveau type de message. Nous fournissons une analyse théorique et uneévaluation expérimentale de l'approche proposée. Nos expérimentations montrent la bonne performance des algorithmes MACA et plus particulièrement ceux de MACA-not.
Fichier principal
Vignette du fichier
papier_18.pdf (409.79 Ko) Télécharger le fichier
Origin Files produced by the author(s)
Loading...

Dates and versions

lirmm-00830408 , version 1 (10-10-2019)

Identifiers

  • HAL Id : lirmm-00830408 , version 1

Cite

Mohamed Wahbi, Redouane Ezzahir, Christian Bessiere, El Houssine Bouyakhf. Maintien asynchrone de la consistance d'arc dans la recherche distribuée synchrone. 9èmes Journées Francophones de Programmation par Contraintes (JFPC 2013), Jun 2013, Aix-en-Provence, France. ⟨lirmm-00830408⟩
298 View
61 Download

Share

More