ACCUEIL

Consignes aux
auteurs et coordonnateurs
Nos règles d'éthique
Auteurs : soumettez
votre article en ligne
Autres revues >>

Technique et Science Informatiques

0752-4072
Revue des sciences et technologies de l'information
 

 ARTICLE VOL 22/RSTI1 - 2003  - pp.303-306
TITRE
L'algorithme « Optimal Distributed Intelligent BackTracking »

RÉSUMÉ
La recherche dans les DCSP est historiquement partagée en deux classes distinctes de méthodes. La première consiste à la recherche d’une solution en utilisant la méthode de Backtrack. La deuxième est la consistance locale, en particulier la consistance d’arc [Ham 99]. Dans ce cadre et à partir de l’algorithme Intelligent BackTracking Distribué (DIBT) [Ham 99], nous avons proposé une Généralisation Optimale en envoi de messages (OGDIBT) [Bel 01a], [Bel 02]. Malheureusement, DIBT n’est pas complet [Bes 01, Yok 00]. Ce papier tente d’étudier la complétude de OGDIBT en proposant une version complète.

ABSTRACT
Research in DCSP has historically focused on two distinct classes of methods. One paradigm has been that of Backtrack search, which presents algorithms for finding a solution in DCSP. The second paradigm has been Local consistency of constraint network, in particular the arc-consistency [Ham 99]. In the setting of the DCSP and from the algorithm DIBT (Distributed Intelligent BackTracking) [Ham 99], we developed an Optimal Generalization algorithm OGDIBT [Bel 01a], [Bel 02]. Our method is optimal according to the number of message passing operations. Unfortunately, DIBT has been shown incomplete [Bes 01, Yok 00]. This paper presents a news version of OGDIBT. It ensures the completeness of search.

AUTEUR(S)


MOTS-CLÉS
problèmes de satisfaction de contraintes distribués (DCSP), IA Distribué.

KEYWORDS
Distributed Constraint Satisfaction Problems, Distributed AI.

LANGUE DE L'ARTICLE
Français

 PRIX
• Abonné (hors accès direct) : 12.5 €
• Non abonné : 25.0 €
|
|
--> Tous les articles sont dans un format PDF protégé par tatouage 
   
ACCÉDER A L'ARTICLE COMPLET  (133 Ko)



Mot de passe oublié ?

ABONNEZ-VOUS !

CONTACTS
Comité de
rédaction
Conditions
générales de vente

 English version >> 
Lavoisier