4824
правки
Детерминированный алгоритм поиска на прямой: различия между версиями
Материал из WEGA
Детерминированный алгоритм поиска на прямой (посмотреть исходный код)
Версия от 09:15, 8 декабря 2023
, 8 декабря 2023→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| (не показаны 3 промежуточные версии этого же участника) | |||
| Строка 3: | Строка 3: | ||
== Постановка задачи == | == Постановка задачи == | ||
Задача заключается в разработке стратегии достижения неизвестной целевой точки искателем (или несколькими искателями), находящимся изначально в некоторой начальной точке на прямой. Целевая точка обнаруживается только тогда, когда искатель находится в ней. Существует несколько вариантов задачи, зависящих от информации о целевой точке, количества параллельно работающих искателей и | Задача заключается в разработке стратегии достижения неизвестной целевой точки искателем (или несколькими искателями), находящимся изначально в некоторой начальной точке на прямой. Целевая точка обнаруживается только тогда, когда искатель находится в ней. Существует несколько вариантов задачи, зависящих от информации о целевой точке, количества параллельно работающих искателей и способов их взаимодействия, а также от типа алгоритма. Стоимость алгоритма поиска определяется как расстояние, пройденное до нахождения точки, по отношению к расстоянию от начальной точки до целевой. Далее будут рассматриваться только детерминированные алгоритмы. | ||
== Основные результаты == | == Основные результаты == | ||
| Строка 9: | Строка 9: | ||
Если информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами. | |||
Если никакая информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами. | |||
Если число искателей больше одного – скажем, равно m – то решение является тривиальным, если у них имеется мгновенная связь друг с другом. Два искателя идут в противоположных направлениях, а прочие остаются в начальной точке. Тот искатель, который нашел цель, сообщает об этом всем остальным. Таким образом, стоимость для всех искателей равна m + 2, если предположить, что все они должны добраться до цели. При отсутствии связи решение усложняется, и оптимальный алгоритм для этой задачи пока не найден. | Если число искателей больше одного – скажем, равно m – то решение является тривиальным, если у них имеется мгновенная связь друг с другом. Два искателя идут в противоположных направлениях, а прочие остаются в начальной точке. Тот искатель, который нашел цель, сообщает об этом всем остальным. Таким образом, стоимость для всех искателей равна m + 2, если предположить, что все они должны добраться до цели. При отсутствии связи решение усложняется, и оптимальный алгоритм для этой задачи пока не найден. | ||
| Строка 18: | Строка 21: | ||
Возможны и другие вариации. Например, если нас интересует средний случай, то можно вывести вероятностное распределение для нахождения целевой точки, получая парадоксальные результаты, как оптимальный алгоритм конечного расстояния с бесконечным числом точек разворота. С другой стороны, в худшем случае, если с каждым разворотом связана стоимость d, оптимальное расстояние равно 9 OPT + 2d, где OPT – расстояние от начала координат до целевой точки. Этот последний случай был решен и для задачи с r лучами. | |||
Возможны и другие вариации. Например, если нас интересует средний случай, то можно вывести вероятностное распределение для нахождения целевой точки, получая парадоксальные результаты, такие как оптимальный алгоритм конечного расстояния с бесконечным числом точек разворота. С другой стороны, в худшем случае, если с каждым разворотом связана стоимость d, оптимальное расстояние равно 9 OPT + 2d, где OPT – расстояние от начала координат до целевой точки. Этот последний случай был решен и для задачи с r лучами. | |||
Аналогичная идея удвоения на каждом шаге может быть распространена на поиск целевой точки в неизвестном простом многоугольнике или на поиск прямой с известным наклоном на плоскости. Спиральный поиск может быть использован для нахождения произвольной прямой на плоскости со стоимостью 13,81. Оптимальность этого результата пока остается недоказанной. | Аналогичная идея удвоения на каждом шаге может быть распространена на поиск целевой точки в неизвестном простом многоугольнике или на поиск прямой с известным наклоном на плоскости. Спиральный поиск может быть использован для нахождения произвольной прямой на плоскости со стоимостью 13,81. Оптимальность этого результата пока остается недоказанной. | ||
== Применение == | ==Применение == | ||
Данная задача является базовым элементом навигации роботов в неизвестной среде. Например, она возникает, когда роботу необходимо найти, где заканчивается стена, если он может только ощущать стену, но не видеть ее. | Данная задача является базовым элементом навигации роботов в неизвестной среде. Например, она возникает, когда роботу необходимо найти, где заканчивается стена, если он может только ощущать стену, но не видеть ее. | ||
== См. также == | ==См. также== | ||
* [[Рандомизированный поиск по лучам или на прямой]] | *[[Рандомизированный поиск по лучам или на прямой]] | ||
== Литература == | ==Литература== | ||
1. Alpern, S., Gal, S.: The Theory of Search Games and Rendevouz. Kluwer Academic Publishers, Dordrecht (2003) | 1. Alpern, S., Gal, S.: The Theory of Search Games and Rendevouz. Kluwer Academic Publishers, Dordrecht (2003) | ||
