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

Question

Предположим, что у нас есть черная коробка $ f $, которую мы можем запросить и сбросить. Когда мы сбрасываем $ f $, состояние $ f_s $ of $ f $ установлено на элемент, выбранный, выбранным случайно из набора $$ {0, 1, ..., n - 1 } $$, где $ n $ фиксирован и известен как данный $ f $. Чтобы запросить $ f $, элемент $ x $ (га) MOD N $. Кроме того, состояние $ f_s $ of $ 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 $ (указано без доказательства).

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

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

Answer 1

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

Кроме того, состояние $ f_s $ of $ f $ установлено значение $ f_s '= f_s pm k $, где $ k $ выбирается случайно случайно из $$ {0, 1, 2, ..., lfloor n/2 rfloor - ((f_s - x) mod n) } $$

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

Кроме того, состояние $ f_s $ of $ 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. Сбросьте и стреляйте в произвольную позицию, пока не получите из Blackbox ответ $ (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. Выполнение: стреляйте в позиции $ f_s - n/2 mod n $. С вероятностью $ 1/2 $, позиция $ f_s '$' кролик запрыгнул на шаге 1 и 2, в диапазоне $ {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) и поэтому ничего не теряют.

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