Задача линейного поиска
В теории сложности вычислений задача линейного поиска — это задача оптимального поиска, введенная Ричардом Э. Беллманом. [1] и независимо рассмотрено Анатолем Беком . [2] [3] [4]
Проблема
[ редактировать ]«Неподвижное укрытие находится на реальной линии в соответствии с известным распределением вероятностей . Искатель, максимальная скорость которого равна единице, стартует из начала координат и желает обнаружить укрытие за минимальное ожидаемое время. Предполагается, что искатель может изменить направление его движения без какой-либо потери времени. Предполагается также, что искатель не может увидеть скрывающегося до тех пор, пока он фактически не достигнет точки, в которой находится скрывающийся, а время, прошедшее до этого момента, является продолжительностью игры».
Задача состоит в том, чтобы найти скрывающегося в кратчайшие сроки. Как правило, поскольку искатель может находиться по обе стороны от искателя и на произвольном расстоянии, искатель должен колебаться вперед и назад, т. е. искатель должен пройти расстояние x 1 в одном направлении, вернуться в исходное положение и пройти это расстояние. x 2 в другую сторону и т. д. (длину n-го шага обозначим x n ). (Однако оптимальное решение не обязательно должно иметь первый шаг и может начинаться с бесконечного числа небольших «колебаний».) Эту задачу обычно называют задачей линейного поиска, а план поиска — траекторией.
Задача линейного поиска общего распределения вероятностей не решена. [5] Однако существует алгоритм динамического программирования , который дает решение для любого дискретного распределения. [6] а также приближенное решение для любого распределения вероятностей с любой желаемой точностью. [7]
Задача линейного поиска была решена Анатолем Беком и Дональдом Дж. Ньюманом (1970) как игра двух лиц с нулевой суммой. Их минимаксная траектория заключается в удвоении расстояния на каждом шаге, а оптимальная стратегия — это смесь траекторий, которые увеличивают расстояние на некоторую фиксированную константу. [8] Это решение дает стратегии поиска, которые не чувствительны к предположениям относительно распределения цели. Таким образом, он также представляет собой верхнюю границу для наихудшего сценария. Это решение было получено в рамках онлайн-алгоритма Шмуэлем Галем , который также обобщил этот результат на набор совпадающих лучей. [9] Наилучший коэффициент онлайн-конкурентности для поиска по строке равен 9, но его можно снизить до 4,6, используя рандомизированную стратегию. Демейн и др. дал онлайн-решение со стоимостью поворота. [10]
Эти результаты были вновь открыты в 1990-х годах учеными-компьютерщиками как задача о коровьих путях .
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ Беллман, Ричард (июль 1963 г.), «Проблема 63-9. Оптимальный поиск», SIAM Review , 5 (3): 274, JSTOR 2027629
- ^ Бек, Анатоль (декабрь 1964 г.), «О задаче линейного поиска», Израильский математический журнал , 2 : 221–228, doi : 10.1007/BF02759737
- ^ Бек, Анатоль (июнь 1965 г.), «Подробнее о задаче линейного поиска», Israel Journal of Mathematics , 3 : 61–70, doi : 10.1007/BF02760028
- ^ Бек, Анатоль; Бек, Мика (декабрь 1986 г.), «Проблема линейного поиска снова возникает», Israel Journal of Mathematics , 53 : 365–372, doi : 10.1007/BF02786568
- ^ Альперн, Стив; Гал, Шмуэль (2003), «Глава 8. Поиск на бесконечной линии», Теория поисковых игр и рандеву, Часть 2 , Международная серия по исследованию операций и науке управления, том. 55, стр. 123–144, номер документа : 10.1007/0-306-48212-6_8 . На стр. 124, Альперн и Гал пишут, что «ни один алгоритм решения задачи для общей функции распределения вероятностей не был найден в течение примерно 37 лет с момента первого представления LSP».
- ^ Брюсс, Ф. Томас; Робертсон, Джеймс Б. (декабрь 1988 г.), «Обзор проблемы линейного поиска» (PDF) , The Mathematical Scientist , 13 : 75–89, заархивировано из оригинала (PDF) 18 августа 2021 г.
- ^ Альперн, Стив; Гал, Шмуэль (2003), «Раздел 8.7. Алгоритм динамического программирования для LSP», Теория поисковых игр и рандеву, Часть 2 , Международная серия по исследованию операций и науке управления, том. 55, стр. 139–144, номер документа : 10.1007/0-306-48212-6_8.
- ^ Бек, Анатоль; Ньюман, Дональд Дж. (декабрь 1970 г.), «Еще больше о проблеме линейного поиска», Israel Journal of Mathematics , 8 : 419–429, doi : 10.1007/BF02798690
- ^ Галь, Шмуэль (1980), Поисковые игры , Academic Press
- ^ Демейн, Эрик Д.; Фекете, Шандор; Гал, Шмуэль (сентябрь 2006 г.), «Онлайн-поиск со стоимостью хода», Theoretical Computer Science , 361 (2–3): 342–355, arXiv : cs/0406045 , doi : 10.1016/j.tcs.2006.05.018