Maxsat usando algoritmo DPLL?

Question

È possibile tornare da un algoritmo DPLL M come massimo per il problema max-sat ?:

Ho un esempio:

https://gist.github.com/davefornig/e670bda722d558817F2Ba0E90EBCE66F

Possiamo modificare la recidiva per restituire il risultato di Max-Sat?

Risorse: https://en.wikipedia.org/wiki/dpll_algorithm

Answer 1

L'algoritmo DPLL non cerca di soddisfare il maggior numero possibile di clausole.Se c'è un incarico soddisfacente, DPLL lo troverà.Altrimenti DPLL proverà una serie di incarichi parziali finché non esaurisce le possibilità, e quindi dichiarerà la formula insoddisfattabile.Ma nel caso di una formula insoddisfacente, non vi è alcuna garanzia che DPLL scoprirà il numero massimo di clausole soddisfavoli sulla strada per dimostrare insoddisfattime.

Il problema Maxsat è legato alla ricerca delle sottoschedule minimamente insoddisfacute (muse) di un'istanza.Determinare se un insieme di clausole è un mus è un problema completo di DP.Ciò dovrebbe essere più difficile della semplice completezza NP, quindi è improbabile che la modifica DPLL per restituire le soluzioni parziali sarà fruttuosa.Dato che la classe DP è contenuta in $ \ delta ^ p_2 $ Si potrebbe elaborare uno schema che chiama DPLL (o algoritmi correlati) un numero polinomiale di volte per produrre un maxsatrisultato.