DPLL 알고리즘을 사용하는 Maxsat?

Question

DPLL 알고리즘 M에서 최대 SAT 문제가 최대로 반환 할 수 있습니까? :

샘플이 있습니다.

https://gist.github.com/davefernig/e670bda722d558817f2ba0e90ebce66f

MAX-SAT의 결과를 반환하기 위해 반복성을 수정할 수 있습니까?

자원 : https://en.wikipedia.org/wiki/dpll_algorithm

Answer 1

DPLL 알고리즘은 가능한 한 많은 절을 만족 시키려하지 않습니다.만족스러운 과제가있는 경우 DPLL은 그것을 찾을 것입니다.그렇지 않으면 DPLL은 가능성이 부족할 때까지 일련의 부분 할당을 시도하고 수식을 불가능하게 선언 할 것입니다.그러나 불만족 할 수없는 수식의 경우, DPLL은 불만족을 증명할 수있는 방법에 대한 최대한의 만족 가능한 절을 발견 할 것으로 보장하지 않습니다.

MAXSAT 문제는 인스턴스의 최소한의 불만족 할 수없는 하위 포커스 (MUSES)를 찾는 것과 관련이 있습니다.클로스 세트가 MUS인지 여부를 결정하는 것은 DP 완전한 문제입니다.이것은 단순한 NP 완전성보다 더 어려울 것으로 예상되므로 DPLL을 반환하도록 변환하는 것은 가능하지 않을 것 같지 않습니다.클래스 DP가 $ \ delta ^ p_2 $ dpll (또는 관련 알고리즘)을 호출하는 계획을 고안하여 maxsat을 생성하기 위해 다항식 횟수를 호출 할 수 있습니다결과.