使用最小总距离算法连接所有点

Question

我有一组点以及适用于每对点的距离函数。我想连接所有点，使得总距离最小。您知道我可以使用的现有算法吗？

每个点可以链接到多个点，因此这不是通常的“销售员路径”问题。

谢谢！

- Blacksad

---

这可以被解释为一个最小权重生成树问题。我不确定这是最好的方法来处理它，但这是一种方式。 - biziclop

如果距离度量遵循对于每三个点x、y和z都有D(x,z) <= D(x,y) + D(y,z)，那么基本上连接每一对点将给出总最小距离。我认为你需要稍微修改一下你的问题。 - ElKamina

距离度量可以是所有连接长度的总和。 - Jim Blackler

对不起，各位，我的问题表述不是很清晰。@biziclop 你是正确的，这是一个最小权重生成树的问题。我不知道这个术语。 - Blacksad

@Blacksad 有时候我们只需要知道我们要找的概念的名称。 :) - biziclop

Answer 1

您需要的是最小生成树。

生成最小生成树的两种最常见算法是：

• 普里姆算法
• 克鲁斯卡尔算法

- z -

Answer 2

正如其他人所说，最小生成树（MST）将允许您形成一个连接所有点的最小距离子图。

但是，您首先需要为数据集创建一个图。为了有效地形成无向图，您可以计算点集的Delaunay三角剖分。然后从三角剖分转换为图形相当直观-任何三角剖分中的边缘也是图形中的边缘，其权重为三角剖分边缘的长度。

对于MST（Prim's/Kruskal's O(E*log(V))）和Delaunay三角剖分（分治O(V*log(V))）阶段都有有效的算法，因此可以实现高效的整体方法。

希望这能帮到您。

- Darren Engwirda

Answer 3

你要寻找的算法称为最小生成树。这个算法对于寻找水、电话或电力网格的最小成本很有用。有Prim算法和Kruskal算法两种实现方式，依我之见，Prim算法更容易理解些。

- Micromega

Answer 4

在这里 http://en.wikipedia.org/wiki/Minimum_spanning_tree，你可以找到更多关于最小生成树的信息，这样你就可以将其应用到解决你的问题上。

- Pedro Teran

Answer 5

看一下Dijkstra算法：

Dijkstra算法是由荷兰计算机科学家Edsger Dijkstra于1956年构思并于1959年发表的图搜索算法，它解决了具有非负边路径成本的图的单源最短路径问题，生成最短路径树。该算法经常用于路由，并作为其他图算法的子程序。

http://en.wikipedia.org/wiki/Dijkstra's_algorithm

- Andrew