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