Sur la pertinence des décompositions arborescentes optimales pour la résolution de CSP
Résumé
La notion de décomposition arborescente est un sujet important pour l'étude et la résolution de problèmes NP-difficiles en intelligence artificielle, et notamment en programmation par contraintes. D'un point de vue théorique, son exploitation, dans le cadre général des modèles graphiques (réseaux bayésiens, CSP (pondérés),. . .), a conduit, sous certaines hypothèses, à la définition d'algorithmes de résolution polynomiaux. Par ailleurs, ces dernières années, des solveurs l'exploitant ont fait montre de leur intérêt pratique pour la résolution de problèmes de décision, d'optimisation ou de comptage. Dans cet article, nous nous intéressons aux décompo-sitions arborescentes optimales et à leur intérêt pratique pour la résolution d'instances CSP. La motivation de ce travail est double. D'une part, des progrès considérables ont été accomplis au niveau des méthodes calculant de telles décompositions, rendant envisageable leur exploitation pratique. D'autre part, la complexité temporelle des méthodes de résolution exploitant une décomposi-tion arborescente est directement liée à la largeur de la décomposition employée et donc employer une décom-position optimale permet théoriquement de minimiser cette complexité. Nous évaluons d'abord la capacité des méthodes calculant des décompositions optimales à dé-composer des instances CSP avant de mesurer l'apport de ces décompositions optimales au niveau de l'efficacité de la résolution. Ce papier est un résumé de [2]. 1 Contexte Une instance CSP (pour Problème de Satisfaction de Contraintes) est définie par la donnée d'un triplet (X, D, C), où X = {x 1 ,. .. , x n } est un ensemble de n * Ce travail est soutenu par l'Agence Nationale de la Recherche dans le cadre du projet DEMOGRAPH (ANR-16-C40-0028) variables, D = {d x1 ,. .. , d xn } est un ensemble de do-maines finis de taille au plus d, et C = {c 1 ,. .. , c e } est un ensemble de e contraintes. Chaque contrainte c i est un couple (S(c i), R(c i)), où S(c i) = {x i1 ,. .. , x i k } ⊆ X définit la portée de c i , et R(c i) ⊆ d xi 1 × · · · × d xi k est une relation de compatibilité. La structure d'une instance CSP est donnée par un hypergraphe, appelé hypergraphe de contraintes, dont les sommets correspondent aux variables et les arêtes aux portées des contraintes. Une affectation d'un sous-ensemble de X est dite cohérente si toutes les contraintes portant sur ce sous-ensemble sont satisfaites. Une solution est une affectation cohérente de toutes les variables. Déterminer si une instance CSP possède une solution est un problème NP-complet. Il en découle que les algorithmes de résolution habituellement em-ployés ont une complexité en O(exp(n)). Toutefois, certains algorithmes, comme BTD [3], sont capables de fournir de meilleures bornes de complexité tem-porelle en exploitant une décomposition arborescente [4] de l'hypergraphe de contraintes pour identifier des sous-problèmes indépendants. Définition 1 Une décomposition arborescente d'un graphe G = (X, C) est un couple (E, T) où T = (I, F) est un arbre (I est un ensemble de noeuds et F un ensemble d'arêtes) et E = {E i : i ∈ I} une famille de sous-ensembles de X, telle que chaque sous-ensemble (appelé cluster) E i est un noeud de T et vérifie : (i) ∪ i∈I E i = X, (ii) pour chaque arête {x, y} ∈ C, il existe i ∈ I avec {x, y} ⊆ E i , et (iii) pour tout i, j, k ∈ I, si k est sur un chemin de i à j dans T , alors E i ∩ E j ⊆ E k. La largeur d'une décomposition est égale à max i∈I |E i | − 1. La largeur arborescente dite tree-width w * de G est la largeur minimale pour toutes les décompositions arborescentes de G.
Domaines
Intelligence artificielle [cs.AI]
Origine : Fichiers produits par l'(les) auteur(s)
Loading...