алгоритм ближайшей пары

Question

Я пытаюсь понять алгоритм ближайшей пары. Я понимаю о делении набора пополам. Но мне трудно понять, как рекурсивно вычислять ближайшую пару. Я понимаю рекурсию, но не понимаю, как вычислить ближайшую пару по рекурсии. Если у вас есть (1,2) (1,11) (7,8), как рекурсия будет работать на них?

Answer 1

основная идея алгоритма заключается в следующем.

У вас есть набор точек P, и вы хотите найти две точки в P, которые имеют наименьшее расстояние между ними.

Aпростой метод грубой силы будет проходить через каждую пару в P, вычислять расстояние, а затем брать одну пару, которая имеет самое короткое расстояние.Это алгоритм O (n²).

Однако лучше по алгоритму, о котором вы говорите.Идея состоит в том, чтобы сначала упорядочить все точки в соответствии с одной из координат, например, координатой x.Теперь ваш набор P на самом деле представляет собой отсортированный список точек, отсортированный по их x-координатам.Алгоритм теперь принимает в качестве входных данных не набор точек, а отсортированный список точек.Давайте назовем алгоритм ClosestPair (L), где L - список точек, заданных в качестве аргумента.

ClosestPair (L) теперь реализован рекурсивно следующим образом:

1. Разделить списокL в его середине, получая L _влево и L _вправо .
2. Рекурсивное решение ClosestPair (L _left ) и ClosestPair (L _право ).Пусть соответствующие кратчайшие расстояния, полученные с помощью δ _влево и δ _вправо .
3. Теперь мы знаем, что кратчайшее расстояние в исходном наборе (представленном L) либо одноиз двух δs, или тогда это расстояние между точкой в ​​L _слева и точкой в ​​L _справа .
4. Se нам еще нужно проверить, есть лиэто более короткое расстояние между двумя точками слева и справа.Хитрость в том, что, поскольку мы знаем, что расстояние должно быть меньше, чем δ _влево и δ _вправо , достаточно рассмотреть из обоих подразделений точки, которые не дальше чем min (δ * 1040)* влево , δ _вправо ) от разделительной линии (координата x, которую вы использовали для разделения исходного списка L).Эта оптимизация делает процедуру быстрее, чем метод грубой силы, на практике O (n log n).

Answer 2

Если вы имеете в виду этот алгоритм , вы делаете следующее:

1. Баллы сортировки: (1,2) (1,11) (7,8)
2. Создайте два подмножества: (1,2) (1,11) и (7,8)
3. Запустите алгоритм для (1,2) (1,11) и для (7,8) по отдельности <= именно здесь начинается рекурсия. В результате dLmin = 9 и dRmin = бесконечность (справа нет второй точки) </li>
4. dLRmin = sqrt (45)
5. результат = min (dLmin, dRmin, dLRmin) = sqrt (45)

Рекурсия состоит из тех же шагов, что и выше. Например. вызов с (1,2) и (1,11) делает:

1. Баллы сортировки: (1,2) (1,11)
2. Создание двух подмножеств: (1,2) и (1,11)
3. Запустите алгоритм для (1,2) и для (1,11) отдельно <= снова вызовы рекурсии. В результате dLmin = бесконечность и dRmin = бесконечность </li>
4. dLRmin = 9
5. результат = min (dLmin, dRmin, dLRmin) = 9

Answer 3

Мне кажется, я знаю, о каком алгоритме вы говорите. Я мог бы рассказать здесь сам, но описание, данное в Введение в алгоритмы , намного превосходит то, что я могу произвести. И эта глава также доступна в книгах Google: наслаждайтесь . (Все остальные тоже могут найти описание проблемы там)

Answer 4

Может быть Алгоритм рандомизированной ближайшей пары с линейным временем поможет.Там вы можете найти пару в ожидаемое время O (n).