Проблема ближайшей пары
Задача:
Предоставить функцию для поиска ближайших двух точек среди множества заданных точек в двух измерениях, т. Е. Решить задачу Ближайшей пары точек в плоском случае.
Прямым решением является алгоритм O (n 2 ) (который мы можем назвать алгоритмом грубой силы); псевдокод (с использованием индексов) может быть простым:
bruteForceClosestPair из P (1), P (2), ... P (N)
если N <2, то
return ∞
еще
minDistance ← | P (1) - P (2) |
minPoints ← {P (1), P (2)}
foreach i ∈ [1, N-1]
foreach j ∈ [i + 1, N]
если | P (i) - P (j) | <minDistance тогда
minDistance ← | P (i) - P (j) |
minPoints ← {P (i), P (j)}
ENDIF
ENDFOR
ENDFOR
return minDistance, minPoints
ENDIF
Лучший алгоритм основан на подходе рекурсивного разделения и покорения, как это объясняется также в самой близкой проблеме точек Википедии , которая является O (n log n); псевдокод может быть:
ближайшая пара (xP, yP)
где xP - P (1) .. P (N), отсортированная по координате x, и
yP - P (1). P (N), отсортированный по координате y (по возрастанию)
если N ≤ 3, то
возвращать ближайшие точки xP с использованием алгоритма грубой силы
еще
xL ← точки xP от 1 до ⌈N / 2⌉
xR ← точки xP от ⌈N / 2⌉ + 1 до N
xm ← xP (⌈N / 2⌉) x
yL ← {p ∈ yP: p x ≤ xm}
yR ← {p ∈ yP: p x > xm}
(dL, pairL) ← ближайшая пара (xL, yL)
(dR, pairR) ← ближайшая пара (xR, yR)
(dmin, pairMin) ← (dR, pairR)
если dL <dR, тогда
(dmin, pairMin) ← (dL, pairL)
ENDIF
yS ← {p ∈ yP: | xm - p x | <dmin}
nS ← число точек в yS
(ближайший, ближайший) ← (dmin, pairMin)
для i от 1 до nS - 1
k ← i + 1
в то время как k ≤ nS и yS (k) y - yS (i) y <dmin
если | yS (k) - yS (i) | <ближе
(ближайший ближайший Pair) ← (| yS (k) - yS (i) |, {yS (k), yS (i)})
ENDIF
k ← k + 1
ENDWHILE
ENDFOR
вернуться ближайший, ближайший
ENDIF
Ссылки и дальнейшие чтения: Самая близкая пара проблем точек Ближайшая пара (McGill) Ближайшая пара (UCSB) Ближайшая пара (WUStL) Ближайшая пара (IUPUI) Для ввода предположим, что аргумент представляет собой массив объектов (точек) с элементами x и y установленными в числа. Для вывода возвращаем объект, содержащий пары ключ: значение для distance и pair (т. Е. Пару из двух ближайших точек).