|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Michael Ryazanov 2:5030/1006.64 05 May 2002 15:09:00
To : Nickita A Startcev
Subject : Re: "Уточняющее прицеливание"
--------------------------------------------------------------------------------
01.05 22:36 Nickita A Startcev, 2:5030/1039.8 -> All
NAS> Есть одномерный массив элементов (x,y,data), где x,y - координаты этого
NAS> псевдоточечного объекта. Диапазон в котором лежат координаты известен.
NAS> Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n) ?
Память дополнительную можно использовать?
NAS> Есть ли решение более быстрое чем нижеприведенное?
NAS> 1) берем расстояние до первого объекта, запоминаем вместе с номером
NAS> объекта.
NAS> 2) перебираем подряд оставшиеся объекты, если попался более близкий -
NAS> 'перезапоминаем' расстояние и номер.
Если без дополнительной памяти, можно предложить некую оптимизацию (если
объектов достаточно много и расположены они более-менее равномерно). Hадо
отсотрировать массив в лексикографическом порядке (x, y). Далее, двоичным (и
т.п.) поиском находим элемент с x, ближайшим к X0, и бежим по массиву в обе
стороны, ищя минимум расстояния. Когда |x[i] - X0| станет больше найденного
минимального расстояния, дальше можно не искать.
Если можно использовать дополнительную память, то тут раздолье. :-) Сетку
построить, деревья всякие-разные...
|V|uxau/\
--- -- - ъ
* Origin: Ф И З Ф А К - Ч Е М П И О H ! (2:5030/1006.64)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
