4551
правка
Детерминированный алгоритм поиска на прямой: различия между версиями
Перейти к навигации
Перейти к поиску
м
Детерминированный алгоритм поиска на прямой (посмотреть исходный код)
Версия от 23:29, 27 октября 2023
, 27 октября 2023→Основные результаты
Irina (обсуждение | вклад) (Новая страница: «== Ключевые слова и синонимы == Поиск точки на прямой; поиск по одному измерению; поиск прямой (или плоскости) с известным наклоном на плоскости (или в трехмерном пространстве) == Постановка задачи == Задача заключается в разработке стратегии достижения н...») |
Irina (обсуждение | вклад) |
||
| Строка 9: | Строка 9: | ||
Если информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм построен по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается 1, 2, 4, 8, ... , | Если информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм построен по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йетсом и коллегами. | ||
| Строка 15: | Строка 15: | ||
Условия задачи поиска можно также изменить; например, нужно найти точку в наборе из r лучей, где оптимальный алгоритм имеет стоимость 1 + | Условия задачи поиска можно также изменить; например, нужно найти точку в наборе из r лучей, где оптимальный алгоритм имеет стоимость <math>1 + 2r^r/(r - 1)^{r - 1}</math>, которая стремится к <math>1 + 2e \approx 6,44</math>. | ||