我的问题是，给定两组点集A和B，其中A的元素大小不超过B，是否有一种有效的方法来找到B中每个点对应的A中的点，从而使所有匹配的距离之和最小？每个B中的点只能使用一次。
非常感谢！
非常感谢！
1个回答
6
是的，这里讲的是有关带权二分图匹配的 匈牙利算法。
对于每个A中的元素和B中的元素之间的边缘，请将该边缘的权重设置为它们之间的距离。然后运行匈牙利算法，以最小化权重的总和。
总运行时间为O（|A|^3）。
对于每个A中的元素和B中的元素之间的边缘，请将该边缘的权重设置为它们之间的距离。然后运行匈牙利算法，以最小化权重的总和。
总运行时间为O（|A|^3）。
- jonathanasdf
5
是的，非常感谢！但我想对于我的数据（大约20000个点），这可能会太慢了。有没有近似解决方案？谢谢！ - Chai ML
1你可能会发现这个问题很有帮助。 - jonathanasdf
请注意，有时算法可能会涉及到最大权重匹配，但这没关系，因为要找到最小权重匹配，可以让W成为图中所有边权重的最大值，并将新的边权重设置为W-旧的边权重。使用新的权重找到最大权重匹配，最后，如果您找到了大小为M的匹配，则原始边权重下的最小权重匹配为M*W-result。 - jonathanasdf
谢谢！但我猜最大权匹配不能保证A中的每个点都能匹配，这正确吗？ - Chai ML
不，所有近似算法都保证A中的每个点都会被匹配。它是近似的，因为它不能保证您获得最佳匹配，因此可能存在更好的匹配，其中距离之和更小。 - jonathanasdf
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接