DisCSP
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Cet article ne cite pas suffisamment ses sources ().
Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».
En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?
DisCSP est l'acronyme anglais pour DIStributed Constraint Satisfaction Problem. Il s'agit de la résolution de problème de satisfaction de contraintes distribué sur un réseau de machines[1]. Cette approche de résolution de problèmes est associée aux systèmes multi-agents. Chaque machine est représentée par un agent qui communique de manière asynchrone avec les autres afin de résoudre le problème. Le domaine est fortement lié à celui de l'optimisation combinatoire sous contraintes distribuées.
Le problème est distribué sur un ensemble d'agents qui sont responsables soit d'un ensemble de variables, soit d'un ensemble de contraintes, et qui communiquent entre eux. Il est résolu par des variantes des algorithmes permettant de résoudre les problèmes de satisfaction de contraintes, comme les algorithmes de backtracking adapté au contexte distribué, comme l'algorithme ABT (Asynchronous Backtracking)[2], ou des algorithmes de synchrones. Les étapes peuvent rester identiques aux algorithmes de résolution de problèmes classique, la propagation de contraintes, le retour sur trace non chronologique (backjumping)...
Articles connexes[modifier | modifier le code]
Notes et références[modifier | modifier le code]
- (en) Boi Faltings, Francesca Rossi, Peter Van Beek et Toby Walsh, « Distributed constraint programming », dans Handbook of constraint programming, Elsevier, (ISBN 978-0-444-52726-4), p. 701
- M. Yokoo, E. H. Durfee, T. Ishida et K. Kuwabara, « Distributed Constraint Satisfaction for Formalizing Distributed Problem Solving », Proceedings of the 12th ICDCS,, , p. 614-621
