Я собираюсь предположить, что вы на самом деле хотите, чтобы EMST соответствовал вашему названию, и TSP - это всего лишь средство для достижения этой цели, а не сама цель. Оба имеют очень разные ограничения (TSP гораздо более ограничительный) и, следовательно, очень разные оптимальные решения.
Обзор
Идея состоит в том, что мы хотим запустить модифицированный алгоритм Крускала, который будет использовать k-d дерево для поиска ближайших пар без оценки каждого потенциального ребра. Мы можем найти самое короткое ребро для каждой вершины в соединенном компоненте, взять самое короткое общее и соединить наши соединенные компоненты через это ребро. Как вы увидите, это связывает, по крайней мере, половину наших подключенных компонентов в каждой итерации, поэтому для выполнения требуется максимум logn итераций.
Поиск ближайшего соседа
Для построения EMST вы захотите использовать структуру данных для запроса ближайших соседей в 4D пространстве. Вы могли бы расширить октреы, чтобы работать в более высоком измерении, но я бы лично пошел с k-d деревом. Вы можете построить дерево k-d за O(nlogn) время, используя алгоритм медианы медиан, чтобы найти медиану на каждом уровне, и вы можете вставить / удалить его из сбалансированного дерева k-d за O(logn) время.
После того как вы построили k-d дерево, вам нужно будет запросить ближайшего соседа к каждой точке. Затем мы построим ребро между этими двумя вершинами. Многие из этих ребер будут дублированы, как для некоторых вершин A и B, ближайший сосед A может быть B, а ближайший сосед B может быть A. Мы справимся с этим, сохранив, к какому связанному компоненту принадлежит каждая вершина, и после того, как две вершины соединены ребром, дубликат ребра четко соединит две вершины одного и того же связанного компонента, и поэтому мы отбросим его. Для этого мы будем использовать дизъюнктное множество (как во многих реализациях алгоритма Крускала), чтобы назначить связанный компонент каждой вершине. Это также помешает нам создать циклы в нашем графе, что приведет к появлению ненужных ребер в MST.
Слияние
Однако, когда мы создаем каждое ребро, мы хотим вставить его в очередь с минимальной кучей, прежде чем проверять, какие ребра оставить, а какие соединить уже соединенные вершины. Это не повлияет на результат этой первой итерации, но позже нам нужно будет обрабатывать ребра путем увеличения расстояния. Затем удалите из очереди все ребра, проверьте наличие ненужных / избыточных ребер с помощью несвязанного множества, вставьте действительные ребра в MST и объедините соответствующие непересекающиеся множества. Все это, конечно, вводит фактор nlogn для создания и удаления элементов из минимальной кучи (мы могли бы просто отсортировать их в виде простого массива, если мы хотим).
После этой первой итерации добавления ребер мы подключим как минимум половину MST, а может и больше. Это потому, что для каждой вершины мы добавили одно ребро, и у нас может быть не более одного дубликата на ребро, поэтому мы добавили всего несколько vertices / 2 ребер, но целых vertices - 1. Теперь построено как минимум 1/2 нашего MST. Мы продолжим процесс, как описано в следующих параграфах, пока мы не добавим всего vertices - 1 ребер.
Обобщающий NN-поиск
Чтобы продолжить, нам нужно составить списки вершин в каждом связанном компоненте, чтобы мы могли перебирать их по группам.Это можно сделать за почти линейное время, так как поиск (также слияние) несвязанного множества занимает O(α(n)) время (α - обратная функция Аккермана), и мы повторяем ровно n раз.Как только у нас есть наши списки вершин для каждого связанного компонента, остальное довольно просто.Мы возьмем наше существующее дерево kd и удалим все вершины в нашем текущем связанном компоненте.Затем мы запросим ближайшего соседа к каждой вершине для каждой вершины в нашем связанном компоненте и добавим эти ребра в нашу минимальную кучу.Затем мы добавим эти вершины обратно в дерево kd и повторим на следующем подключенном компоненте.Поскольку мы вставляем / удаляем в общей сложности n элементов, это в среднем составляет O(nlogn) временной сложности.
Теперь, когда у нас есть очередь из самых коротких потенциальных ребер, соединяющих наши подключенные компоненты, мы будемудалите их по порядку, как и прежде, вставьте действительные ребра и объедините непересекающиеся множества.По тем же причинам, что и раньше, это гарантирует подключение как минимум половины наших компонентов, возможно, даже всех из них.Мы будем повторять этот процесс до тех пор, пока мы не соединим все вершины в один связанный компонент, который будет нашим MST.Обратите внимание, что, поскольку мы уменьшаем вдвое количество отключенных компонентов на каждой итерации, потребуется не более O(logn) итераций, чтобы соединить каждую вершину в нашем MST (скорее всего, намного меньше).
Замечания
В целом, это займет O(nlog^2(n)) времени.Однако итераций, вероятно, будет гораздо меньше, чем log(n), поэтому на практике ожидайте ускорения.Также обратите внимание, что R-дерево может быть хорошей альтернативой дереву kd - однако я не знаю, как они сравниваются на практике.