Algoritmo per inseguire un bersaglio in movimento

Question

Supponiamo di avere un black-box $ f $, che siamo in grado di interrogare e reimpostare. Quando noi ripristiniamo $ f $, lo Stato $ f_S $ di $ f $ è impostato su un elemento scelto in modo uniforme a caso dal set $$ \ {0, 1, ..., n - 1 \} $$ dove $ n $ è fisso e noto per la data $ f $. Per interrogare $ f $, un elemento $ x $ (l'ipotesi) da $$ \ {0, 1, ..., n - 1 \} $$ è fornito, e il valore restituito è di $ (f_S - x) \ mod n $. Inoltre, lo Stato $ f_S $ di $ f $ è impostato su un valore di $ f_S'= f_S \ pm k $, in cui viene selezionato $ k $ uniformemente a caso da $$ \ {0, 1, 2, ..., \ lfloor n / 2 \ rfloor - ((f_S - x) \ mod n) \} $$

Rendendo congetture uniformemente casuali con ogni query, ci si aspetterebbe di dover fare $ n $ congetture prima di ottenere $ f_S = x $, con varianza $ n ^ 2 -. N $ (affermato senza prove)

Può un algoritmo di essere progettato per fare meglio (vale a dire, fare meno supposizioni, possibilmente con meno varianza nel numero di tentativi)? Quanto meglio poteva che fare (vale a dire, che cosa è un algoritmo ottimale, e ciò che è la sua performance)?

Una soluzione efficace a questo problema potrebbe avere importanti implicazioni di risparmio di costi per riprese in un coniglio (limitato a saltare su una pista circolare) in una stanza buia.

Answer 1

Prima di tutto, io supporre che da

Inoltre, lo stato di $ f_S $ di $ f $ è impostato su un valore di $ f_S'= f_S \ pm k $, in cui viene selezionato $ k $ uniformemente a caso da $$ \ {0, 1, 2,. .., \ lfloor n / 2 \ rfloor - ((f_S - x) \ mod n) \} $$

che effettivamente dire

Inoltre, lo Stato $ f_S $ di $ f $ è impostato su un valore di $ f_S'= f_S + k \ mod n $, in cui viene selezionato $ k $ uniformemente a caso da $$ \ left \ {- \ left | \ Left \ lfloor \ frac {n} {2} \ right \ rfloor - ((f_S - x) \ mod n) \ right |, \ ldots, -1, 0, 1, 2, \ ldots, \ left | \ Left \ lfloor \ frac {n} {2} \ right \ rfloor - ((f_S - x) \ mod n) \ right | \ right \} $$

In caso contrario, non è del tutto chiaro che $ f_S \ in \ {0, ..., n-1 \} $ tiene sempre e come esattamente $ f_S \ pm k $ si comporta.

Con questo, il problema viene sostanzialmente verso il basso per "mancante il più possibile". Si osservi che più ci spariamo il coniglio, il luppolo più grandi che egli fa; nel caso estremo che abbiamo $ f_S - x = \ pm 1 \ mod n $. Questo si traduce in un salto uniforme tra $ - (\ lfloor n / 2 \ rfloor \ pm 1) $ e $ (\ lfloor n / 2 \ rfloor \ pm 1) $, che in pratica rende casuale completamente la posizione del coniglio di nuovo. D'altra parte, se ci manca così male come possibile - da un offset di $ f_S - (!) X \ mod n = \ lfloor n / 2 \ rfloor $, il coniglio in realtà non si muove affatto e la scatola nera in realtà ci aggiorna su questo fatto. Pertanto, possiamo solo girare intorno e sparare il coniglio.

Si sono lasciati con la ricerca di una procedura per la mancanza sempre più in ogni scatto. Io propongo un semplice "ricerca binaria". (Vi convenientemente omettere l'arrotondamento.) Si procede approssimativamente come segue:

1. Reset e sparare ad una posizione arbitraria fino ad ottenere dalla Blackbox la risposta $ (f_S - x \ mod n) \ in \ {\ frac {1} {4} n, ..., \ frac {3} {4} n \}. $ Questo richiede una quantità costante di passaggi in attesa.
2. Ora, noi sappiamo che la posizione passata del coniglio $ f_S $, e che non si mosse più di $ \ frac {1} {4} n $ punti in entrambe le direzioni. Questo dimezza in pratica il nostro spazio di ricerca nella successiva iterazione, dal momento che il coniglio deve essere in una posizione $ f_S' \ in \ {(f_S - \ frac {1} {4} n) \ mod n, ..., f_S, ..., (f_S + \ frac {1} {4} n) \ mod n \} $
3. Recurse: Spara alla posizione $ f_S - n / 2 \ mod n $. Con probabilità $ 1/2 $, la posizione $ f_S '$ il coniglio saltato su nella fase 1 e 2 si trova la gamma $ \ {f_S - \ frac {1} {8} n, ..., f_S, ..., f_S + \ frac {1} {8} n \} $. In questo caso abbiamo dimezzato lo spazio di ricerca ancora una volta. Con probabilità $ 1/2 $, il coniglio non ha saltato in tale intervallo, ma dal momento che sappiamo che $ 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 \} $, abbiamo le stesse ipotesi come nel passaggio (2) e quindi perdere nulla.

Ogni passo ha bisogno di $ 2 = \ mathcal {O} (1) $ tempo previsto per avere successo e metà lo spazio di ricerca, ottenendo un complessivo di $ \ mathcal {O} (\ log n) $ previsto numero di passi.