查找连接所有节点的最短路径集

Question

我在2D坐标空间中有一组点。

我想找到将它们连接在一起的路径总长度最短的一组路径。 （好的启发式解决方案，不需要很精确。）

这听起来像是旅行商的问题，但这是不同的。我不是在寻找一个循环，该循环将一次又一次地访问每个点。我只需要将每个点连接到至少一个其他点，以使集合中的所有点至少间接地彼此连接，并使所选连接的长度之和最小即可。因此，应尽量减少连接长度的总和。

一种简单的最近邻居算法（即，将每个点连接到尚未与其连接的最近邻居）不起作用，因为彼此相距较远的小群集最终将被隔离，并且您总是会失败创建周期。

Answer 1

如果我正确理解了您的问题，那么您正在寻找的是最小生成树（通常缩写为MST）。 MST只是

• （（a）连接所有点，
• （b）同时具有最小的总长度，和
• （c）没有循环。

[可以找到MST的几种知名算法，例如Prim算法和Kruskal算法-我将带您逐步了解Kruskal算法，我个人认为这是最直观的。如果有兴趣，您应该可以在线或在算法教科书中找到其他算法。

---

Kruskal首先是按长度对各个路径进行排序。使用该列表，我们可以通过重复以下过程直到所有点/顶点都包含在树中来创建MST：

1. 请考虑列表中的最短路径。
   • 如果会在您的MST中创建一个循环，请不要将其添加到树中（只需将其从列表中删除即可。
   • 否则，将其添加到树中（并将其从列表中删除）。

最终，您最终会得到一棵树，该树是

• （a）连接所有点-保证，因为考虑了每条路径，有资格加入MST的每个顶点都必须在一条路径上，并且添加一条路径以到达先前未连接的顶点不能创建循环；
• （b）的总长度尽可能短-可以保证，因为路径是按长度递增的顺序添加的；和
• （c）没有循环-可以保证，因为算法明确避免了这种情况。

---

注意：

（（1）在处理MST（和其他图形问题）时，我们经常用特定名称来称呼零件：点集是“图形”，特定点或节点是“顶点”，顶点之间的路径是“边缘”，边缘的长度为“权重”。

（（2）Kruskal的算法在O（ElogV）时间内运行，其中E是路径/边的数量，V是点/顶点的数量。

（（3）如果图具有与所有数据集断开连接的任何顶点或一组顶点，则最终在“ MST林”中将出现多个MST。

（4）一个图可以具有多个MST；例如，在this graph中，MST的最小长度为6，这是通过以下两个MST实现的：MST1，MST2

（5）确定添加路径是否会创建一个循环实际上很棘手；一种实现方法是使用UnionFind数据结构，您可以使用here。