Réseaux de contraintes : algorithmes de propagation et de décomposition / par Assef Chmeiss ; sous la direction de Philippe Jégou

Bibliogr. p. 97-100

Thèse de doctorat informatique 1996 Aix-Marseille 1

Nous nous intéressons aux problèmes de satisfaction de contraintes (CSP) binaires à domaines finis. Nous travaillons sur la micro-structure de CSP qui est définie par le graphe des relations de comptabilité entre paires de variable-valeur: ces paires constituent les sommets tandis que les arêtes sont définies par les paires compatibles. Dans la première partie de cette thèse, nous montrons comment cette micro-structure peut être simplifiée par des algorithmes de consistance partielle. Nous proposons ainsi trois algorithmes de propagation de contraintes par consistance de chemin. La complexité en temps du premier est optimale mais sa complexité en espace le rend peu utilisable (seulement pour des problèmes de petite taille). En relaxant la complexité en temps, nous établissons un algorithme efficace en pratique avec une complexité spatiale meilleure. Le troisième algorithme n'est, en effet, qu'une optimisation de la complexité en espace du deuxième. Dans la seconde partie nous nous intéressons à la résolution de CSP par décomposition de la micro-structure. Deux méthodes qui reposent sur les propriétés combinatoires et algorithmiques des graphes triangulés sont mises en oeuvre et expérimentées. D'autre part, nous proposons une méthode incomplète de résolution s'appuyant sur la recherche de graphes partiels triangulés. Enfin, dans la dernière partie, nous proposons une généralisation des graphes triangulés qui offre une classe des graphes possédant le même type de propriétés que celles des graphes triangulés