Как найти уникальный набор ближайших пар точек?

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, который вычисляет идеальное соответствие минимального/максимального веса. Создайте n-m фиктивные точки для неиспользуемых точек B, чтобы они соответствовали (или, если вы готовы приложить больше усилий, адаптируйте венгерский алгоритм к не квадратным матрицам).