Next: Klauseln.
Up: Das Kunstausstellungsproblem ist NP-hart
Previous: Das Kunstausstellungsproblem ist NP-hart
Jedes Literal wird zu einem so genannten Literalmuster, wie in
Abbildung A.4 dargestellt. Der Punkt ist von Punkt
und Punkt aus sichtbar. Das gesamte Polygon ist so konstruiert,
dass Punkt von keinem anderen Eckpunkt aus zu sehen ist. Am Punkt
wird eine Wache aufgestellt, falls das Literal den Wert
wahr annimmt, ansonsten erhält Punkt die Wache.
Abbildung A.4:
Das Literalmuster: Der Punkt ist nur von den Punkten und aus sichtbar.
|
Andreas Nüchter
2002-07-10