Algorytm GSAT jest w większości prosty: dostajesz formułę w spójnej normalnej formie i przerzucasz literały klauzul, aż znajdziesz rozwiązanie, które spełnia formułę lub nie osiągniesz limitu max_tries / max_flips i nie znajdziesz rozwiązania.
Implementuję następujący algorytm:
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
Mam problem z interpretacją następującego wiersza:
V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
Czy nie szukamy maksymalnej liczby spełnionych klauzul? Wydaje mi się, że staramy się użyć rozwiązania lub jego przybliżeń, aby znaleźć rozwiązanie.
Myślałem o kilku sposobach na zrobienie tego, ale dobrze byłoby usłyszeć inne punkty widzenia (założono, że kiedy zmienna zostanie odwrócona, gdy zostanie wybrana.):
- Wygeneruj przestrzeń stanu ze wszystkimi możliwymi odwróceniami i poszukaj w niej literału, który zapewni najlepsze przybliżenie do stanu celu.
- Losowo wybierz zmienną, którą przerzucę, zaczynając od literałów, które są bardziej powszechne.
- Wybierz losowy literał.
źródło