使用 Delaunay 三角剖分加速 Python MST 计算
Speed up Python MST calculation using Delaunay Triangulation
我有一个代码可以生成多组点的最小生成树（大约 25000 个数据集，每组包含 40-10000 个点），这显然需要一段时间。我正在使用来自 scipy.sparse.csgraph.
的 MST 算法
有人告诉我 MST 是 Delaunay 三角剖分的一个子集，因此建议我通过先找到 DT 然后从中找到 MST 来加速我的代码。
有谁知道这会有多大的不同？另外，如果这使它更快，为什么它不首先成为算法的一部分？如果先计算 DT 再计算 MST 更快，那么为什么 scipy.sparse.csgraph.minimum_spanning_tree 会做其他事情呢？
请注意：我不是计算机高手，有些人可能会说我应该使用不同的语言，但 Python 是我唯一知道的足以做这种事情的语言，请使用回答语言简单，请勿使用行话！
注意：这假设我们在 2-d
中工作
我怀疑您现在正在做的是将所有点对点距离输入 MST 库。这些距离的数量级为 N^2，Kruskal 算法在此类输入上的渐近运行时间为 N^2 * log N.
Delaunay 三角剖分的大多数算法都需要 N log N 时间。一旦计算出三角剖分，只需要考虑三角剖分中的边（因为 MST 始终是三角剖分的子集）。有 O(N) 个这样的边，所以 Kruskal 算法在 scipy.sparse.csgraph 中的运行时间应该是 N log N。所以这给你带来 N log N 的渐近时间复杂度。
scipy.sparse.csgraph 不包含 Delaunay 三角剖分的原因是该算法适用于任意输入，而不仅仅是欧几里德输入。
我不太确定这对您在实践中有多大帮助，但这就是它渐近的样子。
我有一个代码可以生成多组点的最小生成树（大约 25000 个数据集，每组包含 40-10000 个点），这显然需要一段时间。我正在使用来自 scipy.sparse.csgraph.
的 MST 算法有人告诉我 MST 是 Delaunay 三角剖分的一个子集，因此建议我通过先找到 DT 然后从中找到 MST 来加速我的代码。
有谁知道这会有多大的不同？另外，如果这使它更快，为什么它不首先成为算法的一部分？如果先计算 DT 再计算 MST 更快，那么为什么 scipy.sparse.csgraph.minimum_spanning_tree 会做其他事情呢？
请注意：我不是计算机高手，有些人可能会说我应该使用不同的语言，但 Python 是我唯一知道的足以做这种事情的语言，请使用回答语言简单，请勿使用行话！
注意：这假设我们在 2-d
中工作我怀疑您现在正在做的是将所有点对点距离输入 MST 库。这些距离的数量级为 N^2，Kruskal 算法在此类输入上的渐近运行时间为 N^2 * log N.
Delaunay 三角剖分的大多数算法都需要 N log N 时间。一旦计算出三角剖分，只需要考虑三角剖分中的边（因为 MST 始终是三角剖分的子集）。有 O(N) 个这样的边，所以 Kruskal 算法在 scipy.sparse.csgraph 中的运行时间应该是 N log N。所以这给你带来 N log N 的渐近时间复杂度。
scipy.sparse.csgraph 不包含 Delaunay 三角剖分的原因是该算法适用于任意输入，而不仅仅是欧几里德输入。
我不太确定这对您在实践中有多大帮助，但这就是它渐近的样子。