求 10^5 阶完备图的 EMST 的最简单算法是什么
What is the simplest, easiest algorithm for finding EMST of a complete graph of order 10^5
我只是想说明一下，EMST 代表欧几里得最小生成树。
基本上，我得到了一个包含 100k 4D 顶点（每行一个顶点）的 文件。目标是访问文件中的每个顶点，同时最小化行进的总距离。从一点到另一点的距离就是欧几里得距离（如果在两点之间画一条直线，则为距离）。
我已经知道这几乎就是旅行商问题，它是 NP 完全的，所以我正在寻找近似解。
我想到的第一个近似算法是从文件构造的图形中找到 MST...但这需要 O(N^2) 甚至只构造给定文件的所有边事实上，它是一个完整的图表（我可以从任何一点转到另一点）。鉴于我的输入是 N = 10^5，我的算法将有一个巨大的 运行 时间，这太慢了......
关于如何计划近似解的任何想法？非常感谢..
我将假设您确实如标题所示想要 EMST，而 TSP 只是达到此目的的一种手段，而不是实际目标本身。两者有非常不同的限制（TSP 的限制要大得多），因此最优解也非常不同。
概述
我们的想法是 运行 修改后的 kruskal 算法，该算法将利用 k-d 树找到最近的对，而无需评估每条潜在边。我们可以找到连接组件中每个顶点的最短边，取最短的整体，并通过该边连接我们的连接组件。正如您将看到的，每次迭代至少连接一半的连接组件，因此最多需要 logn 次迭代才能完成。
最近邻搜索
为了构建 EMST，您需要使用一种数据结构来查询 4D 中的最近邻居 space。您可以扩展八叉树以在更高的维度上工作，但我个人会选择 k-d 树。您可以在 O(nlogn) 时间内构建一棵 k-d 树，使用中位数算法的中位数来查找每个级别的中位数，并且您可以在 [=12] 中插入/从平衡的 k-d 树中删除=]时间。
构建 k-d 树后，您需要查询每个点的最近邻居。然后我们将构建这两个顶点之间的边。其中很多边会被复制，至于一些顶点A和B，A的最近邻可能是B，而B的最近邻邻居可能是 A。我们将通过存储每个顶点属于哪个连通分量来处理这个问题，并且在两个顶点被一条边连接后，重复的边将清楚地连接同一连通分量的两个顶点，因此我们将丢弃它。为此，我们将使用 disjoint-set（就像在 kruskal 算法的许多实现中一样）为每个顶点分配一个连通分量。这也将防止我们在图形中创建循环，这会在 MST 中引入不必要的边。
正在合并
然而，当我们构造每条边时，我们希望在检查要保留哪些边以及哪些边连接 already-connected 顶点之前将其插入到 min-heap 优先级 queue 中。这不会影响第一次迭代的结果，但稍后我们需要通过增加距离来处理边缘。然后去queue所有的边，通过disjoint-set检查不必要/冗余的边，将有效的边插入MST，并合并各自的disjoint-set。当然，所有这些都引入了一个 nlogn 因素，用于从 min-heap 构造和出队元素（如果我们愿意，我们也可以将它们排序在一个普通数组中）。
在添加边的第一次迭代之后，我们将连接至少一半的 MST，也许更多。这是因为我们为每个顶点添加了一条边，并且每条边最多可以有一个副本，因此我们添加了 vertices / 2 条边，但多达 vertices - 1 条。现在我们的 MST 至少已经构建了 1/2。我们将按照以下段落中的描述继续该过程，直到我们总共添加了 vertices - 1 条边。
泛化NN-Search
要继续，我们要在每个连接的组件中构建顶点列表，以便我们可以按组迭代它们。这可以在几乎线性的时间内完成，因为搜索（也合并）一个 disjoint-set 需要 O(α(n)) 时间（α 是反阿克曼函数）并且我们精确地重复 n 次.一旦我们有了每个连接组件的顶点列表，剩下的就相当简单了。我们将采用现有的 k-d 树，并删除当前连接组件中的所有顶点。然后，我们将查询连接组件中每个顶点到每个顶点的最近邻居，并将这些边添加到我们的 min-heap。然后我们将这些顶点添加回 k-d 树，并在下一个连接的组件上重复。由于我们 insert/remove 共有 n 个元素，这相当于平均情况 O(nlogn) 时间复杂度。
现在我们有一个 queue 连接我们连接组件的最短潜在边，我们将按顺序去除 queue 这些边，就像之前一样插入有效边并合并不相交的集合.出于与之前相同的原因，这保证至少连接我们一半的组件，甚至可能是所有组件。我们将重复这个过程，直到我们将所有顶点连接到一个连接的组件中，这将是我们的 MST。请注意，因为我们每次迭代将断开连接的组件数量减半，所以最多需要 O(logn) 次迭代来连接 MST 中的每个顶点（很可能少得多）。
备注
总的来说，这需要 O(nlog^2(n)) 时间。然而，迭代次数可能远少于 log(n) 次，因此在实践中预计会有加速。另请注意，R-tree 可能是 k-d 树的一个很好的替代品——但我不知道它们在实践中如何比较。
我知道这是二次时间，但我认为您应该考虑使用隐式图的 Prim。算法结构为
for each vertex v
mindist[v] := infinity
visited[v] := false
choose a root vertex r
mindist[r] := 0
repeat |V| times
let w be the minimizer of d[w] such that not visited[w]
visited[w] := true
for each vertex v
if not visited[v] and distance(w, v) < mindist[v]:
mindist[v] := distance(w, v)
parent[v] := w
由于使用的存储是线性的，它很可能会驻留在缓存中，并且没有花哨的数据结构，所以这个算法应该运行非常快。
我只是想说明一下，EMST 代表欧几里得最小生成树。
基本上，我得到了一个包含 100k 4D 顶点（每行一个顶点）的 文件。目标是访问文件中的每个顶点，同时最小化行进的总距离。从一点到另一点的距离就是欧几里得距离（如果在两点之间画一条直线，则为距离）。
我已经知道这几乎就是旅行商问题，它是 NP 完全的，所以我正在寻找近似解。
我想到的第一个近似算法是从文件构造的图形中找到 MST...但这需要 O(N^2) 甚至只构造给定文件的所有边事实上，它是一个完整的图表（我可以从任何一点转到另一点）。鉴于我的输入是 N = 10^5，我的算法将有一个巨大的 运行 时间，这太慢了......
关于如何计划近似解的任何想法？非常感谢..
我将假设您确实如标题所示想要 EMST，而 TSP 只是达到此目的的一种手段，而不是实际目标本身。两者有非常不同的限制（TSP 的限制要大得多），因此最优解也非常不同。
概述
我们的想法是 运行 修改后的 kruskal 算法，该算法将利用 k-d 树找到最近的对，而无需评估每条潜在边。我们可以找到连接组件中每个顶点的最短边，取最短的整体，并通过该边连接我们的连接组件。正如您将看到的，每次迭代至少连接一半的连接组件，因此最多需要 logn 次迭代才能完成。
最近邻搜索
为了构建 EMST，您需要使用一种数据结构来查询 4D 中的最近邻居 space。您可以扩展八叉树以在更高的维度上工作，但我个人会选择 k-d 树。您可以在 O(nlogn) 时间内构建一棵 k-d 树，使用中位数算法的中位数来查找每个级别的中位数，并且您可以在 [=12] 中插入/从平衡的 k-d 树中删除=]时间。
构建 k-d 树后，您需要查询每个点的最近邻居。然后我们将构建这两个顶点之间的边。其中很多边会被复制，至于一些顶点A和B，A的最近邻可能是B，而B的最近邻邻居可能是 A。我们将通过存储每个顶点属于哪个连通分量来处理这个问题，并且在两个顶点被一条边连接后，重复的边将清楚地连接同一连通分量的两个顶点，因此我们将丢弃它。为此，我们将使用 disjoint-set（就像在 kruskal 算法的许多实现中一样）为每个顶点分配一个连通分量。这也将防止我们在图形中创建循环，这会在 MST 中引入不必要的边。
正在合并
然而，当我们构造每条边时，我们希望在检查要保留哪些边以及哪些边连接 already-connected 顶点之前将其插入到 min-heap 优先级 queue 中。这不会影响第一次迭代的结果，但稍后我们需要通过增加距离来处理边缘。然后去queue所有的边，通过disjoint-set检查不必要/冗余的边，将有效的边插入MST，并合并各自的disjoint-set。当然，所有这些都引入了一个 nlogn 因素，用于从 min-heap 构造和出队元素（如果我们愿意，我们也可以将它们排序在一个普通数组中）。
在添加边的第一次迭代之后，我们将连接至少一半的 MST，也许更多。这是因为我们为每个顶点添加了一条边，并且每条边最多可以有一个副本，因此我们添加了 vertices / 2 条边，但多达 vertices - 1 条。现在我们的 MST 至少已经构建了 1/2。我们将按照以下段落中的描述继续该过程，直到我们总共添加了 vertices - 1 条边。
泛化NN-Search
要继续，我们要在每个连接的组件中构建顶点列表，以便我们可以按组迭代它们。这可以在几乎线性的时间内完成，因为搜索（也合并）一个 disjoint-set 需要 O(α(n)) 时间（α 是反阿克曼函数）并且我们精确地重复 n 次.一旦我们有了每个连接组件的顶点列表，剩下的就相当简单了。我们将采用现有的 k-d 树，并删除当前连接组件中的所有顶点。然后，我们将查询连接组件中每个顶点到每个顶点的最近邻居，并将这些边添加到我们的 min-heap。然后我们将这些顶点添加回 k-d 树，并在下一个连接的组件上重复。由于我们 insert/remove 共有 n 个元素，这相当于平均情况 O(nlogn) 时间复杂度。
现在我们有一个 queue 连接我们连接组件的最短潜在边，我们将按顺序去除 queue 这些边，就像之前一样插入有效边并合并不相交的集合.出于与之前相同的原因，这保证至少连接我们一半的组件，甚至可能是所有组件。我们将重复这个过程，直到我们将所有顶点连接到一个连接的组件中，这将是我们的 MST。请注意，因为我们每次迭代将断开连接的组件数量减半，所以最多需要 O(logn) 次迭代来连接 MST 中的每个顶点（很可能少得多）。
备注
总的来说，这需要 O(nlog^2(n)) 时间。然而，迭代次数可能远少于 log(n) 次，因此在实践中预计会有加速。另请注意，R-tree 可能是 k-d 树的一个很好的替代品——但我不知道它们在实践中如何比较。
我知道这是二次时间，但我认为您应该考虑使用隐式图的 Prim。算法结构为
for each vertex v
mindist[v] := infinity
visited[v] := false
choose a root vertex r
mindist[r] := 0
repeat |V| times
let w be the minimizer of d[w] such that not visited[w]
visited[w] := true
for each vertex v
if not visited[v] and distance(w, v) < mindist[v]:
mindist[v] := distance(w, v)
parent[v] := w
由于使用的存储是线性的，它很可能会驻留在缓存中，并且没有花哨的数据结构，所以这个算法应该运行非常快。