查找两个点集之间的点对应关系，最小化所有匹配的距离总和

Question

我的问题是，给定两个点集 A 和 B，A 的元素大小不超过 B 的元素大小，是否有任何有效的方法可以为 A 中的每个点找到 B 中的相应点，使得所有匹配的距离之和最小？B 中的每个点最多可以使用一次。谢谢！

Answer 1

是的

，用于加权二分匹配的匈牙利算法。

对于 A 元素和 B 元素之间的每条边，设该边的粗细是它们之间的距离。然后，运行匈牙利算法，最小化权重的总和。

总运行时间为 O（|A|^3）。