|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Anatoly Saveliev 2:5020/400 22 Jul 2003 07:57:07
To : Dmitriy Goldobin
Subject : Re: Поиск ближайшей точки (сабж слетел)
--------------------------------------------------------------------------------
Dmitriy Goldobin wrote:
>
> Hi!
>
> > ну зачем так строго - товарищ просто хотел упорядочить точки по их
> > проекции на ось X, что вполне разумно и работает, если число точек имеет
> > порядок 100 000.
>
> ... и они распределены равномерно по плоскости. Hо в этом случае гораздо
> эффективнее регулярная сетка.
лучше вложенная, она же квадродерево - о чем ниже; и лучше не
регулярная, а делить по медиане на прямоугольники для баланса
> > Точно так же сортируются (по левому краю) и проекции
> а вот в более сложных случаях, чем описано выше, это может привести к
> затратам большим, чем даже простой перебор. Как мы будем искать при такой
> сортировке? Ищем бинарным поиском ближайшую по X точку к искомой, вычисляем
неверно, просто ищем дихотомией левую границу в сортированном массиве
проекций на X (с некоторым epsilon), после чего линейный перебор до
правой границы. поскольку в epsilon окрестности искомой точки ожидается
2*epsilon/Range(x)*N точек, а скорость поиска O(log(N)), то процесс идет
быстро, а приведенный ниже пример к данному методу контрпримером не
является, поскольку му переберем примерно 3 точки - центральную, над
ней, и под ней.
С отрезками конечно немного посложнее, но тоже ничего экстравагантного
> расстояние до нее, ограничиваем дальнейший поиск по X с двух сторон этим
> расстоянием. Берем следующую ближайшую по X, если расстояние до нее меньше,
> то еще ограничиваем поиск. А теперь представь - точки расположены по
> окружности, а искомая неподалеку от центра. Hикакого ограничения по X мы не
> добьемся и получим полный перебор ПЛЮС бинарный поиск по X в начале.
кстати, то, что контрпример всегда существует, меня учили еще в школе
(высшей). поэтому я в свое время строго по науке запрограммировал почти
всего Препарату и Шеймоса. а потом обнаружил, что со сложными
алгоритмами возникает большое число особых случаев, связанных с ошибками
округления, после чего оставил только QSort, но будучи университетским
человеком изучил реальные характеристики поиска при реальных данных - и
с удивлением обнаружил, что матожтдание числа перебираемых точек
примерно 6, а максимум обычно не превышает 200, поэтому с практической
точки зрения скорость можно считать линейной.
Анатолий Савельев
--- ifmail v.2.15dev5
* Origin: MELT InterNetNews site (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
