Verlor in einem "One Directional" -Konzert

16

Sie und ein Freund haben sich während eines Konzerts gegenseitig verloren, und keiner ist sich sicher, welcher von Ihnen weiter vorne ist. Formal ist jede auf einer ganzzahligen Koordinate und kann nur auf eine höhere Koordinate zugehen oder an Ort und Stelle bleiben.

Angenommen, Sie und Ihr Freund folgen genau demselben Algorithmus (und nein, Sie dürfen nicht sagen, dass "if (name ==" R B ") etwas tut :)), und der ursprüngliche Abstand zwischen Ihnen beiden war (was nicht der Fall ist) Ihnen bekannt).x

Was ist der Algorithmus, der die erwartete Gehstrecke minimiert, bis Sie und Ihr Freund sich treffen?


Sie können davon ausgehen, dass sowohl Ihr Freund als auch Sie sich mit der gleichen konstanten Geschwindigkeit bewegen.


Ein einfacher Algorithmus wäre zum Beispiel:

  1. In Stufe (ab ):0n0

    • Gehen Sie Schritte nach rechts, wp oder warten Sie ansonsten Zeiteinheiten.13n 3n123n

Um diesen Algorithmus zu sehen, treffen sich die Freunde mit der Wahrscheinlichkeit, dass 1 überlegt, was auf der Bühne passiert . Selbst wenn der Freund, der Schritt voraus war, immer ging und der andere immer an Ort und Stelle blieb, wäre der Abstand zwischen den beiden: x x + 1 + 3 + 9 + + 3 log 3 x = 2 x + x - 1(log3x+1)x

x+1+3+9++3log3x=2x+x123x

Daher der Freund, der gehen , bei der Iteration Strecke von , also mit der Wahrscheinlichkeit den Freund, der sich dahinter befindet wird aufholen und sie werden sich treffen.3 log 3 x + 1 = 3 x 1log3x+13log3x+1=3x14


Eine einfache Optimierung (um die Gehstrecke zu verringern) wäre, anstatt Schritte zu gehen, Schritte zu gehen, wobei gegeben ist durch: c x c 2 + 13xcxc

2+1c1=c

Daraus ergibt sich die optimale für diesen Algorithmus istc = 3 + c c=3+522.618

Obwohl dieser Algorithmus garantiert, dass die Freunde mit der Wahrscheinlichkeit 1 aufeinandertreffen, ist die erwartete Gehstrecke leider unendlich, was ich nach Möglichkeit vermeiden möchte.

Gibt es einen effizienteren Algorithmus?

RB
quelle
Wenn Sie "erwartete Gehstrecke" sagen - meinen Sie im schlimmsten Fall, wenn der Algorithmus probabilistisch ist, oder nehmen Sie auch eine gewisse Verteilung der Eingaben an? Außerdem: Soll Ihr Algorithmus immer korrekt sein, oder muss er in Punkt 1 korrekt sein? (oder weniger?) - Beachten Sie, dass der Algorithmus, den Sie hier präsentieren, möglicherweise niemals anhält (aber wp 0)
Shaull
Dies ähnelt dem linearen Suchproblem ( en.wikipedia.org/wiki/Linear_search_problem ).
Yuval Filmus
2
@Shaull - da beide Freunde dem gleichen Algorithmus folgen, muss es probabilistisch sein, sonst werden sie sich nie treffen. Die Erwartung ist über der Randomisierung des Algorithmus.
RB
2nC2n
steptime unit2n

Antworten:

4

kq123

  • q=12k12k+12k1
  • q=22k12k12k2k12k1
  • q=32k2k2k

k2kk<log2(x)+1k>=log2(x)+11/3

Daher ist die erwartete Gehstrecke (oben begrenzt durch):

2(k=0log2(x)2k+3log2(x)k=log2(x)+1(23)k)

2log2(x)+3216x

dD>0,P(d>D)>0D=0P(d=D)D=E[d]d ist eine viel stärkere Eigenschaft, und ich glaube, es ist nicht möglich, eine Lösung zu finden, die sie befriedigt.

David Durrleman
quelle