algorithm - 如何找到一组唯一的最接近的点对？

Question

A和B是 m 的集合和n分别为 m<=n 。我想找一套m来自B的独特积分，名为C ，其中所有 [A(i), C(i)] 之间的距离总和对是最少的。

为了在没有唯一性约束的情况下解决这个问题，我可以从 B 找到最近的点到 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, :);

可能存在B重复元素的地方存在于 C 。现在第一个解决方案是暴力搜索:

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除了它的重复点。那么如何减少计算时间呢？

Answer 1

使用 Hungarian algorithm 的变体，它计算最小/最大权重完美匹配。为未使用的 B 点创建 n-m 个虚拟点以进行匹配(或者，如果您愿意付出更多努力，请使匈牙利算法机制适应非方阵)。