Das Brücken Problem

Wir stellen uns vor, daß wir in absoluter Dunkelheit an einen Fluß gelangen und diesen über eine Brücke überqueren wollen. Wenn wir wissen, in welcher Richtung sich die nächste Brücke befindet, können wir diese auf kürzesten Weg ansteuern. Andererseits müssen wir uns mal nach links und mal nach rechts am Ufer entlangtasten. Der Umweg sollte dabei nicht zu groß werden. Es wird gezeigt, daß jede Strategie im schlechtesten Fall mindesten 9 mal den kürzesten Weg zur Brücke zurücklegen muß und daß es eine Methode gibt, die mit diesem Umweg auskommt.

Inhalt des Vortrags:

• Vorstellung des Problems
• Diskretisierung jeder Strategie
• Nicht jede Strategie ist kompetitiv
• Die Verdoppelungsstrategie ist 9-kompetitiv (Theorem 7.10)
• Der Faktor 9 ist auch optimal (Theorem 7.11)

Literatur:

Rolf Klein, Algorithmische Geometrie, Addison Wesley 1997
Kapitel 7.3 S. 330-341.

Betreuer:
Rolf Klein