Задача линейного поиска на прямойВ русскоязычной литературе под линейным поиском обычно подразумевается прямой перебор в массиве данных. () — задача оптимального поиска точки на прямой, когда неизвестно расстояние до точки от начала поиска (начала координат) и неизвестно, в какой стороне это значение находится. Задачу предложил Ричард Беллман. Независимо задачу рассматривал .
Задача «Неподвижный объект, который нужно найти, находится на числовой прямой, его положение известно с определённой вероятностью. Искатель, чья максимальная скорость равна единице, начинает движение от начала координат и стремится найти объект за минимальное ожидаемое время. Предполагается, что искатель может менять направление движения мгновенно. Предполагается также, что искатель не видит объект до тех пор, пока не достигнет точки его нахождения, и время, потраченное на поиск, считается продолжительностью игры».
Задача состоит в том, чтобы найти объект за наименьшее возможное время. В общем случае, поскольку объект может находиться по любую сторону от искателя и на произвольном расстоянии, искателю приходится совершать колебательные движения. То есть, искатель проходит расстояние x1 в одном направлении, возвращается в начало координат и проходит расстояние x2 в другом направлении и так далее (длина n-го шага будем обозначать xn). Задача называется задачей линейного поиска, а план поиска — траекторией.
Задача линейного поиска на прямой для распределения вероятностей общего вида не решена. Однако, существует алгоритм динамического программирования, который даёт решение для любого дискретного распределения, а также приблизительное решение с желаемой точностью для любого распределения вероятностей .
Задача линейного поиска на прямой была решена Анатолем Беком и (1970) как игра с нулевой суммой для двух игроков. Их минимаксная траектория заключается в удвоении расстояния на каждом шаге, а оптимальная стратегия представляет собой смесь траекторий, увеличивающих расстояние на некоторую фиксированную константу. Это решение предлагает стратегии поиска, не зависящие от предположений о распределении цели. Таким образом, оно также представляет собой верхнюю границу для наихудшего сценария. Это решение было получено в рамках , который также обобщил этот результат на набор параллельных лучей. Лучшее для поиска на прямой составляет 9, но его можно уменьшить до 4,6 с помощью рандомизированной стратегии. Демейн и соавторы предложили онлайн-решение с учётом стоимости поворота.
Эти результаты были заново открыты в 1990-х годах учеными-компьютерщиками как задача о пути коровы.
См. также Линейный поиск Игра на поиск
Примечания
Категория:Вычислительные задачи Категория:Теория оптимизации