Satisfaction contrainte : Formulation et algorithmes

Cette séance de cours couvre la formulation de problèmes de satisfaction des contraintes (CSP) et d'algorithmes systématiques pour les résoudre. Il examine les défis de l'explosion combinatoire dans les algorithmes de recherche en général et introduit le concept de satisfaction des contraintes pour permettre des méthodes plus efficaces. Des exemples comme les problèmes d'affectation des ressources sont utilisés pour illustrer la formulation du PSC. La séance de cours explore également des algorithmes systématiques comme la recherche profondeur-première et l'heuristique comme backjumping et la vérification avant. Diverses techniques pour améliorer l'efficacité des solutions CSP, telles que les algorithmes de recherche locaux comme l'escalade de colline et le recuit simulé, sont présentées. L'importance des algorithmes de cohérence pour réduire la complexité de la recherche est soulignée, de même que les applications pratiques pour les problèmes de programmation, de planification et de conception.