Aufgabe:
eine aussagenlogische Formel mit n = 100 Variablen A1, A2, . . . , An gegeben. Die Formel liegt in konjunktiver Normalform vor. Eine Klausel C der Formel wird dabei durch eine Teilmenge
TC ⊆ {1, 2, . . . , n} ∪ {−1, −2, . . . , −n}
wie folgt codiert:
• Ai kommt in C vor, genau dann wenn i ∈ TC ist.
• ¬Ai kommt in C vor, genau dann wenn −i ∈ TC ist.
Gesucht ist eine Belegung
b : {A1, A2, . . . , An} → {true, false},
sodass die Anzahl τ (b) von Klauseln in der Formel, die unter der Belegung b den Wert true haben, so groß wie möglich ist.
Problem/Ansatz:
Wie wählen Sie die Startbelegung b0?
• Wie erhalten Sie aus einer vorliegenden Belegung bi eine Belegung bi+1 mit τ (bi) < τ (bi+1)?
• Wann brechen Sie die Iteration ab?
