Réseaux de contraintes: algorithmes de propagation et de décomposition / par Assef Chmeiss

Auteur: Chmeiss, Assef - AuteurAuteur secondaire : Jégou, Philippe - Directeur de thèseCollectivité secondaire: Université de Provence - Etablissement de soutenanceType de document: ThèseLangue: françaisPays: FranceÉditeur: [S.l.] : [s.n.], 1996Description: 1 vol. (100 p.) : fig. ; 30 cmRésumé: 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.Bibliographie: Bibliogr. p. 97-100.Thèse: Thèse de doctorat en informatique, soutenue en 1996, organisme : Aix-Marseille 1 Sujets MSC: 68T20 Computer science -- Artificial intelligence -- Problem solving (heuristics, search strategies, etc.)
68Q25 Computer science -- Theory of computing -- Analysis of algorithms and problem complexity
68R10 Computer science -- Discrete mathematics in relation to computer science -- Graph theory (including graph drawing)
05C85 Combinatorics -- Graph theory -- Graph algorithms
97A70 Mathematics education - General, mathematics and education -- Theses and postdoctoral theses
Location Call Number Status Date Due
Salle S 00753-01 / Thèses CHM (Browse Shelf) Available

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

There are no comments for this item.

Log in to your account to post a comment.
Languages: English | Français | |