Implementierung des GSAT -Algorithmus - Wie kann ich ausgewählt werden, welches wörtliche zum Flip?

Question

Der GSAT -Algorithmus ist größtenteils direkt: Sie erhalten eine Formel in konjunktiver normaler Form und drehen die Literale der Klauseln um, bis Sie eine Lösung finden, die die Formel erfüllt oder die Max_tries/max_flips -Grenze und keine Lösung finden.

Ich implementiere den folgenden Algorithmus:

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

Ich habe Probleme, die folgende Zeile zu interpretieren:

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

Ist die maximale Anzahl zufriedener Klauseln nicht das, wonach wir suchen? Es scheint mir, dass wir versuchen, die Lösung oder Annäherungen an sie zu verwenden, um die Lösung zu finden.

Ich habe über einige Möglichkeiten nachgedacht, dies zu tun, aber es wäre gut, andere Standpunkte zu hören (die Annahme ist, dass nach der Auswahl der Variablen umgedreht wird.):):

• Erstellen Sie einen Zustandsraum mit allen möglichen Flips und durchsuchen Sie den Raum nach einem wörtlichen, der zu der besten Annäherung an den Zielzustand führt.
• Wählen Sie zufällig die Variable aus, die ich mit den häufigeren Literalen umdrehen werde.
• Wählen Sie ein zufälliges wörtliches.

Answer 1

Ist die maximale Anzahl zufriedener Klauseln nicht das, wonach wir suchen?

Ja, wir suchen nach einer Aufgabe, die die maximale Anzahl von Klauseln erfüllt (das sind alle, vorzugsweise). Und zu diesem Zweck fragen wir uns: "Welche einzelne Variable wird uns diesem Ziel am nächsten bringen, wenn wir es umdrehen?" Und dann drehen Sie es um.

Es scheint mir, dass wir versuchen, die Lösung oder Annäherungen an sie zu verwenden, um die Lösung zu finden.

Die Verwendung der Lösung wäre, wenn wir fragen würden: "Welche Kombination mehrerer Flips würde das beste Ergebnis liefern?" oder einfach "Welche Aufgabe wäre die beste?". Das tun wir jedoch nicht, wir suchen nur einen Schritt voraus. Die Verwendung einer Näherung der Lösung scheint eine genaue Beschreibung zu sein. Daran ist jedoch nichts auszusetzen. So funktionieren gierige Strategien.

Erstellen Sie einen Zustandsraum mit allen möglichen Flips und durchsuchen Sie den Raum nach einem wörtlichen, der zu der besten Annäherung an den Zielzustand führt.

Recht.