4551
правка
Детерминированный алгоритм поиска на прямой: различия между версиями
Перейти к навигации
Перейти к поиску
м
Детерминированный алгоритм поиска на прямой (посмотреть исходный код)
Версия от 16:15, 8 декабря 2023
, 8 декабря 2023→Основные результаты
Irina (обсуждение | вклад) мНет описания правки |
Irina (обсуждение | вклад) |
||
| Строка 11: | Строка 11: | ||
Если никакая информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами. | Если никакая информация о цели неизвестна, то решение не является тривиальным. Оптимальный алгоритм строится по линейной логарифмической спирали со степенью 2 и имеет стоимость 9 плюс члены низшего порядка. То есть в каждую сторону поочередно делается <math>1, 2, 4, 8, ..., 2^i</math> шагов, каждый раз возвращаясь в начало координат, пока цель не будет найдена. Этот результат был впервые обнаружен Гэлом и независимо переоткрыт Баэса-Йейтсом и коллегами. | ||
Если число искателей больше одного – скажем, равно m – то решение является тривиальным, если у них имеется мгновенная связь друг с другом. Два искателя идут в противоположных направлениях, а прочие остаются в начальной точке. Тот искатель, который нашел цель, сообщает об этом всем остальным. Таким образом, стоимость для всех искателей равна m + 2, если предположить, что все они должны добраться до цели. При отсутствии связи решение усложняется, и оптимальный алгоритм для этой задачи пока не найден. | Если число искателей больше одного – скажем, равно m – то решение является тривиальным, если у них имеется мгновенная связь друг с другом. Два искателя идут в противоположных направлениях, а прочие остаются в начальной точке. Тот искатель, который нашел цель, сообщает об этом всем остальным. Таким образом, стоимость для всех искателей равна m + 2, если предположить, что все они должны добраться до цели. При отсутствии связи решение усложняется, и оптимальный алгоритм для этой задачи пока не найден. | ||
| Строка 20: | Строка 22: | ||
Возможны и другие вариации. Например, если нас интересует средний случай, то можно вывести вероятностное распределение для нахождения целевой точки, получая парадоксальные результаты, как оптимальный алгоритм конечного расстояния с бесконечным числом точек разворота. С другой стороны, в худшем случае, если с каждым разворотом связана стоимость d, оптимальное расстояние равно 9 OPT + 2d, где OPT – расстояние от начала координат до целевой точки. Этот последний случай был решен и для задачи с r лучами. | Возможны и другие вариации. Например, если нас интересует средний случай, то можно вывести вероятностное распределение для нахождения целевой точки, получая парадоксальные результаты, такие как оптимальный алгоритм конечного расстояния с бесконечным числом точек разворота. С другой стороны, в худшем случае, если с каждым разворотом связана стоимость d, оптимальное расстояние равно 9 OPT + 2d, где OPT – расстояние от начала координат до целевой точки. Этот последний случай был решен и для задачи с r лучами. | ||