Nouveaux algorithmes pour la résolution des problèmes de satisfaction de contraintes.

Abstract

Les problèmes de satisfaction de contraintes (CSP) constituent un cadre formel essentiel en intelligence artificielle pour modéliser une large gamme de problèmes combinatoires. Toutefois, leur résolution reste un défi majeur en raison de leur complexité intrinsèque (NP-complète). Cette thèse explore différentes approches de résolution des CSP, en mettant un accent particulier sur les techniques de décomposition structurelle, notamment la Décomposition Hypertree Généralisée (GHD), particulièrement adaptée aux contraintes d'arité élevée. Après une étude approfondie des méthodes existantes, recherche systématique (Backtracking et ses variantes), techniques d'inférence (consistance d'arc, consistance de chemin), recherche locale et approches par apprentissage profond, ce travail propose une amélioration aux algorithmes guidés par la GHD. L'algorithme FC-GHD est introduit, ainsi que deux extensions : FC-GHD+NG, intégrant l'apprentissage de nogoods structurels, et FCGHD+NG+DR, basé sur un réordonnancement dynamique des clusters. La contribution principale de cette thèse réside dansl'introduction d'une stratégie de redémarrage adaptatif, visant à pallier la sensibilité des algorithmes GHD à la racine initiale. L'algorithme Restart-FC-GHD+NG+DR permet de diversifier l'exploration en sélectionnant dynamiquement un nouveau nœud racine tout en réutilisant les nogoods appris lors des phases précédentes. Une évaluation expérimentale sur des benchmarks standards de CSP n-aires démontre une amélioration significative des performances et de la robustesse de algorithme proposé, notamment pour les instances satisfiables et les structures complexes. Ce travail ouvre également des perspectives vers l'intégration de techniques d'apprentissage automatique pour guider dynamiquement les stratégies de redémarrage et d'ordonnancement des clusters.