Детерминированный алгоритм поиска на прямой: различия между версиями

== Основные результаты ==

Рассмотрим вариант с одним искателем. Если известно направление на цель, то решение тривиально, и относительная стоимость равна 1. Если известно расстояние до цели, то решение также оказывается простым. Нужно пройти это расстояние в одну сторону и, если цель не найдена, вернуться назад и идти в противоположную, пока цель не будет достигнута. В худшем случае стоимость этого алгоритма равна 3.

Условия задачи поиска можно также изменить; например, нужно найти точку в наборе из r лучей, где оптимальный алгоритм имеет стоимость <math>1 + 2r^r/(r - 1)^{r - 1}</math>, которая стремится к <math>1 + 2e \approx 6,44</math>.