假设我们在实平面上得到了一组N点（xi，yi）。
我们希望将它们与任意数量的线连接，这样，对于每对点A，B-都有一条从A到B的路径（可能间接通过另一个点）-并且线的总长度最小。
例如，假设这些是沙漠中的城镇，并且我们正在构建道路网。我们希望使用最少的材料来修建道路，但每个城镇仍然可以通过道路到达。
对于N = 2，解决方案当然只是两点之间的线段：
+------------------+
对于N = 3，假设这些点是共线的，则解又是一个线段：
+------+-----------+
对于N = 3，假设这些点将成为等边三角形的顶点，那么我们将在中心添加一个点，然后构造三个将新的中心点连接到三个点中的每个点的线段：
+
|
|
/ \
/ \
/ \
+ +
我相信问题及其解决方案应得到充分研究。问题和/或算法是否有名称？
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句