Implementacja algorytmu GSAT - Jak wybrać literał do przerzucenia?

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ł.

Czy nie szukamy maksymalnej liczby spełnionych klauzul?

Tak, szukamy zadania, które spełnia maksymalną liczbę klauzul (najlepiej wszystkie). W tym celu zadajemy sobie pytanie: „Która pojedyncza zmienna zbliży nas do tego celu, gdy go przerzucimy?” a następnie odwróć.

Wydaje mi się, że próbujemy użyć rozwiązania lub jego przybliżeń, aby znaleźć rozwiązanie.

Korzystając z tego rozwiązania, zapytalibyśmy: „Która kombinacja wielu rzutów dałaby najlepszy wynik?” lub po prostu „Które zadanie byłoby najlepsze?”. Jednak nie to robimy, patrzymy tylko o krok do przodu. Zastosowanie przybliżenia rozwiązania wydaje się dokładnym opisem. Jednak nie ma w tym nic złego. Tak działają chciwe strategie.

Wygeneruj przestrzeń stanu ze wszystkimi możliwymi odwróceniami i poszukaj w niej literału, który zapewni najlepsze przybliżenie do stanu celu.

Dobrze.