最も近い点のペアのユニークなセットを見つける方法は？

Question

AとB場合m<=n、それぞれmとn点の集合です。 mユニークポイントがBからCとなり、すべて[A(i), C(i)]ペアの間の距離の合計が最小値であることがわかります。

Cに B現在の要素が繰り返されてもよい

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, :); 

を：私はちょうどAの各点にBから最も近い点を見つけることができる一意制約せずにこれを解決する

。最初のソリューションは、力まかせ探索である今：

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個のダミー点を作成します（ハンガリーのアルゴリズム機械を非正方行列に適応させたい場合は、さらに努力してください）。