Dieses Spiel kann einem verrückt machen. Man fährt mit dem Fahrzeug hin und her und generiert hohe Kosten. Wenn man nur wüsste, in welcher Region der nächste Notruf auftritt! Viele alltägliche oder technische Probleme verlangen nach Entscheiden, obwohl nicht alle Fakten vorliegen. In diesen Fällen muss man fortlaufend Entscheiden, man spricht von einem Online-Problem.

Optimal geringe Kosten wären nur möglich, wenn man die Zukunft vollständig kennen würde. Dies wäre die „allwissenden Strategie“. Die Frage ist, wie viel mal schlechter die gewählte Online-Strategie im Vergleich zur allwissenden Strategie ist. Ist diese um den Faktor 2 oder 3 schlechter? Eine Strategie ist k-kompetetitiv, wenn sie höchstens k-mal schlechter als eine allwissende Strategie ist.

Vielleicht sind Sie immer mit dem am nächsten gelegenen Fahrzeug zum Notruf gefahren? Sie haben also bei jeder Entscheidung die günstigste Variante gewählt. Man spricht von einer „Greedy Strategie“ – „greedy“ heisst gierig.
Vielleicht haben Sie die Fahrzeuge möglichst gleichmässig über das Spielfeld verteilt und ihnen ein Notfallrayon zugeteilt, welches sie nicht verlassen. Eventuell haben Sie überlappende Rayons definiert.

Man könnte sich bei wenigen Fahrzeugen vorstellen, mit einem zweiten Fahrzeug eine Kurzstrecke zu fahren, damit dieses für künftige Notrufe besser positioniert ist. Zum Beispiel wenn das Fahrzeug vorher am Rand des Spielfeldes stand.

Die zuletzt skizzierte Strategie hat eine Kompetitivität von 2 und ähnelt dem Double-Coverage-Algorithmus. Für weitere Details und spannende Spiele rund um Informatik empfiehlt sich das Buch „Abenteuer Informatik“ von Jens Gallenbacher [EAN: 9783662539651].