La Résolution de CSP par les méthodes de décompositions arborescentes.

Abstract

Résoudre un CSP constitue un problème NP-Complet. Devant cette difficulté, des recherches ont été faites et qui ont conduits à définir de nombreuses méthodes de résolution qu'on peut classer en deux approches : une repose sur l'exploration complète de l'espace de recherche, tandis que l'autre utilise des heuristiques. Parmi, on compte les méthodes de décomposition arborescente. De ces méthodes, il y a celles qui décomposent le graphe de contraintes associé au CSP sans le triangulé comme l'heuristique H-TD-WT proposée par Ciril Tireoux. L'inconvénient principale de celle-ci est le choix du premier Cluster et de limité sa taille maximale qui nécessite des heuristiques. Cela augmente le temps de résolution. La résolution de CSP par les méthodes basées sur la triangulation fait le bon choix du premier cluster de départ, diminue la taille et donne des solutions proches de l'optimum. LEX-M est t'une méthode de triangulation qui date de 1976 qui donne une triangulation minimale et de largeur minimale, le choix du sommet de départ est basé sue l'ordre lexicographique cela nous permis de triangulé le graphe de contraintes sans faire recours à des heuristiques. Le fait que LEX-M n'a pas d'autres méthodes concurrentes, en termes du temps d'exécution ou de complexité théorique, la triangulation par LEX-M est un bon choix.