Задача линейного поиска - Linear search problem
В теории сложности вычислений , то задача линейного поиска является задачей поиска оптимального представлен Беллманом и независимо друг от друга по мнению Анатоля Бек .
Эта проблема
«Неподвижный укрыватель располагается на реальной линии в соответствии с известным распределением вероятностей. Поисковик, максимальная скорость которого равна единице, начинает с начала координат и желает обнаружить заградитель за минимально ожидаемое время. Предполагается, что поисковик может изменить направление его движения без какой-либо потери времени. Также предполагается, что ищущий не может видеть хайдера, пока не достигнет точки, в которой он находится, и время, прошедшее до этого момента, является продолжительностью игры ". Чтобы найти злоумышленник, ищущий должен пройти расстояние x 1 в одном направлении, вернуться в начало координат и пройти расстояние x 2 в другом направлении и т. Д. (Длина n-го шага обозначается x n ) , и сделать это оптимальным образом. (Однако оптимальное решение не обязательно должно иметь первый шаг и может начинаться с бесконечного числа небольших «колебаний».) Эта проблема обычно называется задачей линейного поиска, а план поиска называется траекторией. Это привлекло много исследований, некоторые из которых совсем недавно.
Проблема линейного поиска для общего распределения вероятностей не решена. Однако существует алгоритм динамического программирования , который дает решение для любого дискретного распределения, а также приближенное решение для любого распределения вероятностей с любой желаемой точностью.
Задача линейного поиска была решена Анатолем Беком и Дональдом Дж. Ньюманом (1970) как игра двух лиц с нулевой суммой. Их минимаксная траектория состоит в удвоении расстояния на каждом шаге, а оптимальная стратегия представляет собой смесь траекторий, которые увеличивают расстояние на некоторую фиксированную константу. Это решение дает стратегии поиска, которые не чувствительны к предположениям о распределении цели. Таким образом, он также представляет собой верхнюю границу для наихудшего сценария. Это решение было получено в рамках с онлайн алгоритма по Шмуэль Гал , который также обобщил этот результат на множество параллельных лучей. Наилучший коэффициент конкуренции в Интернете для поиска в строке - 9, но его можно снизить до 4,6, используя рандомизированную стратегию. Demaine et al. предоставили онлайн-решение со стоимостью обращения.
Эти результаты были заново открыты в 1990-х компьютерщиками как проблема коровьего пути .