algorithm - 求 10^5 阶完全图的 EMST 的最简单、最容易的算法是什么

Question

我只是想澄清一下，EMST 代表欧几里得最小生成树。

本质上，我得到了一个包含 100k 4D 顶点(每行一个顶点)的文件。目标是访问文件中的每个顶点，同时最小化行进的总距离。从一个点到另一个点的距离就是欧几里德距离(如果在两点之间画一条直线，则为距离)。

我已经知道这几乎是旅行商问题，它是 NP 完全问题，所以我正在寻找近似的解决方案。

我想到的第一个近似算法是从文件构建的图中找到 MST...但是考虑到这一事实，即使只从文件构建所有边也需要 O(N^2)这是一个完整的图表(我可以从任何一点到另一个点)。考虑到我的输入是 N = 10^5，我的算法将有一个巨大的运行时间，这太慢了......

关于我如何计划近似解决方案有什么想法吗？非常感谢您..

Answer 1

我知道这是二次时间，但我认为你应该考虑带有隐式图的 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

由于使用的存储是线性的，它可能会驻留在缓存中，并且没有花哨的数据结构，因此该算法应该运行得相当快。