Probl?es de Satisfaction de Contraintes

Dans le cadre des TICSP (Probl?me de Satisfaction de Contraintes pour l'alg?bre d'Intervalles de Temps), nous avons propos? une am?lioration de l'algorithme d'Allen. A partir de la composition d'Allen, nous avons propos? une composition entre 4 noeuds. Puis, sur la base de cette composition, nous avons d?velopp? un algorithme incr?mental pour la 4- coh?rence ramenant la complexit? ? l'ordre O(n3). En utilisant la g?n?ralisation de la composition entre 4 noeuds ? la composition entre k noeuds, nous avons propos? un algorithme de k-coh?rence avec une complexit? temporelle en O(nk-1). Le passage des Probl?mes de Satisfaction de Contraintes (CSP) aux Probl?mes de Satisfaction de Contraintes Distribu?s (DCSP) pose le probl?me du passage de l'individuel au collectif. Ce passage a fait l'objet de diverses extensions du cadre CSP ? des DCSP. Dans ce cadre et ? partir de l'algorithme Intelligent BackTracking Distribu? (DIBT), nous avons propos? une G?n?ralisation Optimale en envoi de messages (OGDIBT). DIBT n'?tant pas complet. Dans ce m?moire, une ?tude de la compl?tude d'OGDIBT est propos?e et une version compl?te y est donn?e.

Author: Belaissaoui-M

Publisher: Omniscriptum

Publication Date: Feb 28, 2018

Number of Pages: 164 pages

Binding: Paperback or Softback

ISBN-10: 6131548633

ISBN-13: 9786131548635