Задача линейного поиска - Linear search problem

В теория сложности вычислений, то задача линейного поиска - задача оптимального поиска, представленная Ричард Э. Беллман[1] (независимо рассмотрено Анатоль Бек ).[2][3][4]

Проблема

«Неподвижный укрыватель располагается на реальной линии в соответствии с известным распределением вероятностей. Поисковик, максимальная скорость которого равна единице, начинает с начала координат и желает обнаружить заградитель за минимально ожидаемое время. Предполагается, что поисковик может изменить направление его движения без какой-либо потери времени. Также предполагается, что ищущий не может видеть хайдера, пока он не достигнет точки, в которой он находится, и время, прошедшее до этого момента, является продолжительностью игры ". Чтобы найти укрывателя, ищущий должен пройти расстояние x1 в одном направлении, вернуться в начало координат и пройти расстояние x2 в обратном направлении и т. д. (длина n-го шага обозначается xп), и сделать это оптимальным образом. (Однако оптимальное решение не обязательно должно иметь первый шаг и может начинаться с бесконечного числа небольших «колебаний».) Эта проблема обычно называется задачей линейного поиска, а план поиска называется траекторией. Это привлекло много исследований, некоторые из которых совсем недавно.[когда? ]

Проблема линейного поиска для общего распределения вероятностей не решена.[5] Однако существует динамическое программирование алгоритм, который производит решение для любого дискретного распределения[6] а также приближенное решение для любого распределения вероятностей с любой желаемой точностью.[7]

Задача линейного поиска была решена Анатолем Беком и Дональд Дж. Ньюман (1970) как игра с нулевой суммой для двух человек. Их минимакс траектория состоит в том, чтобы удвоить расстояние на каждом шаге, и оптимальная стратегия представляет собой смесь траекторий, которые увеличивают расстояние на некоторую фиксированную константу.[8] Это решение дает стратегии поиска, которые не чувствительны к предположениям относительно распределения цели. Таким образом, он также представляет собой верхнюю границу для наихудшего сценария. Это решение было получено в рамках онлайн алгоритм к Шмуэль Гал, который также обобщил этот результат на набор параллельных лучей.[9] Лучший онлайн конкурентное соотношение для поиска в строке - 9, но его можно уменьшить до 4,6 с помощью рандомизированной стратегии. Demaine et al. предоставили онлайн-решение со стоимостью обращения.[10]

Эти результаты были заново открыты в 1990-х компьютерными учеными как проблема пути коровы.

Смотрите также

Рекомендации

  1. ^ Р. Беллман. Задача оптимального поиска, SIAM Rev. (1963).
  2. ^ А. Бек. О задаче линейного поиска, Israel J. Mathematics (1964).
  3. ^ А. Бек. Подробнее о задаче линейного поиска, Israel J. Mathematics (1965).
  4. ^ А. Бек и М. Бек. Проблема линейного поиска снова актуальна, Израэль Дж. Математик (1986).
  5. ^ Альперн, Стив; Гал, Шмуэль (2003), «Глава 8. Поиск на бесконечной прямой», Теория поисковых игр и рандеву, часть 2, Международная серия исследований операций и менеджмента, 55, стр. 123–144, Дои:10.1007/0-306-48212-6_8. На стр. 124 Альперн и Гал пишут, что «не было найдено ни одного алгоритма для решения задачи для общей функции распределения вероятностей в течение примерно 37 лет с момента первого представления LSP».
  6. ^ Ф. Т. Брюсс и Дж. Б. Робертсон. Обзор задачи линейного поиска. Математика. Sci. 13, 75-84, (1988).
  7. ^ С. Альперн и С. Гал. Теория поисковых игр и рандеву. Спрингер (2003): 139-143.
  8. ^ А. Бек, Д. Дж. Новичок. Еще о проблеме линейного поиска. Israel J. Math. (1970).
  9. ^ С. Гал. ПОИСК ИГР, Academic Press (1980).
  10. ^ E. Demaine, S. Fekete и S. Gal. Интернет-поиск со стоимостью поворота. Теоретическая информатика (2006).