Поиск наименьшего расстояния между точками.

KeSqueer

Прошу прощения, но из общих соображений - симметричности - Ваше решение может быть неоптимальным. Например если обе точки - заданная и ближайшая - имеют очень большие Y (но очень близкие) и совсем разные Y.

Лучший тест - задать достаточно большой рандомный массив точек и реально посортировать его по удалению от заданной точки. Поиск в таком массиве будет идеалом. Тогда эффективность любого алгоритма - это относительно этого идеального поиска.

 

*совсем разные X.

 

PSR1257
Наверное, у любого нелинейного алгоритма есть худший случай.
Я считаю свой алгоритм лучшим на данный момент. Можете сделать его более оптимальным или предложить более универсальный/скоростной - давайте

 

PSR1257

Вовсе нет, ведь можно начать и с конца. Ставя такие условия, вы меняете цель задачи с "придумать более быстрый алгоритм в среднем случае" на "придумать более быстрый алгоритм в худшем случае".

 

рассмотрите несколько вариантов начального расположения точек:

1. По окружности. Все точки расположены на одной окружности, новая точка попадает внутрь ее.
1а. Попадает в центр, все точки равноудалены (все алгоритмы пролетают - то есть пролет алгоритмов не должен быть существенно более ресурсоемким, по сравнению с простым поиском минимума с полным перебором).

2. Все точки расположены на одной прямой, образуя две плотные, почти равные группы, значительно удаленные друг от друга. Новая точка равноудалена от обоих групп, и не лежит на этой прямой.
3. все точки относительно сгруппированы в малом квадрате - как тут уже предлагалось, 0,0 - 100,100. Новая точка - существенно удалена от квадрата, например с координатами (1000, 1000).
4. равномерная дисперсия. Точки равномерно распределены в некотором квадрате, новая точка попадает в этот же квадрат.

Чего-то я сомневаюсь, что деревья и диаграммы Вороного будут оптимальны во всех случаях. Вообще, если бы кто-то дал гарантию, что наш случай 4 - можно придумать много способов решения, оптимальнее деревьев, и не требующих предварительных вычислений.

 

Хм... Да хотя бы, если не будешь извлекать корень, а будешь искать минимальный квадрат расстояния уже быстрее получится И почемму сортировка вынесена за пределы? Как я уже писал, если сортировать не по каждой координате, а по сумме их абсолютных отклонений от заданной точки, то все упрощается

 

Это не меняет сложности алгоритма, ну а в общем, да, быстрее.

Потому как приняли, что предварительно массив можно обработать как угодно, и это не будет вносить вклад в сложность алгоритма.

Если в способе, предложенном Вами, (x,y) или (xi,yi) - точка, для которой нужно найти ближайшую, то этот алгоритм гораздо медленнее простого перебора по той простой причине, что простой перебор не нуждается в сортировке массива.
Если (x,y) и (xi,yi) просто две разные точки массива, и сортировку можно вынести за пределы, то нужно всего лишь будет выполнить (10^6)! раз операцию abs(x-xi)+abs(y-yi) для сортировки.

 

cppasm

Нуоадоело. Стописят раз повторил, что эта обработка одноразовая, не входящая в сам алгоритм поиска минимального расстояния до тестовой точки.

Это не мой метод. Это пример, оправдывающий условия задачи, сформулированные в посте 1 и 4.

Ну-ну. Покажите класс для двумерного случая.

В изначальной задаче сказано, что исходную струкутру данных с точками, с которой Вы работаете можно выбрать заранее. Хотите — сортированный массив, хотите — дерево, хотите — список весов рёбер полного графа, построенного на всех базовых точках и т.п. Согласно этим условиям не важно, разовая тестовая точка или нет.

Как я уже показал, если массив заранее сортирован, это элементарно для одномерного случая. Согласно посту 4 его можно выбрать в том числе и сортированным по любому признаку.

 

Вообще это известная задача (обычно, правда, ставится для пространства произвольной размерности и необязательно стандартной евклидовой метрики), http://en.wikipedia.org/wiki/Nearest_neighbor_search . Алгоритмов для решения существует больше одного, какой лучше - зависит от конкретных данных.
http://en.wikipedia.org/wiki/VP-tree
http://en.wikipedia.org/wiki/Bk-tree
http://en.wikipedia.org/wiki/Kd-tree
http://en.wikipedia.org/wiki/Cover_tree
(ну и почитать статью про Nearest neighbor search, там, в частности, есть внешние ссылки по теме).

 

И что что обработка одноразовая? У него задача одноразовая.
Интересный подход сравнивать производительность алгоритма дающего решение, и алгоритма требующего предварительной подготовки соизмеримой по затратам с поиском решения, но при этом затраты на эту подготовку не учитывать.
В четвёртом посте сказано что структуру данных можно модифицировать, но нигде не сказано что затраты на модификацию не учитываются.
Это всё равно что сказать что я на велосипеде из Москвы в Питер доеду быстрей чем ты на машине.
При этом ты на машине ехать будешь всю дорогу, а меня на самолёте подбросят, а на велосипеде я там 100 метров проеду.

 

cppasm
Вы зациклены на том, что подготовка должна считаться. По условию подготовка предварительная, что означает, что она проводится до работы алгоритма, который нужно оптимизировать. Остальное не важно. Как проводится подготовка, тоже не важно.

Об этом нигде не сказано.

Если проводить такую аналогию, то в исходной задаче оговорено, что как владелец машины, так и владелец велосипеда, могут использовать самолёт. То, что первый не может с собой в самолёт захватить машину как раз и определяет результат: велосипедист доберётся до Питера быстрее.

 

Затраты на предварительные расчеты можно не учитывать, они ничтожны по сравнению с вычислительной сложностью работы самого алгоритма, т.к. предварительные расчеты делаются один раз, алгоритм поиска будет работать многократно.

 

medstrax1
diamond дал уже отличные ссылки. Решение с kd-деревьями не просто подробно разжёвано, но и удачно визуализировано. А лучше чем O(log n) всё равно здесь не получить.

 

Serg50
на момент сортировки опорных точек в дерево, координаты точек расстояния до которых будут искаться - неизвестны.
теоретически возможный диапазон F - [0, +oo).
минимум (a - x)**2 + (b - y)**2 будет находиться там же, где и минимум |a - x| + |b - y|, что позволит избавиться от 2х умножений.

при сортировке в дерево (добавлении очередного элемента), нет необходимости проходить весь массив заново. кроме вырожденых случаев.

при начальном задании массива опорных точек, ессно, хоть один раз их пройти всех надо.

впрочем, r90, Pavia и diamond дали уже готовые алгосы

 

Пример:
тестируемая точка: 0, 0
точка1: 1,1 1^2+1^2=2 |1|+|1|=2 R = 1.414...
точка2: 1.5, 0 1.5^2 +0 = 2.25 |1.5|+0 =1.5 R = 1.5

то есть не всегда
Забавно, ночитав данные ссылки я узнал, что этот способ определения расстояния носит название Manhatten distance

Когда я предлагал алгоритм, я плохо читал условия :-( Я скорее думал о том, что и точка и массив точек каждый раз новые. Наверное, если массив фиксирован, и используется многократно, то построение деревьев оправданно.

 

может полярные координаты что дадут ???

 

Rockphorr
А может лучше в двоичной системе счисления считать?

 

KeSqueer
честно говоря, мне тоже кажется, что проще распараллелить вычисление корня из суммы квадратов чем хитрожопстовать с предвычислениями и строить всякие там индексные таблицы

 

интересные частные случаи

1. точек на плоскости всего две, тогда существует прямая проходящая перпендикулярно через центр - геометрическое место точек равно удаленных от двух данных

2. точек на плоскости всего 3, тогда центр описанной около треугольника с вершинами в этих точках окружности также равноудален от все трех

 

у меня почему-то чувство что по времени эти предварительные расчеты займут времени больше чем простой перебор

другими словами расчет областей в которых каждая точка массива ближайшая для всех остальных точек области задачка огого