|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Evgenij Masherov 2:5020/175.2 06 May 2002 08:37:27
To : Nickita A Startcev
Subject : "Уточняющее прицеливание"
--------------------------------------------------------------------------------
NAS> Есть одномерный массив элементов (x,y,data), где x,y - координаты этого
NAS> псевдоточечного объекта. Диапазон в котором лежат координаты известен.
NAS> Можно ли найти ближайший к X0,Y0 объект быстрее, чем за o(n) ?
NAS> Есть ли решение более быстрое чем нижеприведенное?
NAS> 1) берем расстояние до первого объекта, запоминаем вместе с номером
NAS> объекта.
NAS> 2) перебираем подряд оставшиеся объекты, если попался более близкий -
NAS> 'перезапоминаем' расстояние и номер.
0. Эта задача, практически в такой же постановке, описана у Кнута (т.3, п.
6.5)
1. Простейшее предлагаемое там решение - построить вспомогательный массив, в
котором ключом являются пары округленных значений (х,у), а по этому ключу
вызывается список точных значений (х,у), принадлежащих этому подклассу
(т.е. за О(1) находится от одной до четырех подкарт, а затем по каждой из них
делается линейгый поиск)
2. Более сложное предлагаемое там решение - бинарное дерево, причем узел его
соответствует паре (город, радиус), левая ссылка - города с расстоянием менее
радиуса, правая - более. (Уточнения к Кнуту...)
Евгений Машеров АКА СанитарЖеня
--- ifmail v.2.15dev5
* Origin: FidoNet Online - http://www.fido-online.com (2:5020/175.2)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
