Поиск пути по большому списку узлов? Около 100 000 узлов
У меня есть список узлов в виде 2D-координаты (массив с плавающей точкой), и цель состоит в том, чтобы найти, сколько узлов связанный к исходному узлу (дано).
Два узла определяются как связанные, если расстояние между узлами меньше или равно 10. Кроме того, если расстояние между A и B равно <= 10, расстояние между B и C равно <= 10 и расстояние между A и C> 10, даже тогда A и C связаны, как тогда бы путь был A-> B-> C. Итак, это типичная проблема поиска графов в теории.
Здесь проблема. У меня есть около 100 000 узлов в списке. Каждый узел является 2D координатной точкой. Поскольку список огромен, обычные алгоритмы обхода и поиска пути, такие как DFS или BFS, потребовали бы O (n ^ 2) для построения списка смежности, что не идеально и не то, что я ищу.
Я исследовал в Интернете и обнаружил, что Quad Tree или kd Tree, вероятно, могут быть лучшими для реализации в этом случае. Я также создал свой собственный класс Quad Tree, я просто не понимаю, как реализовать на нем алгоритм поиска, такой как DFS. Или если есть что-то еще, что я пропускаю?
Решение
Квадратное дерево группирует точки, разбивая 2D-пространство на кварталы, либо до тех пор, пока каждая точка не имеет своего квадранта, либо до достижения минимального размера, после чего все точки внутри квадранта объединяются в список.
Поскольку вы пытаетесь найти все точки на максимальном расстоянии от каждой точки в списке источников, вам не нужно переходить к одному пункту на ячейку. Чтобы выбрать отсечение, я бы провел тесты производительности на некоторых других значениях, но в качестве отправной точки для минимального размера квадранта максимальное расстояние соединения для точек, вероятно, является хорошим предположением.
Итак, теперь у вас есть все ваши точки, сгруппированные в дерево, и вам нужно знать, как на самом деле найти ближайшие.
Поскольку квадродерево кодирует пространственную информацию, чтобы найти точки на определенном расстоянии от любой заданной точки, вы должны были спуститься вниз по квадродереву и использовать эту пространственную информацию для исключения целых квадрантов из вашего поиска. Для этого вы должны проверить, является ли ближайший граница каждого квадранта находится за пределами максимального расстояния от точки, из которой вы ищете. Если ближайший край этого квадранта находится за пределами максимального расстояния, то ни одна из точек в этом квадранте не может находиться в пределах максимального расстояния, поэтому нет необходимости исследовать эту часть дерева. (Это похоже на то, что бинарному поиску не нужно искать части отсортированного массива или дерева, потому что он знает, что эти части не могут содержать искомое значение).
Как только вы дойдете до уровня квадродерева, где у вас есть одна точка или список точек, вы будете выполнять регулярную евклидову проверку расстояния с этими точками, чтобы убедиться, что они действительно находятся в пределах максимального расстояния. (Не забудьте проверить на равенство, иначе вы найдете ту же точку, что и искали).
Так, например, если бы вы искали точки рядом с одной из точек в правом нижнем углу этого изображения, не было бы необходимости искать другие три квадранта верхнего уровня, потому что все три из них были бы за пределами максимума расстояние. Это избавит вас от изучения всех подквадрантов в этих частях дерева и позволит избежать сравнения расстояний по всем этим точкам.
Однако, если вы ищете точку рядом с краем квадранта, вам нужно проверить соседние квадранты, потому что ближайшая граница будет достаточно близкой, чтобы вы не могли исключить возможность наличия действительной точки в этом квадранте.
В вашем конкретном случае вы бы воспользовались этим, однажды построив дерево квадрантов, а затем перебрав исходный список точек и выполнив поиск, описанный выше, чтобы найти все точки вблизи этой точки. Затем вы можете использовать найденные точки для построения графа связности, который может быть эффективно пройден с помощью поиска по глубине / ширине вначале или может быть задан вес ребер для использования с более сложным, взвешенным поиском, таким как алгоритм Дейкстры или A * ,
Другие решения
Других решений пока нет …