算法来连接所有点的最小总距离 [英] Algorithm to connect all dots with the minimum total distance

问题描述

我有一组点，适用于各对点的距离函数。我想将所有的分在一起，用最小的总距离。你知道现有的算法，我可以用是什么？

I have a set of points and a distance function applicable to each pair of points. I would like to connect ALL the points together, with the minimum total distance. Do you know about an existing algorithm I could use for that ?

每个点可以连接到几个点，所以这不是通常的推销员行程的问题：）

Each point can be linked to several points, so this is not the usual "salesman itinerary" problem :)

谢谢！

推荐答案

你想要的是一个最小生成树。

的两种最常见的算法，以生成一个是：

The two most common algorithms to generate one are:

• Prim算法
• Kruskal算法

• Prim's algorithm
• Kruskal's algorithm

这篇关于算法来连接所有点的最小总距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！