algorithm - 如何找到与点元组关联的最小数字总和，以使点不重复？

Question

我有一个这样呈现的数据结构:

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

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

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

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 个元素移动到结果列表中，源和目标都不会重复。但当然不是那么简单，因为有些情况下最好不要对某个节点取最小距离，因为取更高的距离可能会导致最终结果更低。

我希望我对问题的描述是可以理解的。我不需要实际的代码，如果能帮助我了解算法，那就太好了。

Answer 1

这听起来像 assignment problem - “在加权二分图中找到最大权重匹配(或最小权重完美匹配)”(来自维基百科)。我相信一个经典的解决方案是 Hungarian algorithm .