Abstract FR:

Les problèmes de satisfaction de contraintes (CSP) constituent un cadre de formalisation puissant des problèmes d'intelligence artificielle. Un CSP est la donnée d'un ensemble de variables définies sur certains domaines, et d'un ensemble de contraintes reliant ces variables. De nombreuses méthodes ont été définies pour les résoudre. Nous nous intéressons dans ce document, aux méthodes complètes, i. E. Qui permettent toujours de trouver une solution. Les méthodes complètes de résolution les plus performantes pour les csp utilisent un mécanisme de recherche par vérification de consistance "en avant", c-à-d. En filtrant les valeurs incompatibles dans les domaines non instancies lorsqu'une nouvelle instanciation est testée (forward-checking). Cependant, ces méthodes ne sont définies que pour des contraintes binaires. Nous étendons ces méthodes en définissant une notion de consistance n-aire généralisée : la relationnelle-(I,J)-consistance. Nos expérimentation montrent que la résolution n-aire directe est plus rapide que la résolution sur un CSP binaire obtenu apres transformation. Comme la recherche séquentielle est particulièrement couteuse (NP-complete), le parallélisme permet de réduire le temps de calcul. Pour cela, nous definissons un algorithme générique qui permet d'hybrider aussi bien les différentes techniques de recherche séquentielles que les méthodes de parallélisation. Le principe de la recherche reprend le schéma " OU-parallèle". Si la plupart des techniques parallèles classiques restent utilisables pour les CSP, nous définissons différentes techniques destinées à mieux s'adapter aux spécificités des CSP. Ainsi, nous proposons une méthode de répartition initiale de charge, une méthode de division adaptée à la taille des contextes de recherche et une fonction de détermination de la divisibilité d'une tâche. Nous appliquons et spécialisons les algorithmes définis pour la résolution de problèmes de bordereau de coupe en confection, i. E. Le placement de formes quelconques sur une surface restreinte.