Всем привет, давайте сегодня рассмотрим очень, очень классическую алгоритмическую задачу —недавняя двухточечная проблема.
Этот вопрос часто появляется в различных интервью, и он не низок по сложности, и мало кто может на него ответить. Меня, если честно, тоже спрашивали, и я, потому что был не готов, не стал на него отвечать. Да, этот вопрос немного волшебный, и неподготовленные люди часто не могут на него ответить.
смысл названия
Давайте сначала рассмотрим смысл вопроса. Смысл вопроса очень прост. На плоскости распределено n точек. Теперь, когда мы знаем координаты этих n точек, нам нужно найти расстояние между двумя ближайшими точками среди n точек.
Я не уверен, исходит ли этот вопрос из астрономии, но очень уместно поставить его в астрономическом контексте. Представьте, что в огромной вселенной бесчисленное множество звезд, и мы хотим найти два ближайших небесных тела. Это могут быть звезды-близнецы, а могут быть галактики-компаньоны... Думая об этом, вы думаете, что это очень романтично?
При анализе проблемы мы обнаружим противоречие. Парадокс в том, что если мы запросим расстояние между любыми двумя точками, то сложность должна быть, так как n точек занимают две точки и одна имеет
Возможность. Если есть более быстрый алгоритм, то мы не сможем найти расстояние между всеми парами точек, но если мы даже не перечислим все расстояния, как мы можем сказать, что то, что мы нашли, должно быть правильным?
Это то, что я ответил во время интервью в то время.Хотя теперь мы знаем, что это утверждение неверно, можете ли вы судить без этого слоя информации?
разделяй и властвуй
Если подумать, то можно увидеть, что эта задача очень похожа на сортировку. Потому что, когда мы сортируем, на поверхности между каждыми двумя точками существует отношение размера, и кажется, что мы хотим получить эти отношения при сортировке. Но на самом деле мы все знаем, что можно делать и быструю сортировку, и сортировку слиянием.пора заканчивать сортировку.
Будь то быстрая сортировка или сортировка слиянием, по сути, они используют принцип «разделяй и властвуй». Можно ли решить эту проблему методом «разделяй и властвуй»?
Ответ, конечно, да, так как используется метод разделяй и властвуй, то мыПервое, что нужно сделать, это разделить, разбить все данные на две части, использовать рекурсию для завершения двух частей по отдельности, а затем объединить, чтобы получить полный результат. В этой задаче нам очень просто разделить данные.Нам нужно только отсортировать все точки в соответствии с координатами оси X, а затем выбрать среднюю точку для разделения.Результаты, которые мы получаем после разделения, следующие:
После того, как раскол закончился, нам нужно только считать отдельноПара ближайших точек в левой части, пара ближайших точек в правой части и пара ближайших точек с одной точкой слева и одной точкой справаВот и все. Для первых двух случаев это легко решить, нам просто нужно рекурсировать, и мы можем это сделать, но что мы должны сделать для третьего случая? В этом и сложность этого вопроса.
Четко проанализировать эту задачу не очень просто и требует глубокого размышления.Во-первых, мы можем получить кратчайшее расстояние D1 левой части SL и кратчайшее расстояние D2 правой части SR через рекурсивные вызовы. мы принимаем, то есть минимальное значение кратчайшего расстояния по левой и правой сторонам, что следует хорошо понимать.
Найдя D, мы можемИспользуйте его, чтобы ограничить диапазон пар точек, в которых точка находится в SL и точка в SR., иначе придется сравнивать случай, когда с каждой стороны n/2 точек, а вычислительная сложность все равно очень велика.
Давайте проанализируем задачу. Мы случайным образом выбираем точку p на левой стороне. Давайте подумаем о задаче. Для точки p все точки на стороне SR могут образовывать ближайшую к ней точку, верно? Конечно нет, есть некоторые точки, которые находятся далеко и заведомо невозможны, Нам не нужно проходить эти точки одну за другой, и мы можем напрямую игнорировать их пачками.Чтобы сформировать ближайшую пару точек с точкой p, она должна находиться в пределах диапазона, обведенного пунктирной линией на рисунке ниже..
Коробка, образованная этой пунктирной линией, представляет собой прямоугольник, ширина которого равна D, а длина — 2D. Как это произошло? На самом деле это очень просто.Для точки p, если вы хотите составить с ним ближайшую точечную пару, тоРасстояние от него должно быть меньше текущего оптимального решения D. Поскольку расстояние меньше D, значит, абсолютное значение разности их горизонтальных и вертикальных координат также должно быть меньше D.
Конечно, этот прямоугольник — это только то, что мы видим интуитивно, при работе реального алгоритма такого прямоугольника нет, мы можем только судить о том, находится ли в нем определенная точка по оси координат.
С этой коробкой у нас есть еще один вопрос, а именно, насколько полезна эта коробка на самом деле? Можно ли уменьшить сложность алгоритма с помощью этого блока?Будет ли крайний случай, когда все точки справа находятся в квадрате?Шерстяная ткань?
На самом деле нам нужен только простой анализ, чтобы обнаружить, что это невозможно Мы не только можем судить, что это невозможно, но мы также можем сделать другой очень, очень неожиданный вывод.
Во-первых, давайте обсудим, почему невозможно, чтобы все точки справа попали в этот пунктирный прямоугольник. Давайте сначала рассмотрим самый крайний случай, когда выбранная нами точка p находится на разделительной линии. Тогда нарисованные им ящики должны все попасть в область SR, и рисунок, вероятно, будет таким:
Но если мы просто подумаем об этом, мы обнаружим проблему, которая заключается в следующем.Количество точек в пунктирной рамке не может быть бесконечным. Поскольку у нас есть базовое требование к точкам в поле, то есть к точкам в этом поле и в области SR,Расстояние между ними должно быть не менее D.. Если оно меньше D, то это противоречит выводу о том, что D является минимальным расстоянием между левой и правой сторонами. Тогда ситуация на приведенном выше рисунке фактически невозможна, потому что так много точек собрано вместе, и очевидно, что расстояние между двумя точками меньше D, что противоречит.
То есть из-за ограничения этого расстояния количество точек, которые могут попасть в этот пунктирный квадрат, ограничено, и это число может быть намного меньше, чем все думают. маленький додо 6, то есть следующая ситуация:
На приведенном выше рисунке всего 6 точек, и кратчайшее расстояние между этими 6 точками равно D, что является самым крайним случаем.Как бы мы ни добавляли к нему точки, расстояние между двумя точками должно быть меньше D. Это наше интуитивное ощущение, есть ли способ это доказать? На самом деле их тоже немного, мы можем разделить этот прямоугольник на шесть равных частей на следующую фигуру:
Давайте проанализируем, длина каждого маленького прямоугольника на картинке выше равна, ширина
, длина его диагонали
. Тогда согласноПринцип голубиной клетки, если мы ставим больше 6 точек, то в маленьком прямоугольнике должно быть две точки. Наибольшее расстояние в маленьком прямоугольнике меньше, чем D, то есть расстояние между этими двумя точками также должно быть меньше, чем D, что противоречит нашему предыдущему предположению, поэтому можно сделать вывод, что ситуация с более чем 7 точками не имеет значения. не существует.
то естьДля точки p на стороне SL мы можем найти не более 6 точек на стороне SR, чтобы, возможно, образовать самую короткую пару точек., так что количество пар точек, которые нам нужно экранировать, значительно сокращается. А для точек со стороны SL не все точки нужно учитывать,Необходимо учитывать только точку, абсцисса которой отличается от средней точки O меньше, чем D..
На первый взгляд кажется, что все наши анализы закончены, но на самом деле осталась нерешенной одна проблема. Как найти эти 6 точек? Очевидно, что полагаться только на абсциссу недостаточно, здесь необходимо учитывать ординату. После того, как мы разделим набор точек на левую и правую части, мы сортируем правую часть по ординате, Для точки слева (x, y) нам нужно только отфильтровать правую часть, которая удовлетворяет диапазону ординат ( y - d), y + d), таких точек не более 6. Мы можем использовать метод деления пополам, чтобы найти наименьшую точку, ордината которой больше, чем y - d, а затем по очереди перечислить следующие 6 точек.
Код
Прежде чем мы реализуем алгоритм, нам нужно сначала сгенерировать тестовые данные, иначе как мы можем убедиться, что у нашего алгоритма есть проблемы? И этот алгоритм тоже разработан мной с нуля, что тоже полезно для отладки.
В этом вопросе тестовые данные относительно просты, просто нужно сгенерировать два случайных числа в качестве координат. Мы вызываем этот метод, чтобы сначала сгенерировать 200 баллов в качестве теста.
import random
def random_point():
x, y = random.uniform(0, 1000), random.uniform(0, 1000)
return (x, y)
points = [random_point() for _ in range(200)]
Затем мы реализуем решение методом перебора, чтобы проверить правильность нашего алгоритма.Я не думаю, что мне нужно больше говорить об этом абзаце, это всем понятно.
def distance(x, y):
return math.sqrt((x[0] - y[0]) ** 2 + (x[1] - y[1])** 2)
def brute_force(points):
ret = sys.maxsize
a, b = None, None
n = len(points)
for i in range(n):
for j in range(i+1, n):
dis = distance(points[i], points[j])
if dis < ret:
ret = dis
a, b = i, j
return ret, points[a], points[b]
И, наконец, изюминка.На самом деле объем кода самого алгоритма невелик, но деталей в нем много, и небольшая невнимательность может перевернуть машину.
def divide_algorithm(points):
n = len(points)
# 特判只有一个点或者是两个点的情况
if n < 2:
return sys.maxsize, None, None
elif n == 2:
return distance(points[0], points[1]), points[0], points[1]
# 对所有点按照横坐标进行排序
points = sorted(points)
half = (n - 1) // 2
# 递归，这里有一个问题，为什么要先排序再递归？
d1, a1, b1 = divide_algorithm(points[:half])
d2, a2, b2 = divide_algorithm(points[half:])
d, a, b = (d1, a1, b1) if d1 < d2 else (d2, a2, b2)
calibration = points[half][0]
# 根据中间的位置将点集分成两个部分
left, right = [], []
for u in points:
if calibration - d < u[0] < calibration:
left.append(u)
elif calibration <= u[0] < calibration + d:
right.append(u)
# 右侧点集按照纵坐标排序
right = sorted(right, key=lambda x: (x[1], x[0]))
res = d
for u in left:
# 左开右闭的二分
l, r = -1, len(right)-1
while r - l > 1:
m = (l + r) >> 1
if right[m][1] <= u[1] - d:
l = m
else:
r = m
idx = r
# 在范围内最多只有6个点能够构成最近点对
for j in range(7):
if j + idx >= len(right):
break
if distance(u, right[idx + j]) < res:
res = distance(u, right[idx + j])
a, b = u, right[idx + j]
return res, a, b
Алгоритм завершен, но есть еще некоторые детали, например, почему нам нужно сначала сортировать, а затем рекурсивно разделять и властвовать? Непосредственно разделить на две части рекурсивно ОК? почему нет? Например, когда мы делим на два, мы используем интервальную дихотомию, которая закрыта слева и открыта справа?
Я не буду давать ответ на эти два вопроса, надеюсь, вы попробуете подумать сами. Если у вас есть какие-либо идеи, пожалуйста, оставьте мне сообщение ниже, чтобы обсудить.
Вот и все, что касается сегодняшней статьи, и я искренне желаю вам удачи каждый день. Если вам все еще нравится сегодняшний контент, пожалуйста, зайдите на одинТройная поддержкабар~(Нравится, подписывайтесь, делайте репост)