两组点之间的最小距离

yiyan • • 问答 • 248 阅读

我在度量空间中有一组 n 个点。这些点都是蓝色的。我在空间中有另一组 n 点。这些点都是红色的。我想以这样的方式连接这些点，即每个蓝点都连接到一个红点，每个红点都连接到一个蓝点。（显然有 n! 种方法可以做到这一点。）我希望找到使连接总长度最小的连接集。这个问题叫什么？

回答

该问题称为完全二部图上的最小权重完美匹配，或分配问题，

通常表述如下：

该问题可以通过匈牙利算法解决，其复杂度为 O(n^3)。

以上是两组点之间的最小距离的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>