Учитывая четное число вершин, как найти оптимальный набор пар на основе близости?
Эта проблема:
-
У нас есть набор из n вершин в трехмерном евклидовом пространстве, и существует четное количество этих вершин.
-
Мы хотим соединить их в зависимости от их близости. Другими словами, мы хотели бы иметь возможность найти набор пар вершин, где вершины в каждой паре как можно ближе друг к другу.
-
Мы хотим свести к минимуму жертву близости между вершинами любых других пар, насколько это возможно.
-
Я не ищу большинство оптимальное решение (если оно даже строго существует / может быть сделано), просто разумное решение, которое может быть вычислено относительно быстро.
Относительно ужасный метод грубой силы включает выбор вершины и цикл по остальным, чтобы найти ближайшего соседа, а затем повторять, пока не останется ни одного. Конечно, когда мы приближаемся к концу списка, ближайшая вершина может быть очень далеко, но это единственный выбор, поэтому в третьем пункте выше он может потерпеть неудачу.
Решение
Общим подходом для такого рода проблем (особенно если n велико) является предварительное вычисление структуры пространственного индекса, такой как кд дерево или octtree и выполнить поиск ближайшие соседи с помощью этого. Через узлы октодерева доступные точки помещаются в ячейки, поэтому вы можете быть уверены, что они взаимно близки. Также вы минимизируете количество сравнений.
Эскиз реализации с октавным деревом: вам нужен класс Node, в котором хранится его ограничительная рамка. Производный класс LeafNode хранит небольшое количество точек вплоть до максимума (например, k = 20), которые добавляются с помощью функции вставки. Производный класс NonLeafNode хранит ссылки на 8 подузлов (которые могут быть как Leaf, так и NonLeafNodes).
Дерево представлено корневым узлом, все вставки и запросы начинаются здесь. Дерево строится, начиная с первых k точек, вставляемых в LeafNode. Если k + 1-я точка вставлена, ограничивающий прямоугольник разбивается на 8 вспомогательных блоков, и содержащиеся в нем точки сортируются в них. Текущий LeafNode заменяется одним NonLeafNode с 8 подузлами.
Это повторяется, пока все точки в дереве.
Для поиска ближайшего соседа дерево обходится, начиная с корневого узла, по сравнению с ограничительной рамкой. Если точка запроса находится в ограничивающей рамке узла, обход идет в этот узел. Обратите внимание, что если вы нашли ближайшего кандидата, вам также необходимо проверить соседние узлы в октавном дереве.
Для реализации kdtree проверьте страницу википедии, выглядит довольно просто.
Другие решения
Поскольку вы не ищете оптимального решения, вот эвристика, которую вы можете рассмотреть.
Для каждой точки p вычисляют две точки: ближайший сосед и самый дальний сосед, которые являются самыми близкими и самыми дальними к p соответственно. Теперь пусть q будет точкой с наибольшим самым дальним соседом (q — крайняя точка на входе). Сопоставьте q с ближайшим соседом, удалите их оба и рекурсивно вычислите совпадение для оставшихся точек.
Это, конечно, НЕ оптимально, но, похоже, оно хорошо работает на небольших входных наборах. Если вам нужно оптимальное решение, вы должны прочитать о евклидова проблема соответствия.
detector