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

Если информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йетсом и коллегами.

Если число искателей больше одного – скажем, равно m – то решение является тривиальным, если у них имеется мгновенную связь друг с другом. Два искателя идут в противоположных направлениях, а прочие остаются в начале пути. Тот искатель, который нашел цель, сообщает об этом всем остальным. Таким образом, стоимость для всех искателей равна m + 2, если предположить, что все они должны добраться до цели. При отсутствии связи решение усложняется, и оптимальный алгоритм для этой задачи пока не найден.

Возможны и другие вариации. Например, если нас интересует средний случай, то можно иметь вероятностное распределение для нахождения целевой точки, получая парадоксальные результаты, как оптимальный алгоритм конечного расстояния с бесконечным числом точек разворота. С другой стороны, в худшем случае, если с каждым разворотом связана стоимость d, оптимальное расстояние равно 9 OPT + 2d, где OPT – расстояние от начала координат до целевой точки. Этот последний случай был решен и для задачи с r лучами.

Аналогичная идея удвоения на каждом шаге может быть распространена на поиск целевой точки в неизвестном простом многоугольнике или на поиск прямой с известным наклоном на плоскости. Такой же спиральный поиск может быть использован для нахождения произвольной прямой на плоскости со стоимостью 13,81. Оптимальность этого результата пока остается недоказанной.