Problème de satisfaction de contraintes n-aires : une étude expérimentale
Résumé
Depuis quelques années, la communauté I.A. affiche un intérêt croissant pour les Problèmes de Satisfaction de Contraintes (CSPs), cadre de formalisation puissant pour de nombreux problèmes du monde réel et généralement NP-complets. Les méthodes de recherche de solutions pour les CSPs de type Forward Checking (FC) ont été intensivement étudiées dans le cas binaire. Ces derniéres années ont vu arriver de nombreux résultats relatifs aux CSPs n-aires. Notre objectif général est de développer une bibliothèque d'algorithmes de recherche arborescente distribués capables de s'attaquer à des CSPs généraux suite à l'analyse préalable des algorithmes n-aires d'arc-consistance et de résolution, qui permettrait d'en sélectionner ceux qui sont les plus efficaces. Plutôt que d'utiliser des solveurs existants, nous avons développé notre propre solveur pour mener des études expérimentales sur des CSPs n-aires.
Loading...