Abstract FR:

Cette thèse traite de la recherche arborescente parallèle pour résoudre les problèmes de satisfaction de contraintes (CSP), notamment des changements qu'elle produit naturellement sur l'ordre de visite des noeuds de l'arbre de recherche par rapport à sa version séquentielle. Dans les cas où ces changements s'avèrent préjudiciables en terme de temps de résolution, on donne des moyens de rétablir, au moins partiellement, l'ordre originel de visite des feuilles. Lorsque ces changements sont profitables, on propose de les appliquer directement à la recherche séquentielle. Après avoir rapidement rappelé quelques notions utiles sur les CSP (chapitre 1) et le parallélisme (chapitre 2), nous présentons un algorithme parallèle destiné à trouver toutes les solutions d'un CSP (chapitre 3). Puis la recherche d'une seule solution ou de la meilleure est abordée en étudiant notamment les conditions qui font qu'une recherche parallèle puisse conduire à une accélération superlinéaire ou sublinéaire (chapitre 4). Enfin nous traitons de la transformation des algorithmes d'optimisation séquentiels en algorithmes parallèles de facon plus générale, en l'illustrant par l'intégration du parallélisme dans une bibliothèque générique de classes C++ destinées à la modélisation et la résolution de problèmes d'optimisation. Dans la deuxième partie, nous exploitons le phénomène d'accélération superlinéaire pour traiter des possibles améliorations de parcours d'arbre par rapport au Backtrack chronologique. Nous présentons un algorithme séquentiel récent basé sur le phénomène de superlinéarité étudié dans le chapitre 4 ainsi que d'autres méthodes de recherche arborescente apparues ces dernières années. Leur point commun est de parcourir les noeuds de l'arbre de recherche dans un ordre différent de celui de la recherche classique en profondeur d'abord. Toutes ces méthodes sont comparées entre elles suivant la pertinence de l'ordre de visite des feuilles de l'arbre qu'elles suivent (chapitre 6). Finalement, nous proposons toute une série d'algorithmes qui sont des variations des algorithmes présentés dans le chapitre précédent. Ils exploitent les caractéristiques des CSP pour améliorer encore l'ordre de visite des feuilles ou diminuer le nombre de noeuds générés.