Sostenere strutture di dati per SAT ricerca locale
-
16-10-2019 - |
Domanda
WalkSAT e GSAT sono ben noti e semplici algoritmi di ricerca locale per risolvere il soddisfacibilità booleana problema. Il pseudocodice per l'algoritmo GSAT viene copiato dalla questione l'implementazione dell'algoritmo GSAT -?. Come selezionare quale letterale capovolgere e presentate di seguito
procedure GSAT(A,Max_Tries,Max_Flips)
A: is a CNF formula
for i:=1 to Max_Tries do
S <- instantiation of variables
for j:=1 to Max_Iter do
if A satisfiable by S then
return S
endif
V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
S <- S with V flipped;
endfor
endfor
return the best instantiation found
end GSAT
Qui capovolgere la variabile che massimizza il numero di clausole soddisfatti. Come è questo fatto in modo efficiente? Il metodo ingenuo è quello di capovolgere tutte le variabili, e per ogni passo attraverso tutte le clausole e calcolare quanti di loro ottiene soddisfatti. Anche se una clausola potrebbe essere interrogato per soddisfattibilità in tempo costante, il metodo più semplice sarebbe ancora eseguiti in $ O (VC) $ tempo, dove $ V $ è il numero di variabili e $ C $ il numero di clausole. Sono sicuro che possiamo fare meglio, da qui la domanda:
Molti algoritmi di ricerca locale capovolgere l'assegnazione della variabile che massimizza il numero di clausole soddisfatte. In pratica, con quello che le strutture di dati è supportato questa operazione in modo efficiente?
Questo è qualcosa che mi sento come libri di testo spesso omettono. Un esempio è anche il famoso Russell & Norvig libro .
Soluzione
La struttura dei dati necessaria è un verificarsi list , un elenco per ogni variabile che contiene le clausole della variabile si verifica in. Queste liste sono costruiti una volta, quando il CNF è prima lettura. Essi sono utilizzati in punti 3 e 5 di seguito per evitare la scansione di tutta la formula CNF per contare le clausole soddisfatti.
Un algoritmo meglio di lanciando ogni variabile è:
- Fare un elenco di solo le variabili che si verificano nelle clausole insoddisfatti.
- Seleziona una variabile $ x $ da questo elenco.
- contare quante clausole che contengono $ x $ sono soddisfatti.
- vibrazione di $ x $.
- contare quante clausole che contengono $ x $ sono soddisfatti.
- Unflip $ x $.
- Sottrai il risultato del passaggio 3 dal passaggio 5 e registrare per $ x $.
- Ripetere i passaggi 2-7 per il resto delle variabili trovato nel passaggio 1.
- Rifletti la variabile con il numero più alto registrato nel passaggio 7.
Un riferimento per la struttura dei dati (spesso conosciuto anche come lista di adiacenza) è per esempio Lynce e Marques-Silva, efficienti strutture dati per Backtracking SAT risolutori, 2004.