Das Geometric Firefighter Problem

Wir möchten einen Feuerausbruch in einem Gebiet modellieren, welches dur ein einfaches geschlossenes Polygon beschrieben werden kann. Um das Feuer an der Ausbreitung zu hindern, können Barrieren gebaut werden, die einen Teil des Polygons vom Feuer separieren. Die möglichen Barrieren stehen zu beginn fest und bestehen hier aus einer Teilmenge der Diagonalen im Polygon. Jede Barriere benötigt Zeit proportional zur länge um errichtet zu werden. Außerdem muss jede Barriere vollständig fertiggestellt sein, bevor das Feuer sie erreicht. Es kann immer nur ein Barriere gleichzeitig gebaut werden.
Ziel ist es eine Auswahl und Reihenfolge von Barrieren zu berechnen, so dass sie in dieser Reihenfolge gebaut eine möglichst große Fläche des Polygons vor dem Feuer schützen.
Dieses Problem wird in dem Artikel Approximation Algorithms for the Geometric Firefighter and Budget Fence Problems von R. Klein, C. Levcopoulos und A. Lingas behandelt und es wird gezeigt, dass dieses Problem NP-Vollständig ist. Es konnte jedoch ein Approximationsalgorithmus entwickelt, welcher in folgendem Applet implementiert wurde.

Der Algorithmus

Jede Barriere kann als Job in einem Scheduling Problem Betrachtet werden. Die Dauer ergibt sich durch die länge und der Geschwindigkeit in der Barrieren gebaut werden können. Durch die Geschwindigkeit mit der sich das Feuer ausbreitet und der kürzesten Distanz vom Ausbruchpunkt zur Barriere ergibt sich ein spätest möglicher Fertigstellungszeitpunkt. Außerdem muss jederm Job ein Wert zugewiesen werden.
Dazu wird das Polygon in Flächen zerlegt die sich ergeben, wenn man das Polygon entlang jeder Barriere zerschneidet. Formal ist die eine Partitionierung des Polygons, so dass der Rand jeder Fläche aus einem Barrierenstück, oder dem Rand des Polygons besteht und von keiner Barriere (echt) geschnitten wird. Jede dieser Flächen (im Applet Prime Areas genannt) wird rot eingefärbt. Jede Barriere erhält nun als Wert das Verhältnis der Fläche aller roten Flächen, die vom Ausbruchpunkt hinter der Barriere liegen geteilt durch die Dauer die benötigt wird um die Barriere fertigzustellen. Diese Bewertung kann sich im laufe des Algorithmus ändern, wenn sich die Farbe einzelner Flächen ändert.
Der eigentlich Algorithmus durchläuft nun eine einzige Schleife, in der jede Barriere genau einmal betrachtet wird und erstellt einen Schedule, welcher zu beginn leer ist.
while es gibt noch eine Barriere die nicht betrachtet wurde do
Wähle eine Barriere mit maximaler Bewertung. Füge diese in den bisherigen Schdule ein, wenn dies ohne sonstige änderungen im Schedule möglich ist. Ist dies nicht möglich füge sie an eine Stelle ein, so dass die Summe aller grünen Flächen, die denjenigen Barrieren zugewiesen wurden, die dazu aus dem Schedule gelöscht werden müssen, insgesamt kleiner ist, als (2) − 1 mal die Summe aller roten Flächen, die von der aktuellen Barriere abgedeckt werden. Färbe alle grünen Flächen, der gelöschten Barrieren grau. Ist auch das nicht möglich, verwirf die Barriere.
Wurde die Barriere nicht verworfen, färbe alle roten Flächen, die von der Barriere abgedeckt werden grün und weise die Flächen eindeutig dieser Barriere zu.
end-while

Das Applet

Kein Java Plugin erkannt
Zunächst muss ein Polygon gezeichnet werden. Dazu kann man entweder manuell die einzelnen Punkte des Polygons durch Linksklicks auf die Zeichenfläche zeichnen, oder man nurzt den Random Button um ein zufälliges Polygon zu verwenden. Hat man das Polygon manuell gezeichnet und ist das Polygon geschlossen muss man noch durch einen Linksklick innerhalb des Polygons einen Punkt festlegen an dem das Feuer ausbricht. Daraufhin wird die Szene initialisiert. Die Gelben Linien stellen die Menge der Barrieren dar die überhaupt gebaut werden können, die Grünen punkte stellen Bäume dar, die zur Visualisierung des Feuers dienen werden.
Durch wiederholtes klicken auf den Next Button, werden Barrieren ausgewählt, die in den Schedule aufgenommen werden. Barrieren im Schedule werden Schwarz dargestellt und tragen eine Kennzeichnung in welcher Reihenfolge sie (vorläufig) gebaut werden. Das Polygon wird ensprechend obigem Algorithmus gefärbt. Durch die Färbung der Bäume lässt sich einschätzen wie weit das Feuer vorangeschritten ist, wenn alle Barrieren im aktuellen Schedule gebaut werden würden. Man beachte hierbei, dass es sich hier nicht um einen online Algorithmus handelt. Selbst Barrieren die aktuell im Einflussgebiet des Feuers liegen, können für den Schedule ausgewählt werden, wenn dafür eine andere Barriere gelöscht wird. Barrieren die nicht mehr in Frage kommen, da sie keine Rote Fläche mehr abdecken, werden gestrichelt dargestellt.
Ist der Schedule endgültig wird der Next Button ausgegraut und das gesamt ungeschütze Gebiet wird verbrannt dargestellt. Durch einen Klick auf den Animationsbutton wird dargestellt wie sich das Feuer während dem Bau der Barrieren Ausbreitet.

Optionen

Show Forest

Schaltet die Bäume zur Visualisierung des Feuers ein und aus

Show Barrier Set

Schaltet die Darstellung der gesamten Barrierenmenge ein und aus

Allow Intersecting

Ist diese Option deaktiviert, dürfen sich die Barrieren nicht schneiden. Es wird eine Triangulation des Polygons verwendet. Ist die Option eingeschaltet, werden etwa 60% aller möglichen Diagonalen verwendet.

Barier rating

Zeigt die Bewertung aller Barrieren an.

Step by step setup

Ermöglicht es die initialisierung Schritt für Schritt nachzuvollziehen.
  1. Berechnung der Diagonalen, die als Barrieren verwendet werden sollen
  2. Berechnung der Paritionierung des Polygons
  3. Berechnung welche Flächen hinter der jeweiligen Barriere liegen.

Building speed

Die Geschwindigkeit mit der Barrieren gebaut werden können

Fire speed

Die Geschwindigkeit mit der sich das Feuer ausbreitet

Beispiele

Example 1

Ein einfaches Beispiel ohne Sonderfälle.

Example 2

Demonstration, dass Barrieren manchmal nicht in sinnvoller Reihenfolge Gebaut werden.

Example 3

Demonstration, dass Barrieren die einmal im Schedule sind auch wieder entfernt werden können.