Алгоритм преследования движущейся цели

Предположим, что у нас есть черный ящик который мы можем запросить и сбросить. Когда мы сбрасываем , состояние для устанавливается произвольно выбранному элементу из набора где фиксировано и известно для данного . Для запроса предоставляется элемент (предположение) из , а возвращаемое значение равно . Кроме того, состояние для устанавливается равным значению , где выбирается случайным образом изе е С е { 0 , 1 , . , , , П - 1 } п е е х { 0 , 1 , . , , , n - 1 } ( f S - x $f$$f$$f_S$$f$

$$\{0, 1, ..., n - 1\}$$ $n$$f$$f$$x$ $$\{0, 1, ..., n - 1\}$$ е S е е ' S = F S ± к к { 0 , 1 , 2 , . , , , ⌊ n / 2 ⌋ - ( ( f S - x $(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)\}$$

Делая равномерно случайные догадки с каждым запросом, можно было бы ожидать сделать $n$ догадок, прежде чем получить $f_S = x$ с дисперсией $n^2 - n$ (заявлено без доказательства).

Может ли алгоритм быть спроектирован так, чтобы он работал лучше (т. Е. Создавал меньше догадок, возможно, с меньшим разбросом в количестве догадок)? Насколько лучше это сделать (т. Е. Каков оптимальный алгоритм и какова его производительность)?

Эффективное решение этой проблемы может иметь важные последствия для экономии при стрельбе по кролику (ограниченному прыжками по круговой дорожке) в темной комнате.

Прежде всего, я предполагаю, что

Кроме того, состояние для устанавливается равным значению , где выбирается случайным образом равномерно из$f_S$$f$$f_S' = f_S \pm k$$k$

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

вы на самом деле имеете в виду

Кроме того, состояние для устанавливается равным значению , где выбирается случайным образом из$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\}$$

В противном случае не совсем ясно, что всегда выполняется и как именно ведет себя.$f_S \in \{ 0, ..., n-1\}$$f_S \pm k$

Используя это, проблема в основном сводится к тому, чтобы «пропустить как можно больше». Заметьте, что чем ближе мы стреляем в кролика, тем больше хмеля он делает; в крайнем случае мы имеем . Это приводит к равномерному переходу между и , что в основном снова полностью рандомизирует положение кролика. С другой стороны, если мы пропустим настолько сильно, насколько это возможно - из-за смещения , кролик фактически не двигается вообще (!), И черный ящик фактически обновляет нас на этот факт. Поэтому мы можем просто развернуться и пристрелить кролика.$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$

Нам остается найти процедуру пропуска в каждом кадре. Я предлагаю простой «бинарный поиск». (Я удобно опущу округление.) Это происходит примерно следующим образом:

1. Сброс и стрельба в произвольном положении, пока вы не получите из черного ящика ответЭто требует постоянного количества шагов в ожидании.$(f_S - x \mod n) \in \{ \frac{1}{4}n, ..., \frac{3}{4}n\}.$
2. Теперь мы знаем, что кролик в прошлом положении и что он не двигался более чем на шагов в любом направлении. Это в основном вдвое уменьшает наше пространство поиска на следующей итерации, поскольку кролик должен находиться в позиции$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: стрелять в позиции . С вероятностью позиция на которую кролик прыгнул на 1 и 2, лежит в диапазоне . В этом случае мы вдвое сократили пространство поиска. С вероятностью , кролик не прыгнул в этом диапазоне, но так как мы знаем, что , у нас есть те же предположения, что и на шаге (2) и поэтому ничего не теряешь.$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 \}$

Каждый шаг требует ожидаемого времени для успешного завершения и делит пополам пространство поиска, что дает общее ожидаемое количество шагов.$2 = \mathcal{O}(1)$$\mathcal{O}(\log n)$