L'algorithme « Optimal Distributed Intelligent BackTracking »
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.
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.
problèmes de satisfaction de contraintes distribués (DCSP), IA Distribué.
Distributed Constraint Satisfaction Problems, Distributed AI.
Français
|
