Wie findet man eine einzigartige Menge von engsten Paaren von Punkten?

Question

A und B sind Sätze von m und n Punkte, wobei m<=n. Ich möchte eine Reihe von meinzigartige Punkte von B finden, mit dem Namen C, wo die Summe der Abstände zwischen allen [A(i), C(i)] Paare ist das Minimum.

diese Einschränkung ohne Einzigartigkeit lösen kann ich in A nur am nächsten Punkt von B zu jedem Punkt finden:

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

Wo Elemente B in C wiederholt werden kann. Nun ist die erste Lösung ist Brute-Force-Methode:

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

Ich denke C2 (Satz am nächsten Punkte für jede A(i)) ist ziemlich gleich C mit Ausnahme seiner wiederholten Punkte. Wie kann ich die Rechenzeit reduzieren?

Answer 1

Verwenden Sie eine Variante des Hungarian algorithm, die ein perfektes Minimum/Maximum-Gewicht berechnet. Erstellen Sie n-m Dummy-Punkte für die ungenutzten B-Punkte, damit sie übereinstimmen (oder, wenn Sie bereit sind, mehr Mühe zu investieren, passen Sie die ungarische Algorithmus-Maschinerie an nicht-quadratische Matrizen an).