4551
правка
Детерминированный алгоритм поиска на прямой: различия между версиями
Перейти к навигации
Перейти к поиску
м
Детерминированный алгоритм поиска на прямой (посмотреть исходный код)
Версия от 16:12, 8 декабря 2023
, 8 декабря 2023→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Если информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами. | |||
Если никакая информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами. | |||
| Строка 23: | Строка 26: | ||
Аналогичная идея удвоения на каждом шаге может быть распространена на поиск целевой точки в неизвестном простом многоугольнике или на поиск прямой с известным наклоном на плоскости. Спиральный поиск может быть использован для нахождения произвольной прямой на плоскости со стоимостью 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) | ||