Задача такая: дано N точек и для каждой нужно найти ближайшую.
Ясно, что она решается kD-деревом, а эвристики типа проецирования на прямую валятся хорошими тестами.
Быстро работает(и акцептится) такая идея
for j = 1..n
num[j] = j
d[j] = x[j]^2 + y[j]^2
a[j] = INFINITY
осортируем точки по d
for i = 1..n
temp1 := i + 1
temp2 := i - 1
while (temp1 <= n) and (sqrt(d[temp1]) - sqrt(d[i]) - sqrt(a[num[i]]) < eps){
temp3 := squared_distance(x[temp1], y[temp1], x[i], y[i])
if temp3 < a[num[i]]
a[num[i]] := temp3
temp1++
}
while (temp2 >= 1) and (sqrt(d[i]) - sqrt(d[temp2]) - sqrt(a[num[i]]) < eps){
temp3 := squared_distance(x[temp2], y[temp2], x[i], y[i])
if temp3 < a[num[i]]
a[num[i]] := temp3
temp2--
}
в итоге в массиве а будет квадрат ответа
Вроде ясно, что тут какие-то промежуточные оптимизации, но почему это работает и за сколько?
Почему не отсортировать все точки дважды (первый раз по x первично,вторично по y координате, а второй наоборот)и выбрать ближайшую из 4?
Можно подобрать к этому алгоритму контрпример, когда мы можем выбрать точку, такую, что в отсортированном по иксу массиву соседние точки будут иметь очень большую у-координату, а в отсортированном по игреку массиву соседние точки наоборот будут иметь очень большую х-координату. В этом случае правильным ответом может быть какая-то точка, координаты которой немного больше отличаются от данной (чем рассматриваемые до этого), однако мы ее ошибочно рассматривать не будем.
Представьте себе точку в начале координат и много-много точек на единичном круге. Из этих много-много точек какая-то одна случайная чуть сдвинута к центру (находится на круге с радиусом 0.95). Как мы ее найдем таким образом? Если сортировать по координатам, и я правильно понял Вашу идею, то мы будем проверять точки (0,1), (1, 0), (-1,0), (0,-1) — и не найдем ответ.
Кстати, кто сказал, что эвристики с проецированием на прямую валятся хорошими тестами? Я не совсем согласен. Они валятся такими тестами только в том случае, если это codeforces-стайл, т.е. можно подогнать генератор под константы участника. Да и то если у него какой-то хитро спрятанный рэндом или что-то в этом духе — то и это становится сложным. Если же тесты составляют до начала соревнования — лично у меня никогда не возникало проблем с таким решением, оно всегда проходит.
Upd. Или я не совсем правильно понял идею. Я имел в виду эвристики вида "спроектируем, будем перебирать в обе стороны до тех пор, пока по одной из координат разность не станет больше лучшего ответа". Что-то похожее на код топикстартера.
А как она решается КД-деревом?
http://en.wikipedia.org/wiki/K-d_tree#Nearest_neighbour_search
Спроецировать на случайную прямую не валится. Если идти в стороны, пока проекция меньше ответа. Там можно дать честную оценку матожидания времени на корень.
Хм, правда? А как это доказывается? И верно ли это в многомерном случае?
Доказательства я не знаю.
Есть тест, на котором работает ровно n2 с вероятностью близкой к единице. Но там координаты растут экспоненциально. Тестов с достаточно большим n и 32-битными целыми координатами я не знаю.
В многомерном случае эффект такой: в d-мерном пространстве работает за n2 - 1 / d.
Буду признателен, если кто нибудь покажет АС код с такой эвристикой. Я час пихал с шаманством над константами и не нашёл удачной комбинации.
Код для 3d случая
Указанный в посте код работает за квадрат. Тест такой: куча точек, лежащих на одной окружности (тогда сортировка ничего не изменит). "sqrt(d[temp1]) — sqrt(d[i]) — sqrt(a[num[i]])" будет всегда <= 0, т.к. первые 2 терма в выражении равны, и код будет работать вечно. By the way, перед тем как спрашивать сообщество, можно было бы привести код в нормальный вид (убрав оттуда obfuscations вроде массива num).
kD-tree? Интересный взгляд на вещи. Считал это задачей на диаграмму Вороного
И диаграмма Вороного, и kd-дерево решают эту задачу с одинаковой сложностью в среднем случае. Можно погуглить на эту тему Nearest neighbour search. В данной задаче, как мне кажется, эти структуры примерно равны. Однако в похожей задаче, где нужно найти ближайшие точки из одного множества для каждой точки из другого множества (например, в "Тараканьих бегах" на тимусе), kd-дерево не проходит 17 тест — там кормушки расположены близко друг к другу, а тараканы вокруг них равномерно по центру. На таком тесте дерево не даст ускорения, посколько рекурсия при поиске будет идти до конца. Эта задача решается только построением диаграммы Вороного и последующим выметанием по ней.
Кто-нибудь вообще пробовал диаграмму Вороного реализовать?
Учитывая, что полно задач, сдающихся только диаграммой Вороного (или триангуляцией Делоне), — да, много кто пробовал, и даже много кто успешно пробовал.
Вот бы ссылочку на успешные решения через Вороного или Делоне.
Надеюсь, Вы тоже в скором времени попробуете — копипастю алгоритмы с Вашего сайта, когда на емаксе нет или код с ошибками :3
И диаграмма Вороного, и kd-дерево решают эту задачу с одинаковой сложностью в среднем случае.
По какому параметру вы усредняете? KD-дерево решает эту задачу непонятно за сколько, но уж пример, на котором будет ≥ O(n1.5) операций, привести можно. А диаграмма Вороного — за
, так что она быстрее.
Я имел в виду на случайно взятых точках. На рандомных тестах сложность будет такой же у дерева — O(n * log(n)), но на специально подобранных да, оно будет работать за квадрат, в отличие от диаграммы Вороного.
Тогда замечу вам, что не стоит говорить в таком случае о времени работы "в среднем". Под "средним" как правило понимается математическое ожидание времени работы алгоритма в зависимости от некоторого внутреннего рандома (если он вообще есть), а вовсе не от входных данных. Иными словами, это среднее время работы на худшем для алгоритма тесте, а вовсе не среднее время работы по всем тестам (тут вообще возникнет много проблем с определением случайного теста).
В противном случае (то есть при оценке среднего по тестам) и бинарное дерево поиска без балансировки будет работать O(n log n) Предвидя некоторые уточнения, сразу оговорюсь, что если рандом в программе "детерминированный", то есть не делается его сброс от времени, то тот же qsort работает гипотетически за квадрат, но tell me who cares...
Задача "для каждой точки множества A найти ближайшую среди точек множества A" таки решается kD-деревом за O(n1.5). Я умею объяснять, почему время работы будет такое же, как и в методе "спроецируем все точки на случайную прямую". И там, и там я не знаю тестов, дающих асимптотику более n1.5.
Диаграмма Вороного, конечно, круче. Но фиг напишешь на контесте.
А вот задачу "для каждой точки множества A найти ближайшую из множества B" (Тараканьи Бега с тимуса) никак кроме диаграммы Вороного со сканирующей прямой я решать не умею.