Задача линейного поиска на прямой
- Задача линейного поиска на прямой** — это задача оптимального поиска неизвестной точки на числовой прямой, когда начальное положение и направление до цели неизвестны. Проблема была независимо предложена Ричардом Беллманом и другими исследователями.
- Примечание:** В англоязычной литературе эта задача известна как «linear search problem». В русскоязычных источниках термин «линейный поиск» чаще относится к алгоритму последовательного перебора в массиве, что может приводить к терминологической путанице.
- Постановка задачи
На числовой прямой расположен неподвижный объект, положение которого задано некоторым распределением вероятностей. Поисковик, способный двигаться с максимальной скоростью, равной единице, стартует из начала координат. Цель состоит в минимизации математического ожидания времени до обнаружения объекта. Предполагается, что направление движения можно менять мгновенно, а объект становится виден только в момент достижения точки его нахождения; это время и считается продолжительностью поиска.
Поскольку цель может находиться на произвольном расстоянии слева или справа от начала координат, оптимальная стратегия, как правило, представляет собой колебательное движение. Поисковик проходит расстояние *x₁* в одном направлении, возвращается в исходную точку, затем проходит расстояние *x₂* в противоположном направлении и так далее (где *xₙ* — длина *n*-го шага). Такой план действий называется траекторией поиска.
Общее решение задачи для произвольного распределения вероятностей до сих пор не найдено. Однако с помощью методов динамического программирования можно получить точное решение для любого дискретного распределения, а также приближённое — с заданной точностью — для любого распределения.
- История и результаты
Задача была решена Анатолем Беком и его соавторами (1970) в рамках теории антагонистических игр для двух игроков. Их минимаксная траектория основана на удвоении пройденного расстояния на каждом шаге, а оптимальная стратегия представляет собой смешанную, где расстояние увеличивается на фиксированную константу. Это решение предлагает стратегии, не зависящие от априорных предположений о распределении цели, и даёт верхнюю оценку для наихудшего случая. Результат был получен в контексте теории поиска и впоследствии обобщён на случай набора параллельных лучей.
Наихудший коэффициент конкурентности для детерминированного поиска на прямой равен 9, но его можно снизить до 4.6, используя рандомизированные стратегии. Демейн и другие исследователи предложили онлайн-алгоритмы, учитывающие стоимость изменения направления движения.
В 1990-х годах эти результаты были переоткрыты в компьютерных науках под названием **«задача о коровьей тропе»** (cow-path problem).
- См. также
- Последовательный поиск (линейный поиск в массиве)
- Поисковые игры
- Примечания