Jump to content

Задача линейного поиска

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

Проблема

[ редактировать ]

«Неподвижное укрытие находится на реальной линии в соответствии с известным распределением вероятностей . Искатель, максимальная скорость которого равна единице, стартует из начала координат и желает обнаружить укрытие за минимальное ожидаемое время. Предполагается, что искатель может изменить направление его движения без какой-либо потери времени. Предполагается также, что искатель не может увидеть скрывающегося до тех пор, пока он фактически не достигнет точки, в которой находится скрывающийся, а время, прошедшее до этого момента, является продолжительностью игры».

Задача состоит в том, чтобы найти скрывающегося в кратчайшие сроки. Как правило, поскольку искатель может находиться по обе стороны от искателя и на произвольном расстоянии, искатель должен колебаться вперед и назад, т. е. искатель должен пройти расстояние x 1 в одном направлении, вернуться в исходное положение и пройти это расстояние. x 2 в другую сторону и т. д. (длину n-го шага обозначим x n ). (Однако оптимальное решение не обязательно должно иметь первый шаг и может начинаться с бесконечного числа небольших «колебаний».) Эту задачу обычно называют задачей линейного поиска, а план поиска — траекторией.

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

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

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

См. также

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