Sostenere strutture di dati per SAT ricerca locale

Question

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 .

Answer 1

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 è:

1. Fare un elenco di solo le variabili che si verificano nelle clausole insoddisfatti.
2. Seleziona una variabile $ x $ da questo elenco.
3. contare quante clausole che contengono $ x $ sono soddisfatti.
4. vibrazione di $ x $.
5. contare quante clausole che contengono $ x $ sono soddisfatti.
6. Unflip $ x $.
7. Sottrai il risultato del passaggio 3 dal passaggio 5 e registrare per $ x $.
8. Ripetere i passaggi 2-7 per il resto delle variabili trovato nel passaggio 1.
9. 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.