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\}$$ gdzie $n$ jest ustalone i znane dla danego $f$ . Do zapytania $f$ , element $x$ (przypuszczenie) z $$\{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$$f$$f_S' = f_S \pm k$$k$ $$\{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.

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, ..., \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$

$$\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:

1. 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\}.$
2. 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 \}$
3. 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)$