Эффективное минимальное остовное дерево в метрическом пространстве

Question

У меня есть большой набор точек (n> 10000 в количестве) в некотором метрическом пространстве (например, с Jaccard Distance). Я хочу связать их с минимальным связующим деревом, используя метрику как вес по краям.

• Есть ли алгоритм, который работает меньше, чем O (N 2 ) время?
• Если нет, существует ли алгоритм, который работает меньше, чем O (n) среднее время (возможно, с использованием рандомизации)?
• Если нет, существует ли алгоритм, который работает меньше, чем O (n) и дает хорошее приближение минимального остовного дерева?
• Если нет, есть ли причина, почему такой алгоритм не может существовать?

Благодарим вас заблаговременно!

Редактировать плакаты, указанные ниже: Классические алгоритмы поиска минимального связующего дерева здесь не работают. Они имеют E-фактор в своем времени работы, но в моем случае E = n , так как я фактически рассматриваю полный график. У меня также недостаточно памяти для хранения всех возможных краев> 49995000.

Answer 1

По-видимому, в соответствии с этим: Estimating the weight of metric minimum spanning trees in sublinear time нет детерминированного o (n^2) (обратите внимание: smallOh, что, вероятно, означает, что вы подразумеваете менее чем на O (n^2), я полагаю). В этой статье также представлен сублинейный рандомизированный алгоритм для метрического минимального веса, охватывающего дерево.

Также посмотрите на эту статью: An optimal minimum spanning tree algorithm, которая дает оптимальный алгоритм. В документе также утверждается, что сложность оптимального алгоритма пока неизвестна!

Рекомендации в первом документе должны быть полезными, и эта бумага, вероятно, наиболее важна для вашего вопроса.

Надеюсь, что помогает.

Answer 2

Когда я смотрел на очень похожую проблему 3-4 года назад, я не мог найти идеального решения в литературе, на которую я смотрел.

Трюк, на мой взгляд, заключается в том, чтобы найти «маленькое» подмножество «вероятных хороших» краев, на котором вы можете запустить обычный старый Kruskal. В общем, вполне вероятно, что многие ребра MST можно найти среди множества ребер, которые соединяют каждую вершину со своими ближайшими соседями, для некоторых небольших k. Эти ребра могут не охватывать график, но когда они этого не делают, каждый компонент может быть свернут в одну вершину (выбран случайным образом) и процесс повторяется. (Для лучшей точности вместо того, чтобы выбрать одного представителя, чтобы стать новым «супервертекс», выберите небольшое количество представителей и в следующем раунде изучите все расстояния между двумя суперверсиями, выбирая минимум.)

к -ближайших соседа алгоритмы достаточно хорошо изучены для случая, когда объекты могут быть представлены в виде векторов в конечномерном евклидовом пространстве, так что если вы можете найти способ отображения ваших объектов вниз, что (например, с multidimensional scaling), тогда вам может повезти. В частности, отображение вниз до 2D позволяет вычислить диаграмму Вороного, а края MST всегда будут находиться между смежными гранями.Но из того, что я читал, этот подход не всегда дает хорошие результаты.

В противном случае вы можете найти полезные методы кластеризации: Clustering large datasets in arbitrary metric spaces - одна из немногих найденных мной документов, которая явно касается объектов, которые не обязательно являются конечномерными векторами в евклидовом пространстве, и которая учитывает возможность вычислительно дорогостоящих дистанционные функции.