时间戳

首页 > 解决方案 > 如何找到与点元组相关的最小数字总和，这样点就不会重复？

algorithm - 如何找到与点元组相关的最小数字总和，这样点就不会重复？

问题描述

我的数据结构如下所示：

List<Tuple<Tuple<Node, Node>, int>>

节点只是具有 x 和 y 坐标（整数）的点。元组是 C# 元组，因此是一对值。一个 int 表示从源节点到目标节点的最小移动次数。总而言之，它是一个对列表，其中第一个元素是由 Source 和 Destination 组成的对，第二个元素是它们之间的最小距离。

现在列表中的节点正在重复，因为它包含所有可能的组合，例如：

Sources:
0,0
1,1
Destinations:
2,2
3,3
List with distances:
((0,0 to 2,2) -> DISTANCE)
((0,0 to 3,3) -> DISTANCE)
((1,1 to 2,2) -> DISTANCE)
((1,1 to 3,3) -> DISTANCE)

我想要实现的是计算将一些东西从所有来源移动到可用目的地所需的最小移动。因此，在这种情况下，它将是 2 个距离的总和，以一种可能的最小解决方案的方式进行选择（源或距离不能重复）。

我尝试了最简单的解决方案，我只是按距离（从最低到最高）对列表进行排序，然后将 N 个元素移动到结果列表中，而来源和目的地都不会重复。但当然不是那么简单，因为在某些情况下，最好不要与某个节点保持最小距离，因为距离较高可能会导致最终结果较低。

我希望我对问题的描述是可以理解的。我不需要实际的代码，获得算法想法的一些帮助会很棒。

标签： algorithm

解决方案

虽然问题描述相当模糊，但您似乎需要确定图形顶点之间的最短路径。有一些算法可以解决不同类型的这个问题。

对于有限数量的源顶点，值得应用Dijkstra 算法，该算法可以及时搜索从给定顶点到所有其他顶点的最短路径O(V^2)，因此对于 K 个源 -O(K*V^2)

如果源数与总顶点数相当，您可以使用Floyd-Warshall 算法给出所有顶点对之间的距离O(V^3)

推荐阅读