Блог

Главная - Вопросы по программированию - Поиск ближайшего узла для каждого узла

Поиск ближайшего узла для каждого узла

#algorithm #time-complexity #nearest-neighbor #closest-points

#алгоритм #время-сложность #ближайший сосед #ближайшие точки

Вопрос:

У меня есть 2 набора узлов — Set A и Set B. Каждый набор имеет размер 25 000.

Мне дается процент (скажем, 20%). Мне нужно найти минимальное расстояние, чтобы 20% узлов в наборе A находились на этом расстоянии от любого узла в наборе B.

Решение:

Найдите 20% набора A, который ближе всего к любому узлу в наборе B. Ответом является узел в тех 20%, который находится дальше всего от любого узла в наборе B.

Решение методом перебора:

         foreach (Node a in setA)
        {
            a.ShortestDistance = infinity;
            foreach (Node b in setB)
            {
                if (a.DistanceTo(b) < a.ShortestDistance)
                {
                    a.ShortestDistance = a.DistanceTo(b);
                }
            }
        }
        setA.SortByShortestDistance();
        return setA[setA.Size * 0.2];

Это работает, но время, которое потребуется, безумно. (Я думаю, O (n ^ 2 сортировка)?)

Как я могу ускорить это? Я хотел бы нажать O (n), если это возможно.

Комментарии:

1. как distanceTo оценивает расстояние?

2. Я использую Haversine Distance ( movable-type.co.uk/scripts/latlong.html )

Ответ №1:

Ниже приведен алгоритм, который может повысить скорость:-

  1. преобразуйте ваши (lat, long) пары в (x, y, z) в декартовом с центром земли в качестве начала координат
  2. расстояние между (x, y, z) в декартовом формате является нижней границей фактических расстояний в сферических координатах.
  3. Постройте, чтобы разделить 3D-деревья для setA и setB.
  4. для каждого узла a в setA поиск ближайшего соседа в 3d дереве setB, который в среднем случае равен O (logN).
  5. Тогда расстояние для ближайшего соседа будет расстоянием от ближайшего соседа.
  6. Затем отсортируйте setA, как вы это сделали.

Временная сложность :-

В среднем случае : O(n*logn)

В худшем случае : O(n^2)

Комментарии:

1. мне нравится идея, но я не уверен, стоит ли увеличение скорости потери точности. что-то, что мне нужно будет рассмотреть

Ответ №2:

Вы можете выбрать меньший из двух наборов и построить из него структуру для ответа на запросы ближайшего соседа — http://en.wikipedia.org/wiki/Cover_tree не делает много предположений о базовой метрике, поэтому она должна работать с haversine / great circle.

После выполнения этого проще всего было бы взять каждый элемент большего набора, найти ближайшего к нему соседа в меньшем наборе, а затем отсортировать или http://en.wikipedia.org/wiki/Quickselect расстояния. Если вы изменили операцию поиска, чтобы вернуться раньше, ничего не найдя, если ближайший объект должен находиться дальше порогового расстояния, и у вас было приблизительное представление о расстоянии, вы можете сэкономить некоторое время.

Вы могли бы получить приблизительное представление, предварительно выполнив ту же операцию со случайной выборкой из двух наборов. Если ваше предположение немного завышено, вам нужно отсортировать еще несколько расстояний до ближайших соседей. Если ваше предположение слишком низкое, вам нужно только повторить операции поиска для тех точек, где операция ближайшего соседа вернулась раньше, ничего не найдя.

Метки: