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

Question

我的问题是，给定两个点集 A 和 B，A 的元素大小不超过 B 的元素大小，是否有任何有效的方法可以为 A 中的每个点找到 B 中的对应点，使得所有点的距离总和比赛很少？B 中的每个点只能使用一次。非常感谢！

Answer 1

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

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

总运行时间为 O(|A|^3)。