如何找到一組最接近的點？

Question

A和B分別是一組m和n點，其中m<=n。我想從B中找到一組m獨特點，名爲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個虛擬點以匹配（或者，如果您願意付出更多努力，則將匈牙利算法機制適應於非平方矩陣）。