Maxat à l'aide d'algorithme DPLL?

Question

Il est possible de revenir d'un algorithme DPLL M comme maximum pour le problème Max-Sat?:

J'ai un échantillon:

https://gist.github.com/DAVEFERNIG/E670BDA7222D558817F2BA0E90EBCE66F

Nous pouvons modifier la récurrence pour renvoyer le résultat de MAX-SAT?

ressources: https://fr.wikipedia.org/wiki/dpll_algorithm

Answer 1

L'algorithme DPLL n'essaie pas de satisfaire autant de clauses que possible.S'il y a une affectation satisfaisante, DPLL le trouvera.Sinon, DPLL essaiera une série d'affectations partielles jusqu'à ce qu'elle manque de possibilités, puis elle déclarera la formule insatisfaite.Mais dans le cas d'une formule insatisfaite, rien ne garantit que DPLL découvrira le nombre maximal de clauses satisfaisantes sur le point de prouver une insatisfaisabilité.

Le problème MAXSAT est lié à la recherche des sous-formules (muses) minimalement insatisfiables d'une instance.Déterminer si un ensemble de clauses est un MUS est un problème complet.Cela devrait être plus difficile que la simple exhaustivité NP, il est donc peu probable que la modification de DPLL de retourner des solutions partielles soit fructueuse.Étant donné que la classe DP est contenue dans $ \ delta ^ p_2 $ Vous pouvez concevoir un schéma qui appelle dpll (ou algorithmes associés) un nombre polynomial de fois pour produire un maxatrésultat.