Детерминированный алгоритм поиска на прямой
Ключевые слова и синонимы
Поиск точки на прямой; поиск по одному измерению; поиск прямой (или плоскости) с известным наклоном на плоскости (или в трехмерном пространстве)
Постановка задачи
Задача заключается в разработке стратегии достижения неизвестной целевой точки искателем (или несколькими искателями), находящимся изначально в некоторой начальной точке на прямой. Целевая точка обнаруживается только тогда, когда искатель находится в ней. Существует несколько вариантов задачи, зависящих от информации о целевой точке, количества параллельно работающих искателей и способов их взаимодействия, а также от типа алгоритма. Стоимость алгоритма поиска определяется как расстояние, пройденное до нахождения точки, по отношению к расстоянию от начальной точки до целевой. Далее будут рассматриваться только детерминированные алгоритмы.
Основные результаты
Рассмотрим вариант с одним искателем. Если известно направление на цель, то решение тривиально, и относительная стоимость равна 1. Если известно расстояние до цели, то решение также оказывается простым. Нужно пройти это расстояние в одну сторону и, если цель не найдена, вернуться назад и идти в противоположную, пока цель не будет достигнута. В худшем случае стоимость этого алгоритма равна 3.
Если никакая информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается [math]\displaystyle{ 1, 2, 4, 8, ..., 2^i }[/math] шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами.
Если число искателей больше одного – скажем, равно m – то решение является тривиальным, если у них имеется мгновенная связь друг с другом. Два искателя идут в противоположных направлениях, а прочие остаются в начальной точке. Тот искатель, который нашел цель, сообщает об этом всем остальным. Таким образом, стоимость для всех искателей равна m + 2, если предположить, что все они должны добраться до цели. При отсутствии связи решение усложняется, и оптимальный алгоритм для этой задачи пока не найден.
Условия задачи поиска можно также изменить; например, нужно найти точку в наборе из r лучей, где оптимальный алгоритм имеет стоимость [math]\displaystyle{ 1 + 2r^r/(r - 1)^{r - 1} }[/math], которая стремится к [math]\displaystyle{ 1 + 2e \approx 6,44 }[/math].
Возможны и другие вариации. Например, если нас интересует средний случай, то можно вывести вероятностное распределение для нахождения целевой точки, получая парадоксальные результаты, такие как оптимальный алгоритм конечного расстояния с бесконечным числом точек разворота. С другой стороны, в худшем случае, если с каждым разворотом связана стоимость d, оптимальное расстояние равно 9 OPT + 2d, где OPT – расстояние от начала координат до целевой точки. Этот последний случай был решен и для задачи с r лучами.
Аналогичная идея удвоения на каждом шаге может быть распространена на поиск целевой точки в неизвестном простом многоугольнике или на поиск прямой с известным наклоном на плоскости. Спиральный поиск может быть использован для нахождения произвольной прямой на плоскости со стоимостью 13,81. Оптимальность этого результата пока остается недоказанной.
Применение
Данная задача является базовым элементом навигации роботов в неизвестной среде. Например, она возникает, когда роботу необходимо найти, где заканчивается стена, если он может только ощущать стену, но не видеть ее.
См. также
Литература
1. Alpern, S., Gal, S.: The Theory of Search Games and Rendevouz. Kluwer Academic Publishers, Dordrecht (2003)
2. Baeza-Yates, R., Culberson, J., Rawlins, G.: Searching in the Plane. Inf. Comput. 106(2), 234-252 (1993) Preliminary version as Searching with uncertainty. In: Karlsson, R., Lingas, A. (eds.) Proceedings SWAT 88, First Scandinavian Workshop on Algorithm Theory. Lecture Notes in Computer Science, vol. 318, pp. 176-189. Halmstad, Sweden (1988)
3. Baeza-Yates, R., Schott, R.: Parallel searching in the plane. Comput. Geom. Theor. Appl. 5,143-154 (1995)
4. Blum, A., Raghavan, P., Schieber, B.: Navigating in Unfamiliar Geometric Terrain. In: On Line Algorithms, pp. 151-155, DI-MACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, Providence RI (1992) Preliminary Version in STOC 1991, pp. 494-504
5. Demaine, E., Fekete, S., Gal, S.: Online searching with turn cost. Theor. Comput. Sci. 361, 342-355 (2006)
6. Gal, S.: Minimax solutions for linear search problems. SIAM J. Appl. Math. 27,17-30(1974)
7. Gal, S.: Search Games, pp. 109-115, 137-151, 189-195. Academic Press, New York (1980)
8. Hipke, C., Icking, C., Klein, R., Langetepe, E.: How to Find a point on a line within a Fixed distance. Discret. Appl. Math. 93,67-73 (1999)
9. Kao, M.-Y., Reif, J.H., Tate, S.R.: Searching in an unknown environment: an optimal randomized algorithm for the cow-path problem. Inf. Comput. 131(1), 63-79 (1996) Preliminary version in SODA'93, pp. 441-447
10. Lopez-Ortiz, A.: On-Line Target Searching in Bounded and Unbounded Domains: Ph.D. Thesis, Technical Report CS-96-25, Dept. of Computer Sci., Univ. of Waterloo (1996)
11. Lopez-Ortiz, A., Schuierer, S.: The Ultimate Strategy to Search on m Rays? Theor. Comput. Sci. 261 (2), 267-295 (2001)
12. Papadimitriou, C.H., Yannakakis, M.: Shortest Paths without a Map. Theor. Comput. Sci.84,127-150(1991) Preliminary version in ICALP '89
13. Schuierer, S.: Lower bounds in on-line geometric searching. Comput. Geom. 18,37-53 (2001)