Algorithmus, um ein sich bewegendes Ziel zu verfolgen

Question

Angenommen, wir haben eine Black-Box $ f $, die wir abfragen und zurücksetzen können. Wenn wir $ f $ zurücksetzen, wird der Status $ f_s $ von $ f $ auf ein Element eingestellt $ ist fest und bekannt für gegeben $ f $. Um $ f $ zu befragen, wird ein Element $ x $ (die Vermutung) von $$ {0, 1, ..., n - 1 } $$ bereitgestellt und der zurückgegebene Wert beträgt $ (f_s - x) Mod n $. Zusätzlich wird der Status $ f_s $ von $ f $ auf einen Wert $ f_s '= f_s pm k $ eingestellt, wobei $ k $ einheitlich zufällig aus $$ {0, 1, 2, .... lfloor n/2 rfloor - ((f_s - x) mod n) } $$

Indem man bei jeder Abfrage gleichmäßig zufällige Vermutungen vorgenommen hat, muss man erwarten, $ n $ Vermutungen vorzulegen, bevor $ f_s = x $ mit Varianz $ n^2 - n $ (ohne Beweis angegeben) erhalten muss.

Kann ein Algorithmus so konzipiert werden, dass es besser abschneidet (dh weniger Vermutungen machen, möglicherweise mit weniger Abweichungen in der Anzahl der Vermutungen)? Wie viel besser könnte es tun (dh, was ist ein optimaler Algorithmus und was ist seine Leistung)?

Eine effiziente Lösung für dieses Problem könnte wichtige kostensparende Auswirkungen auf das Schießen auf einem Kaninchen (auf eine kreisförmige Strecke beschränkt) in einem dunklen Raum.

Answer 1

Zuallererst werde ich das von annehmen

Zusätzlich wird der Status $ f_s $ von $ f $ auf einen Wert $ f_s '= f_s pm k $ eingestellt, wobei $ k $ einheitlich zufällig aus $$ {0, 1, 2, .... lfloor n/2 rfloor - ((f_s - x) mod n) } $$

Du meinst tatsächlich

Zusätzlich wird der Status $ f_s $ von $ f $ auf einen Wert $ f_s '= f_s + k mod n $ eingestellt, wobei $ k $ einheitlich zufällig von $$ links {- links | einheitlich ausgewählt wird links lfloor frac {n} {2} rechts rfloor - ((f_s - x) mod n) rechts |, ldots, -1, 0, 1, 2, ldots, links | links lfloor frac {n} {2} rechts rfloor - ((f_s - x) mod n) rechts | rechts } $$

Andernfalls ist nicht ganz klar, dass $ f_s in {0, ..., n-1 } $ immer hält und wie genau $ f_s pm k $ sich verhält.

Das Problem ist im Wesentlichen darauf zurückzuführen, dass "so viel wie möglich fehlt". Beobachten Sie, dass je näher wir auf das Kaninchen schießen, desto größere Hopfen, die er macht; Im Extremfall haben wir $ f_s - x = pm 1 mod n $. Dies führt zu einem einheitlichen Hopfen zwischen $ -( lfloor n/2 rfloor pm 1) $ und $ ( lfloor n/2 rfloor pm 1) $, was die Position des Kaninchens im Wesentlichen vollständig zufällig vollständig randomisiert. Auf der anderen Seite, wenn wir so schlecht wie möglich vermissen - durch einen Versatz von $ f_s - x mod n = lfloor n/2 rfloor $, bewegt sich der Kaninchen tatsächlich überhaupt nicht (!) und Die Black Box aktualisiert uns tatsächlich über diese Tatsache. Deshalb können wir uns einfach umdrehen und das Kaninchen schießen.

Wir haben ein Verfahren, um zunehmend in jedem Schuss zu fehlen. Ich schlage eine einfache "binäre Suche" vor. (Ich werde die Rundung bequem weglassen.) Es geht ungefähr wie folgt fort:

1. Setzen Sie und schießen Sie an einer willkürlichen Position, bis Sie aus der Blackbox die Antwort $ (f_s - x mod n) in { frac {1} {4} n, ..., frac {3} {4} erhalten haben. N }.
2. Jetzt wissen wir, dass die vergangene Position des Kaninchens $ f_s $ und dass es nicht mehr als $ frac {1} {4} n $ in beide Richtungen bewegt hat. Dies halbiert grundsätzlich unseren Suchraum in der nächsten Iteration, da das Kaninchen an einer Position $ f_s ' in {(f_s - frac {1} {4} n) mod n, ..., f_s, sein muss ..., (f_s + frac {1} {4} n) mod n } $
3. Wiederholen: Schießen Sie an Position $ f_s - n/2 mod n $. Mit der Wahrscheinlichkeit $ 1/2 $ ist die Position $ f_s '$ Das Kaninchen in Schritt 1 & 2 ist der Bereich $ {f_s - frac {1} {8} n, ..., f_s, ..., f_s + liegt frac {1} {8} n } $. In diesem Fall haben wir den Suchraum noch einmal halbiert. Mit Wahrscheinlichkeit $ 1/2 $ sprang das Kaninchen nicht in diesen Bereich, aber da wir wissen, dass $ f_s ' - x mod n = f_s' - f_s + n/2 mod n in { frac {1} {2} n - frac {1} {4} n, ..., frac {1} {2} n + frac {1} {4} n } $, wir haben die gleichen Annahmen wie in Schritt (2) und damit nichts verlieren.

Jeder Schritt benötigt $ 2 = mathcal {o} (1) $ erwartete Zeit, um den Suchraum erfolgreich zu machen und zu hemmen, wodurch eine Gesamtzahl von $ mathcal {o} ( log n) $ erwartete Anzahl von Schritten ergibt.