Problém maximální uspokojivosti - Maximum satisfiability problem

v teorie výpočetní složitosti, problém maximální uspokojivosti (MAX-SAT) je problém stanovení maximálního počtu klauzulí dané Booleovský vzorec v konjunktivní normální forma, což lze splnit přiřazením hodnot pravdy k proměnným vzorce. Jedná se o zobecnění Booleovský problém uspokojivosti, který se ptá, zda existuje přiřazení pravdy, které dělá všechny klauzule pravdivé.

Příklad

Spojovací vzorec normální formy

${ displaystyle (x_ {0} lor x_ {1}) land (x_ {0} lor lnot x_ {1}) land ( lnot x_ {0} lor x_ {1}) land ( lnot x_ {0} lor lnot x_ {1})}$

není uspokojivý: bez ohledu na to, které hodnoty pravdy jsou přiřazeny jeho dvěma proměnným, alespoň jedna z jeho čtyř vět bude nepravdivá. Je však možné přiřadit hodnoty pravdy tak, aby byly tři ze čtyř vět pravdivé; opravdu, každé přiřazení pravdy to udělá. Proto, pokud je tento vzorec uveden jako příklad problému MAX-SAT, řešením problému je číslo tři.

Tvrdost

Problém MAX-SAT je NP-tvrdé, protože jeho řešení snadno vede k řešení booleovský problém uspokojivosti, který je NP-kompletní.

Je také obtížné najít přibližný řešení problému, které splňuje řadu klauzulí v rámci zaručeného přibližný poměr optimálního řešení. Přesněji řečeno, problém je APX -kompletní, a tedy nepřipouští a schéma aproximace v polynomiálním čase pokud P = NP.^[1][2][3]

Vážený MAX-SAT

Obecněji lze definovat váženou verzi MAX-SAT následovně: vzhledem k tomu, že vzorec konjunktivní normální formy s nezápornými váhami přiřazenými každé klauzuli, najděte pravdivé hodnoty pro její proměnné, které maximalizují kombinovanou váhu splněných klauzulí. Problém MAX-SAT je instancí váženého MAX-SAT, kde jsou všechny váhy 1.^[4][5][6]

Aproximační algoritmy

1/2-aproximace

Náhodné přiřazení každé proměnné jako pravdivé s pravděpodobností 1/2 dává očekávaný 2-přiblížení. Přesněji řečeno, pokud má každá klauzule alespoň k proměnných, pak se získá (1 - 2^−k)-přiblížení.^[7] Tento algoritmus může být derandomizováno za použití metoda podmíněných pravděpodobností.^[8]

(1-1/E)-přiblížení

MAX-SAT lze také vyjádřit pomocí celočíselný lineární program (ILP). Opravte konjunktivní vzorec normální formy F s proměnnými X₁, X₂, ..., X_na nechte C označují věty z F. Pro každou klauzuli C v C, nechť S⁺_C a S⁻_C označuje množinu proměnných, které nejsou negovány Ca ty, které jsou negovány C, resp. Proměnné y_X ILP bude odpovídat proměnným vzorce F, zatímco proměnné z_C bude odpovídat doložkám. ILP je následující:

maximalizovat	${ displaystyle sum _ {c v C} w_ {c} cdot z_ {c}}$		(maximalizujte váhu splněných doložek)
podléhá	${ displaystyle z_ {c} leq sum _ {x v S_ {c} ^ {+}} y_ {x} + sum _ {x v S_ {c} ^ {-}} (1-y_ {X})}$	pro všechny ${ displaystyle c v C}$	(klauzule je pravdivá iff má pravdivou, nezápornou proměnnou nebo nepravou, negovanou proměnnou)
	${ displaystyle z_ {c} v {0,1 }}$	pro všechny ${ displaystyle c v C}$.	(každá klauzule je buď splněna, nebo ne)
	${ displaystyle y_ {x} v {0,1 }}$	pro všechny ${ displaystyle x ve F}$.	(každá proměnná je buď pravdivá, nebo nepravdivá)

Výše uvedený program může být uvolněný k následujícímu lineárnímu programu L:

maximalizovat	${ displaystyle sum _ {c v C} w_ {c} cdot z_ {c}}$		(maximalizujte váhu splněných doložek)
podléhá	${ displaystyle z_ {c} leq sum _ {x v S_ {c} ^ {+}} y_ {x} + sum _ {x v S_ {c} ^ {-}} (1-y_ {X})}$	pro všechny ${ displaystyle c v C}$	(klauzule je pravdivá iff má pravdivou, nezápornou proměnnou nebo nepravou, negovanou proměnnou)
	${ displaystyle 0 leq z_ {c} leq 1}$	pro všechny ${ displaystyle c v C}$.
	${ displaystyle 0 leq y_ {x} leq 1}$	pro všechny ${ displaystyle x ve F}$.

Následující algoritmus využívající tuto relaxaci je očekávaný (1-1 /E )-přiblížení:^[9]

1. Vyřešte lineární program L a získat řešení Ó
2. Nastavit proměnnou X být pravdivý s pravděpodobností y_X kde y_X je hodnota uvedená v Ó.

Tento algoritmus lze také derandomizovat pomocí metody podmíněných pravděpodobností.

3/4-přiblížení

Algoritmus aproximace 1/2 je lepší, když jsou klauze velké, zatímco (1-1 /E) -proximace je lepší, když jsou klauze malé. Lze je kombinovat následujícím způsobem:

1. Spuštěním (derandomizovaného) algoritmu aproximace 1/2 získáte přiřazení pravdy X.
2. Spuštěním (derandomizované) (1-1 / e) přiblížení získáte přiřazení pravdy Y.
3. Výstup podle toho, co X nebo Y maximalizuje váhu splněných klauzulí.

Toto je přiblížení deterministického faktoru (3/4).^[10]

Příklad

Na vzorci

$${ displaystyle F = underbrace {(x lor y)} _ {{ text {weight}} 1} land underbrace {(x lor lnot y)} _ {{ text {weight}} 1 } land underbrace {( lnot x lor z)} _ {{ text {weight}} 2+ epsilon}}$$

kde ${ displaystyle epsilon> 0}$, (1-1 /E) -aproximace nastaví každou proměnnou na True s pravděpodobností 1/2, a bude se tedy chovat stejně jako aproximace 1/2. Za předpokladu, že přiřazení X je vybrán jako první během derandomizace, derandomizované algoritmy vyberou řešení s celkovou váhou ${ displaystyle 3+ epsilon}$, zatímco optimální řešení má váhu ${ displaystyle 4+ epsilon}$.^[11]

Řešitelé

Během posledních let bylo vyvinuto mnoho přesných řešičů pro MAX-SAT a mnoho z nich bylo představeno na známé konferenci o problému booleovské uspokojivosti a souvisejících problémech, SAT Conference. V roce 2006 se na konferenci SAT uskutečnila první konference MAX-SAT vyhodnocení porovnání výkonu praktických řešičů pro MAX-SAT, jak tomu bylo v minulosti pro pseudo-booleovská uspokojivost problém a kvantifikovaný booleovský vzorec problém. Vzhledem k jeho NP-tvrdosti nelze obecně vyřešit případy MAX-SAT velkých rozměrů přesně a člověk se musí často uchýlit k aproximační algoritmy a heuristika ^[12]

Na poslední hodnocení Max-SAT je odesláno několik řešitelů:

• Branch and Bound na základě: Clone, MaxSatz (na základě Satz ), IncMaxSatz, IUT_MaxSatz, WBO, GIDSHSat.
• Na základě uspokojivosti: SAT4J, QMaxSat.
• Na základě neuspokojivosti: msuncore, WPM1, PM2.

Speciální případy

MAX-SAT je jedním z optimalizačních rozšíření systému booleovský problém uspokojivosti, což je problém určení, zda proměnné dané Booleovský vzorec lze přiřadit tak, aby byl vzorec vyhodnocen jako PRAVDA. Pokud jsou klauze omezeny na maximálně 2 literály, jako v 2 - uspokojivost, dostaneme MAX-2SAT problém. Pokud jsou omezeny na maximálně 3 literály na klauzuli, jako v 3 - uspokojivost, dostaneme MAX-3SAT problém.

Související problémy

Existuje mnoho problémů souvisejících s uspokojivostí konjunktivní normální formy booleovských vzorců.

• Problémy s rozhodováním:
  • 2SAT
  • 3SAT
• Problémy s optimalizací, kde je cílem maximalizovat počet splněných klauzulí:
  • MAX-SAT a odpovídající vážená verze Vážený MAX-SAT
  • MAX-kSAT, kde má každá klauzule přesně k proměnné:
    • MAX-2SAT
    • MAX-3SAT
    • MAXEkSAT
  • Problém částečné maximální uspokojivosti (PMAX-SAT) požaduje maximální počet klauzulí, které lze splnit jakýmkoli přiřazením dané podmnožiny klauzulí. Zbývající ustanovení musí být splněna.
  • Problém měkké uspokojivosti (soft-SAT), daný souborem problémů SAT, vyžaduje maximální počet problémů, které lze uspokojit jakýmkoli přiřazením.^[13]
  • Problém minimální uspokojivosti.
• Problém MAX-SAT lze rozšířit na případ, kdy proměnné proměnné problém spokojenosti s omezením patří do množiny skutečností. Problém spočívá v hledání těch nejmenších q takové, že q-uvolněná křižovatka omezení není prázdné.^[14]

Viz také

• Booleovský problém uspokojivosti
• Omezení spokojenosti
• Teorie modulo uspokojivosti

externí odkazy

• http://www.satisfiability.org/
• https://web.archive.org/web/20060324162911/http://www.iiia.csic.es/~maxsat06/
• http://www.maxsat.udl.cat
• Vážená měřítka Max-2-SAT se skrytými optimálními řešeními
• Poznámky k přednášce o MAX-SAT aproximaci

Reference

• Vazirani, Vijay V. (2001), Aproximační algoritmy (PDF), Springer-Verlag, ISBN  978-3-540-65367-7