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

Question

5

我有两组点S和V，它们的大小均为n。我想将这两组点链接起来，使得S中的每个点仅连接一个V中的点，并且将两点之间链接的代价定义为两点之间的欧几里得距离。应该有n!种可能的连接方式。如何以高效的方式找到最小代价的连接方式？

- kkpattern

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- David Nehme · Accepted Answer

这是一个分配问题。您可以使用匈牙利算法来解决它。在Python中有此算法的实现。您也可以使用任何线性规划求解器来解决此问题。LP公式始终会给您一个整数解。