如何找到一组独特的最接近的点对? [英] How to find a unique set of closest pairs of points?
问题描述
A
和 B
分别是 m
和 n
点的集合,其中 m< =n
.我想从 B
中找到一组名为 C
的 m
unique 个点,其中两个点之间的距离之和所有 [A(i),C(i)]
对都是最小的.
A
and B
are sets of m
and n
points respectively, where m<=n
. I want to find a set of m
unique points from B
, named C
, where the sum of distances between all [A(i), C(i)]
pairs is the minimal.
要解决此问题而没有 uniqueness 约束,我可以找到从 B
到 A
中每个点的最近点:
To solve this without uniqueness constraint I can just find closest points from B
to each point in A
:
m = 5; n = 8; dim = 2;
A = rand(m, dim);
B = rand(n, dim);
D = pdist2(A, B);
[~, I] = min(D, [], 2);
C2 = B(I, :);
在 C
中可能存在重复的 B
元素的地方.现在第一个解决方案是蛮力搜索:
Where there may be repeated elements of B
present in C
. Now the first solution is brute-force search:
minSumD = inf;
allCombs = nchoosek(1:n, m);
for i = 1:size(allCombs, 1)
allPerms = perms(allCombs(i, :));
for j = 1:size(allPerms, 1)
ind = sub2ind([m n], 1:m, allPerms(j, :));
sumD = sum(D(ind));
if sumD<minSumD
minSumD = sumD;
I = allPerms(j, :);
end
end
end
C = B(I, :);
我认为 C2
(到每个 A(i)
的最接近点的集合)与 C
几乎相同,除了它的重复点.那么如何减少计算时间呢?
I think C2
(set of closest points to each A(i)
) is pretty much alike C
except for its repeated points. So how can I decrease the computation time?
推荐答案
使用匈牙利算法的变体,用于计算最小/最大重量完美匹配.为未使用的B点创建n-m个虚拟点以与之匹配(或者,如果您愿意付出更多的努力,请使匈牙利算法适用于非平方矩阵).
Use a variant of the Hungarian algorithm, which computes a minimum/maximum weight perfect matching. Create n-m dummy points for the unused B points to match with (or, if you're willing to put in more effort, adapt the Hungarian algorithm machinery to non square matrices).
这篇关于如何找到一组独特的最接近的点对?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!