Implementare l'algoritmo GSAT - Come selezionare quale letterale a Flip?
-
16-10-2019 - |
Domanda
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.
Soluzione
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.