#algorithm
#алгоритм
Вопрос:
В настоящее время я работаю над реализацией алгоритма ближайшей пары точек на C . То есть, учитывая список точек (x, y), найдите пару точек, которая имеет наименьшее евклидово расстояние. Я провел исследование по этому вопросу, и мое понимание алгоритма заключается в следующем (пожалуйста, поправьте меня, если я ошибаюсь):
Разделите массив точек посередине, рекурсивно найдите пару точек с минимальным расстоянием для левой и правой половин. Отсортируйте левую и правую половины по y-координате и сравните каждую точку слева с ее 6 ближайшими соседями (по y-координате) справа. За этим стоит некоторый теоретический материал, но это мое понимание того, что нужно сделать).
Я заставил работать рекурсивную часть алгоритма, но изо всех сил пытаюсь найти эффективный способ найти 6 ближайших соседей справа для каждой точки слева. Другими словами, учитывая два отсортированных массива, мне нужно найти 6 ближайших чисел в массиве B для каждой точки в массиве A. Я предполагаю, что здесь требуется что-то похожее на сортировку слиянием, но не смог понять это. Любая помощь будет высоко оценена.
Комментарии:
1. Мой коллега показал мне эти заметки по вычислительной геометрии . Интересный материал, может быть вам полезен.
2. Я помню это из CLRS . Метод «разделяй и властвуй». И да, я помню 6 (или это было 7? очки) но я не помню деталей. В любом случае, если у вас есть доступ к этой книге, решение находится там.
Ответ №1:
Похоже, вам нужно четырехугольное дерево.
Комментарии:
1. Ни в одном из исследований, которые я провел в этом алгоритме, ничего не упоминается об использовании четырехъядерного дерева.
2. Тем не менее, это естественный способ организовать облако 2d-точек. Если у вас есть такое дерево, вы можете получить приблизительную оценку того, насколько близки две точки по уровню наименьшего поддерева, содержащего их оба: близкие точки появятся под глубокими поддеревьями. Это позволяет вам сократить список пар, которые вам нужно проверить, чтобы найти ближайшие.
Ответ №2:
Пусть dist = min(dist_L, dist_R) где dist_L, dist_R — минимальные расстояния, найденные в левом и правом наборах соответственно.
Теперь, чтобы найти минимальное расстояние, на котором одна точка находится в левой половине, а другая — в правой половине, вам нужно учитывать только точки, координаты x которых находятся в интервале [x_m - dist, x_m dist] .
Теперь идея состоит в том, чтобы рассмотреть 6 ближайших точек в этом интервале. Итак, отсортируйте точки по y-координате для каждой точки, посмотрите вперед на следующие 6. Это приведет к увеличению O(nlog^2(n)) времени выполнения.
Вы можете дополнительно улучшить это O(nlogn) , ускорив процесс сортировки. Для этого пусть каждый рекурсивный вызов также возвращает отсортированный список точек. Затем, чтобы отсортировать весь список, вам просто нужно объединить два отсортированных списка. Внимательный читатель заметил бы, что это именно сортировка слиянием.
Комментарии:
1. Спасибо, это именно то, что мне было нужно. Я сортировал два массива по координате y отдельно и пытался сравнить точки в левом массиве с 6 ближайшими точками в правом массиве, для чего нет эффективного способа сделать. Все работает отлично.
2. Хорошо, единственная проблема, с которой я все еще сталкиваюсь, заключается в том, как реализовать сортировку слиянием в моей рекурсии. Базовым вариантом для рекурсии моего алгоритма являются подсписки размером 2 и 3 (насколько я знаю, не имело бы смысла иметь базовый вариант 1, потому что минимальное расстояние между точкой само по себе не имело бы значения). Базовый вариант для рекурсивной части сортировки слиянием, по-видимому, равен 1. Итак, как я мог бы объединить эти два разных типа рекурсии?
3. Для подсписка длиной 2 или 3 просто отсортируйте список вручную. Для этого вам не нужно использовать сортировку слиянием.
4. Как вы находите шесть ближайших точек по координате y? Я могу думать только о двоичном поиске, но это стоит времени журнала n, что также приведет к времени O (n log ^ 2 n), даже если сортировка слиянием привязана к алгоритму.