Algorytm ścigania ruchomego celu

Załóżmy, że mamy czarną skrzynkę $f$ którą możemy wyszukać i zresetować. Kiedy przywrócić $f$ stan $f_S$ o $f$ ma wartość pierwiastka wybranego losowo równomiernie ze zbioru

{0, 1, . . ., n - 1}

$\{0, 1, ..., n - 1\}$ gdzie

n

$n$ jest ustalone i znane dla danego

f

$f$ . Do zapytania

f

$f$ , element

x

$x$ (przypuszczenie) z

{0, 1, . . ., n - 1}

$\{0, 1, ..., n - 1\}$ jest podany, a zwracana wartość to . Ponadto stan dla jest ustawiony na wartość , gdzie jest wybierane losowo równomiernie z

(f_{S} - x) \mod n

$(f_S - x) \mod n$

f_{S}

$f_S$

f

$f$

f_{S}^{'} = f_{S} \pm k

$f_S' = f_S \pm k$

k

$k$

{0, 1, 2, . . ., ⌊ n / 2 ⌋ - ((f_{S} - x) \mod n)}

$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\}$

Wykonując jednolicie losowe domysły przy każdym zapytaniu, należałoby się spodziewać domysłów przed uzyskaniem , z wariancją (podane bez dowodu). $n$ $f_S = x$ $n^2 - n$

Czy można zaprojektować algorytm, aby działał lepiej (tzn. Robił mniej domysłów, być może z mniejszą zmiennością liczby domysłów)? O ile lepiej mógłby to zrobić (tj. Jaki jest optymalny algorytm i jaka jest jego wydajność)?

Skuteczne rozwiązanie tego problemu może mieć istotne implikacje oszczędnościowe podczas strzelania do królika (ograniczonego do przeskakiwania na okrągłym torze) w ciemnym pokoju.

algorithms probability-theory randomized-algorithms

— Patrick87
źródło

Nie jestem pewien, czy strzelanie do królików to informatyka.

— Dave Clarke,

@DaveClarke Ale jeśli potrafisz strzelać do królików, rozwiązałeś problem zatrzymania królików.

— Patrick87,

@DaveClarke Żadne z nich nie strzela do satelitów w kosmos, ale obliczenia pozycji satelity są. To pytanie nie różni się całkowicie od kryptoanalizy.

— Gilles „SO- przestań być zły”

Po pierwsze, zakładam, że do

Ponadto stan dla jest ustawiony na wartość , gdzie jest wybierane losowo równomiernie z $f_S$ $f$ $f_S' = f_S \pm k$ $k$
${0, 1, 2, . . ., ⌊ n / 2 ⌋ - ((f_{S} - x) \mod n)}$ $\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\}$

masz na myśli

Ponadto stan dla jest ustawiony na wartość , gdzie jest wybierane losowo równomiernie z $f_S$ $f$ $f_S' = f_S + k \mod n$ $k$
${- | ⌊ \frac{n}{2} ⌋ - ((f_{S} - x) \mod n) |, \dots, - 1, 0, 1, 2, \dots, | ⌊ \frac{n}{2} ⌋ - ((f_{S} - x) \mod n) |}$ $\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\}$

W przeciwnym razie nie jest całkowicie jasne, czy zawsze obowiązuje i jak dokładnie . $f_S \in \{ 0, ..., n-1\}$ $f_S \pm k$

Dzięki temu problem sprowadza się do „zagubienia jak najwięcej”. Zauważ, że im bliżej strzelamy do królika, tym większy robi chmiel; w skrajnym przypadku mamy . Powoduje to jednolity przeskok między i , co w zasadzie całkowicie ponownie losowo ustawia pozycję królika. Z drugiej strony, jeśli przegapimy tak bardzo, jak to możliwe - przesunięcie o , królik faktycznie się nie rusza (!), A czarna skrzynka faktycznie nas aktualizuje na ten fakt. Dlatego możemy po prostu odwrócić się i zastrzelić królika. $f_S - x = \pm 1 \mod n$ $-(\lfloor n/2 \rfloor \pm 1)$ $(\lfloor n/2 \rfloor \pm 1)$ $f_S - x \mod n = \lfloor n/2 \rfloor$

Pozostaje nam znalezienie procedury zaginięcia w każdym ujęciu. Proponuję proste „wyszukiwanie binarne”. (Dogodnie pominę zaokrąglenie.) Postępuje z grubsza w następujący sposób:

Zresetuj i strzelaj w dowolnej pozycji, aż z odpowiedźTo wymaga stałej liczby kroków w oczekiwaniu. $(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$
Teraz wiemy, że poprzednia pozycja królika i że nie przesunęła się ona bardziej niż kroków w dowolnym kierunku. To w zasadzie zmniejsza o połowę naszą przestrzeń wyszukiwania w następnej iteracji, ponieważ królik musi znajdować się w pozycji $f_S$ $\frac{1}{4}n$ $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
Recurse: Strzelaj w pozycji . Z prawdopodobieństwem pozycja na którą wskoczył królik w kroku 1 i 2, leży w zakresie . W takim przypadku ponownie zmniejszyliśmy o połowę przestrzeń wyszukiwania. Z prawdopodobieństwem królik nie skoczył w tym zakresie, ale ponieważ wiemy, że , mamy takie same założenia jak w kroku (2) i dlatego nic nie tracicie. $f_S - n/2 \mod n$ $1/2$ $f_S'$ $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$ $1/2$ $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 \}$

Każdy krok wymaga spodziewanego czasu do sukcesu i zmniejsza o połowę przestrzeń wyszukiwania, dając ogólną oczekiwaną liczbę . $2 = \mathcal{O}(1)$ $\mathcal{O}(\log n)$

— HdM
źródło