Abstract FR:

Les problèmes de satisfaction de contraintes (CSP) constituent un cadre de formalisation puissant des problèmes d'Intelligence Artificielle. De nombreuses méthodes ont été définies pour les résoudre. Les travaux présentés dans cette thèse s'intéressent aux méthodes complètes, i. E. Qui permettent toujours de trouver une solution. Les plus performantes méthodes complètes de résolution de CSP utilisent un mécanisme de recherche de type forward-checking. Afin d'améliorer l'efficacité des algorithmes de résolution, de diverses techniques de filtrage ont été proposées, appliquées avant et / ou pendant la recherche. Cependant, les contraintes n-aires ont été peu étudiées. Nous proposons un solveur non-binaire composé d'une famille d'algorithmes résolution de type Forward Checking n-aire (nFC) et une famille d'algorithmes d'arc-consistance n-aire (nAC) qui comporte plusieurs versions. Comme la résolution séquentielle des CSP n-aires peut s'avérer coûteuse (probèmes NP-complets), le parallélisme permet de réduire le temps de calcul. Pour cela, nous exploitons essentiellement une méthode de parallélisation en mémoire partagée, basée sur la division de l'arbre de recherche en utilisant OpenMP. Nous appliquons et spécialisons les algorithmes proposés pour la résolution de problèmes académiques et de problèmes aléatoires non-binaires, ainsi que pour la résolution du problème du car-sequencing dans une formulation de CSP n-aire.