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