[LO5] 7.2. Recherche de modèle par simplification
Channel: Sylvain Schmitz
Date: 2020-10-04

Une autre façon de voir les arbres de recherche de modèle par énumération : on simplifie l'ensemble de clauses étape par étape. Cela permet d'arrêter l'exploration de certaines branches plus tôt : si on obtient l'ensemble vide Ø de clauses, c'est satisfiable ; si on obtient un ensemble de clauses qui contient la clause vide ⊥, c'est insatisfiable. Les choix de littéraux par lesquels simplifier le long des branches a maintenant une importance, ce qui va permettre de mettre en place des optimisations (l'algorithme DPLL que l'on verra après en est une) et des heuristiques de choix des littéraux.