Comptage de solutions en exploitant la structure du graphe de contraintes

International audienceCe papier traite du probl eme de comp- tage du nombre de solutions d'un CSP, d enot e #CSP. Ce probl eme tr es di cile a de nom- breuses applications en informatique, en par- ticulier en Intelligence Arti cielle, et aussi en physique statistique. Des progr es r ecents ont et e fait par des m ethodes de recherche, telle que BTD [16], qui exploitent la structure du graphe de contraintes dans le but de r esoudre des CSPs e cacement. Nous proposons d'adap- ter BTD pour r esoudre le probl eme #CSP. La m ethode de comptage exacte r esultante a dans le pire des cas une complexit e temporelle ex- ponentielle en un param etre graphique sp eci- que appel e largeur d'arbre. Pour des probl emes ayant un graphe peu dense mais une grande largeur d'arbre, nous proposons une m ethode it erative qui approche le nombre de solutions en r esolvant une partition de l'ensemble des contraintes en une collection de sous-graphes partiels triangul es. Sa complexit e temporelle est exponentielle en la taille de la plus grande clique (aussi appel e clique number ) du probl eme d'ori- gine, taille qui peut ^etre beaucoup plus petite que la largeur d'arbre. Des exp erimentations sur des probl emes al eatoires CSP structur es et des benchmarks SAT montrent l'e cacit e pratique de nos approches