Implementare l'algoritmo GSAT - Come selezionare quale letterale a Flip?

Question

L'algoritmo GSAT è, per la maggior parte, dritto in avanti: È possibile ottenere una formula in forma normale congiuntiva e capovolgere i letterali delle clausole fino a trovare una soluzione che soddisfi la formula o si raggiunge la max_tries / limitano max_flips e scoperta nessuna soluzione.

sto implementando il seguente algoritmo:

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

Ho problemi interpretare la seguente riga:

V <- the variable whose flip yield the most important raise in the number of satisfied clauses;

Non è il numero massimo di clausole soddisfatto quello che stiamo cercando? Mi sembra che stiamo cercando di utilizzare la soluzione o approssimazioni ad esso per trovare la soluzione.

Ho pensato di alcuni modi per fare questo, ma Sarebbe bello sentire altri punti di vista (Il presupposto è che una volta che la variabile è capovolto una volta che è stato selezionato.):

• Generare uno spazio di stato con tutte le possibili salti mortali e cercare lo spazio per un letterale che si traduce nella migliore approssimazione allo stato obiettivo.
• in modo casuale selezionare la variabile che io capovolgere a partire dai letterali che sono più comuni.
• Scegli un letterale casuale.

Answer 1

Non è il numero massimo di clausole soddisfatto quello che stiamo cercando?

Si, stiamo cercando un incarico che soddisfa il numero massimo di clausole (che è tutto di loro, preferibilmente). E a tal fine ci chiediamo "Quale singola variabile ci porterà più vicino a questo obiettivo quando si è ribaltato vero?" e poi capovolgere.

Mi sembra che stiamo cercando di utilizzare la soluzione o approssimazioni ad esso per trovare la soluzione.

Utilizzando la soluzione sarebbe se abbiamo chiesto "Quale combinazione di molteplici lanci darebbe il miglior risultato?" o semplicemente "Quale incarico sarebbe la migliore?". Tuttavia questo non è quello che stiamo facendo, stiamo solo cercando un passo avanti. Utilizzando un'approssimazione della soluzione sembra una descrizione accurata. Tuttavia non c'è niente di sbagliato in questo. È così che le strategie di avidi di lavoro.

Generare uno spazio di stato con tutte le possibili salti mortali e cercare lo spazio per un letterale che si traduce nella migliore approssimazione allo stato obiettivo.

A destra.