标签列表
找到两个点集之间的点对应关系,使得所有匹配点对的距离总和最小化。
algorithm
geometry
6
6
我的问题是,给定两组点集A和B,其中A的元素大小不超过B,是否有一种有效的方法来找到B中每个点对应的A中的点,从而使所有匹配的距离之和最小?每个B中的点只能使用一次。
非常感谢!
-
Chai ML
1
个回答
6
6
是的,这里讲的是有关带权二分图匹配的
匈牙利算法
。
对于每个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 提供, 点击上面的
可以查看英文原文,
原文链接
相关问题
10
给定一组点,如何找到距离最远的两个点?
11
寻找到其他点距离之和最小的点
7
最小化点对间距离之和
8
最小化点对之间的距离
4
利用曼哈顿距离找到最接近的点对
6
对点进行排序,使得相邻点之间的最小欧几里得距离最大化。
4
寻找最优循环排列,使得两个有序点列表之间的平均距离最小化。
7
给定一个二维点列表,找到距离所有其他点最近的点。
7
最小化到n个点集的欧几里得距离和的点
4
给定K个点集,从每个集合中选择一个点,使得所选点之间的配对距离之和最小化。