Kameras an Kreuzungen: Greedy ist nicht immer optimal
Kameras an Kreuzungen
In einem Park sollen Kameras an Kreuzungen (Knoten) so aufgestellt werden, dass jeder Weg (Kante) von mindestens einer Kamera an einem seiner Enden überwacht wird. Eine Aufstellung, die jeden Weg überwacht, ist eine zulässige Lösung. Kameras sind teuer – optimal ist eine zulässige Aufstellung mit möglichst wenigen Kameras.
Kleine Parks untersuchen
Bevor man ein Verfahren sucht, lohnt es sich, ein paar sehr kleine Instanzen von Hand zu lösen. Dabei fallen oft Eigenschaften des Problems auf, die zu einer Lösungsidee führen.
Aufgabe 2: An einer Kreuzung endet nur ein einziger Weg (wie bei A in Park 1). Wohin stellst du die Kamera für diesen Weg?
Merke: kleine Instanzen untersuchen
An kleinen Instanzen erkennt man Eigenschaften eines Problems und entwickelt erste Lösungsideen. Hier: Eine Kamera am anderen Ende eines Endweges überwacht denselben Weg und vielleicht noch weitere – sie ist nie schlechter. Beim Dreieck gibt es aber keine Endkreuzung, dort hilft diese Idee nicht weiter.
Die Greedy-Idee
Eine andere Idee für beliebige Parks: Stelle die nächste Kamera immer dort auf, wo die meisten noch unbewachten Wege zusammenkommen. Wiederhole das, bis alle Wege überwacht sind.
Aufgabe 5: Was zeigt der Vergleich von Aufgabe 3 und 4 über Greedy-Algorithmen?
Merke: optimale und gefundene Lösung
Die optimale Lösung ist die beste zulässige Lösung, die es gibt. Ein Verfahren liefert eine gefundene Lösung. Die Greedy-Idee findet immer eine zulässige Lösung (alle Wege sind überwacht) – sie ist aber nicht immer optimal.
Ein Verfahren, das schnell eine meist gute, aber nicht garantiert optimale Lösung findet, heißt Heuristik. Die Greedy-Idee für die Kameras ist eine Heuristik.
Für das Aufstellen der Kameras kennt bis heute niemand ein schnelles Verfahren, das immer die optimale Lösung findet – vermutlich gibt es keins. Solche Probleme sind auch für Computer „schwer“: Man hat nur die Wahl zwischen Brute Force (optimal, aber bei großen Instanzen viel zu langsam) und Heuristiken (schnell, aber nicht immer optimal). Kürzeste Wege und Spannbäume dagegen sind „leicht“.
Aufgabe 6: Welche Aussage über Heuristiken stimmt?