Algoritmo para perseguir un objetivo en movimiento

Question

Supongamos que tenemos una caja de negro $ f $ cual podemos consultar y restablecer. Cuando reiniciamos $ f $, $ f_S los estatales de $ $ $ f se establece en un elemento elegido de manera uniforme al azar del conjunto $$ \ {0, 1, ..., n - 1 \} $$ $ donde n $ es fijo y conocido por dado $ f $. Para consulta $ f $, un elemento x $ $ (la suposición) de $$ \ {0, 1, ..., n - 1 \} $$ se proporciona, y el valor devuelto es $ (f_S - x) \ mod n $. Además, los $ f_S Estado $ de $ f $ se establece en un valor $ f_S'= f_S \ pm k $, en donde se selecciona $ k $ uniformemente al azar de $$ \ {0, 1, 2, ..., \ lfloor n / 2 \ rfloor - ((f_S - x) \ mod n) \} $$

Al hacer conjeturas uniformemente al azar con cada consulta, se podría esperar a tener que hacer conjeturas $ n $ antes de conseguir $ f_S = x $, con una varianza $ n ^ 2 -. N $ (declarado sin pruebas)

Puede ser un algoritmo diseñado para hacer mejor (es decir, hacer que un menor número de conjeturas, posiblemente con menos variación en el número de conjeturas)? Cuánto mejor podría hacerlo do (es decir, lo que es un algoritmo óptimo, y lo que es su rendimiento)?

Una solución eficaz a este problema podría tener importantes implicaciones para el tiroteo en un conejo (confinado a saltar en una pista circular) en un cuarto oscuro. Ahorro de costes

Answer 1

First of all, I will assume that by

Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S \pm k$, where $k$ is selected uniformly at random from $$\{0, 1, 2, ..., \lfloor n/2 \rfloor - ((f_S - x) \mod n)\} $$

you actually mean

Additionally, the state $f_S$ of $f$ is set to a value $f_S' = f_S + k \mod n$, where $k$ is selected uniformly at random from $$\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\} $$

Otherwise, it is not entirely clear that $f_S \in \{ 0, ..., n-1\}$ always holds and how exactly $f_S \pm k$ behaves.

Using this, the problem basically comes down to "missing as much as possible". Observe that the closer we shoot the rabbit, the larger hops he makes; in the extreme case we have $f_S - x = \pm 1 \mod n$. This results in a uniform hop between $ -(\lfloor n/2 \rfloor \pm 1)$ and $ (\lfloor n/2 \rfloor \pm 1)$, which basically completely randomizes the position of the rabbit again. On the other hand, if we miss as badly as possible - by an offset of $f_S - x \mod n = \lfloor n/2 \rfloor$, the rabbit actually does not move at all (!) and the black box actually updates us on this fact. Therefore, we can just turn around and shoot the rabbit.

We are left with finding a procedure for missing increasingly in each shot. I propose a simple "binary search". (I will conveniently omit the rounding.) It proceeds roughly as follows:

1. Reset and shoot at an arbitrary position until you get from the blackbox the answer $(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$ This takes a constant amount of steps in expectation.
2. Now, we know that the rabbit's past position $f_S$, and that it did not move more than $\frac{1}{4}n$ steps in either direction. This basically halves our search space in the next iteration, since the rabbit has to be at a position $f_S' \in \{ (f_S - \frac{1}{4}n) \mod n, ..., f_S, ..., (f_S + \frac{1}{4}n) \mod n \}$
3. Recurse: Shoot at position $f_S - n/2 \mod n$. With probability $1/2$, the position $f_S'$ the rabbit jumped onto in step 1&2 lies the range $\{ f_S - \frac{1}{8}n, ..., f_S, ..., f_S + \frac{1}{8}n \}$. In that case we halved the search space once more. With probability $1/2$, the rabbit did not jump in that range, but since we know that $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 \}$, we have the same assumptions as in step (2) and therefore lose nothing.

Each step needs $2 = \mathcal{O}(1)$ expected time to succeed and halves the search space, yielding an overall of $\mathcal{O}(\log n)$ expected number of steps.