algorithm - 如何找到连接两组点的最小成本

Question

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

Answer 1

这是一个分配问题。你可以用匈牙利方法解决它。在python中有这个的实现。您还可以使用任何线性规划求解器来解决问题。LP 公式总是会给你一个整数解。