Aufgabe:
Ein Roboter wird vor eine unendlich lange Mauer gesetzt, und soll den (einzigen) Durchgang
suchen, so dass er möglichst wenige Schritte zurücklegt. In nur eine Richtung zu suchen, kann
zu unendlichem Wettbewerbsfaktor führen. Beschreibe eine Strategie mit (kleinem) konstanten
Wettbewerbsfaktor.
Problem/Ansatz:
Der Wettbewerbsfaktor wird berechnet indem man die Laufzeit vom Algorithmus durch die Laufzeit des optimalen Algorithmus teilt.
Der optimale Algo wäre einer der die Position schon kennt und würde direkt zum Punkt laufen, also Laufzeit k.
Ich weiß aber nicht wie ich es beim nicht Optimalen angehen soll. Betrachte man die Startposition als 0 auf den ganzen Zahlen, dann müsste ich abwechselnd 1, -1, 2, -2, 3, -3, ... abgehen, damit hätte ich aber eine Laufzeit von O(k^2) und somit ein Wettbewerbsfaktor von O(k).
Wenn ich eine größere Schrittlänge m wähle habe ich eine Laufzeit von O(log^2(k/m)) was als Wettbewerbsfaktor log^2(k/m)/k < einer Konstante sein würde, aber was wäre dafür das optimalste m? (Oder ich habe mich verrechnet)
Grüße
