如何找到连接两组点的最小费用

Question

我得到了两组点S和V，都是n的大小。我想链接两个集合，使得S中的每个点都链接到V中的一个且仅有一个点。链接两个点的成本定义为两点之间的欧几里德距离。应该有n！可能的联系方式。那么如何找到最低成本的方式呢？ （以有效的方式）

Answer 1

这是一个分配问题。你可以用Hungarian Method来解决它。在python中有这样的实现。你也可以用任何线性规划求解器来解决这个问题。 LP公式总是会给你一个整数解。