#algorithm #recursion #data-structures #closest-points
#алгоритм #рекурсия #структуры данных #ближайшие точки
Вопрос:
Возможно ли найти k пар ближайших точек в наборе из n точек быстрее, чем O(n^2) ?
Я знаю, что могу вычислить ближайшую пару точек за O(nlogn) , но с помощью этого алгоритма вычисляются не все расстояния, поэтому я не могу вернуть k ближайших пар верхних точек.
Эта проблема тривиальна при использовании метода вычисления расстояния между всеми ребрами точек «Грубой силой«, но это имеет сложность [n * (n-1)]/2 , и я хотел бы найти что-то более эффективное.
Редактировать: Смотрите алгоритм ближайших пар здесь: https://www.geeksforgeeks.org/closest-pair-of-points-using-divide-and-conquer-algorithm
Комментарии:
1. Re: «Я могу вычислить ближайшую пару точек за O (nlogn), но с помощью этого алгоритма вычисляются не все расстояния, поэтому я не могу вернуть k ближайших пар точек»: Не могли бы вы предоставить подробную информацию об алгоритме, на который вы ссылаетесь? (Или ссылку на подробности?)
2.
closest pointsсколько измерений?3. (Казалось бы, очевидным расширением является использование приоритетной очереди вместо минимального кандидата .)
4. Существует только 2 измерения (x, y).
Ответ №1:
Одним из жизнеспособных вариантов для малого k было бы многократное использование вашего O(nlogn) алгоритма на подмножествах исходного набора точек, удаляя точки по мере продвижения. Более конкретно, сохранить набор точек, которые образовали минимальную пару. Каждый раз, когда вы запрашиваете следующую ближайшую пару, мы запрашиваем следующую ближайшую пару внутри этих точек и между каждой точкой и остальными исходными точками, и выбираем ближайшую из двух пар.
Для начала удалите все эти точки из исходного набора, кроме одной, и вычислите ближайшую пару. Повторите это для каждой из точек в этом «минимальном наборе» и сохраните общую ближайшую пару. Для вычисления этого потребуется O(j*nlogn) время, когда «минимальный набор» имеет размер j .
Затем запросите следующую ближайшую пару в этом «минимальном наборе» с помощью find-min ( O(1) time) в куче минимально-максимального размера k , которую мы создадим по мере добавления точек к нашему «минимальному набору». Каждый раз, когда мы добавляем точки в наш «минимальный набор», мы вычисляем расстояние между каждой точкой в «минимальном наборе» (размер j ) и этими (до) 2 новыми точками, вставляем их в нашу минимальную-максимальную кучу, а затем удаляем столько элементов, сколько необходимо, чтобы k снова увеличить размер кучи (не более 2j элементов) за O(jlogk) время.
Теперь мы берем ближайшую пару из этих двух (удаляя из кучи, если это уместно — O(logk) время), добавляем точки в наш «минимальный набор» и обновляем минимальную-максимальную кучу, как описано, и повторяем для оставшихся k-j ближайших пар. В целом, это займет O((k^2)nlogn (k^2)logk klogk) = O((k^2)(nlogn logk)) = O((k^2)nlogn) время.
Комментарии:
1. Хорошо, я все еще немного запутался, правильно ли это: 1) найдите первые 2 точки, которые составляют ближайшую пару 2) удалите одну из этих точек из набора, затем снова запустите ближайшую точку (nlogn) 3) сравните точку, удаленную на втором шаге, с оставшимися n-1 точками 3.1) если k> 1, то необходимо проверить все точки (kn) 4) повторите k раз построение моего набора (k) Правильно ли это? Разве это не было бы k * (nk nlogn)? Спасибо за быстрый ответ!
2. @ZachRomano подумайте об этом таким образом, у вас есть два вида точек — те, которые не являются парными, и те, которые были сопряжены хотя бы один раз. Последние составляют «минимальный набор». Итак, на шаге 2 вы «добавляете обратно» каждую точку из «минимального набора» (включая ранее удаленные точки) к остальным по очереди (чтобы посмотреть, образует ли какая-либо из них ближайшую пару с остальными). Для этого требуется knlogn, а не просто nlogn. Вы могли бы использовать здесь некоторые причудливые структуры данных, чтобы избежать повторного вычисления некоторых из них, но это было бы немного затруднительно.
3. Однако я немного заблудился на шагах 3.1 и 4. Вы говорите о 3-м абзаце. Перефразируя, вы будете запрашивать минимальную-максимальную кучу для ближайшей пары, которая может быть создана полностью из «минимального набора» (спаренных / удаленных точек). Это занимает всего O (1) времени, и если оно меньше, чем другая ближайшая пара, мы удалим его, что занимает O (logk) времени. Однако сначала нам нужно создать минимальную-максимальную кучу, чтобы использовать ее. Итак, когда мы удалим пару точек / добавим их в «минимальный набор», мы также увидим, какие пары они образуют с существующими точками в «минимальном наборе». Мы добавим их и уменьшим кучу до размера k.
4. В результате в нашей куче останутся только наименьшие k пар, которые могут быть сформированы полностью в пределах «минимального набора» — именно то, что нам требуется. Это занимает много времени. Сложение всего этого вместе и повторение k раз дает нам наше k ^ 2 (nlogn klogk) = k ^ 2nlogn времени.