Algo. für Optimierungsproblem < Komplex. & Berechnb. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) überfällig  | | Datum: | 20:00 Mo 02.07.2012 | | Autor: | j3ssi |
| Aufgabe | Aus der Vorlesung kennen Sie bereits das Entscheidungsproblem Sat. Hier betrachten wir eine Variante davon, das Optimierungsproblem MaxSat:
Problem: MaxSatO
Gegeben: Aussagenlogische Formel [mm] $\phi$ [/mm] über n Variablen in konjunktiver Normalform.
Gesucht: Eine Variablenbelegung, welche die Anzahl erfüllter Klauseln in maximiert.
a) Formulieren Sie das zugehörige Wertproblem MaxSatW und Entscheidungsproblem Max-Sat. (1 Punkt)
b) Zeigen Sie: (4 Punkte)
(i) Ist MaxSat in polynomieller Zeit lösbar, so auch MaxSatW. [2 Punkte]
(ii) Ist MaxSatW in polynomieller Zeit lösbar, so auch MaxSatO.
Hinweis: Wie ändert sich [mm] $\phi$, [/mm] wenn eine Variable auf
”wahr“ gesetzt wird? Wie wirkt sich das auf die Anzahl der maximal erfüllbaren Klauseln in der geänderten Formel
aus?
[2 Punkte] |
MaxSatW soll die maximale Anzahl erfüllbarer Klauseln in [mm] $\phi$ [/mm] angeben.
MaxSat soll bei Eingabe k und [mm] $\phi$ [/mm] angeben, ob [mm] $\phi$ [/mm] eine Variablenbelgung hat, sodass die Anzahl erfüllbarer Klauseln [mm] $\ge [/mm] k$ ist.
Mir fehlt für die Teilaufgabe b) (ii) eine Einschätzung, ob meine Beweisidee überhaupt möglich ist.
Ich nehme an, dass es einen Algorithmus für MaxSatW gibt, der in polynomieller Zeit ein $k [mm] \in \IN$ [/mm] ausgibt, welches die Anzahl maximal erfüllbarer Klauseln in [mm] $\phi$ [/mm] ist.
Nun habe ich versucht einen Algorithmus zu finden, der bei Eingabe k und [mm] $\phi$ [/mm] in polynomieller Zeit schafft, die Variablenbelegung auszugeben, so dass k Klauseln erfüllt sind.
Irgendwie komme ich beim Suchen hier nicht weiter, und frage mich ob so ein Algorithmus überhaupt zu finden ist.
Wäre nett wenn sich hier jemand findet, der mir dabei helfen könnte.
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 09:18 Di 03.07.2012 | | Autor: | Stoecki |
hallo,
ich habe erstmal eine rückfrage:
was genau soll der unterschied zwischen MaxSatO und MaxSatW sein? sind bei MaxSatW die klauseln unterschioedlich gewichtet?
gruß bernhard
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 09:28 Di 03.07.2012 | | Autor: | j3ssi |
MaxSat ist ein Entscheidungsproblem,
MaxSatW gibt die optimale Lösung aus
und MaxSatO gibt Belgegung, die zur optimalen Lösung passt aus.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 20:20 Mi 04.07.2012 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
