Найти ближайший набор точек в другой набор

Question

У меня есть два множества, и B, с N и M точек в R^п соответственно. Я знаю, что N < M всегда.

Расстояние между двумя точками, P и Q, обозначается через г (P, Q). Поскольку проблема является общей, это расстояние может быть любой функцией (например, евклидовым расстоянием).

Я хочу, чтобы найти ближайший подмножество B в A. Математически я бы сказал, я хочу, чтобы найти подмножество C из B с размером N с минимальным глобальным расстоянием до . Глобальное расстояние между и C дается

D(A,C) = min([sum(d(P_i,Q_i),i=1,N) with P_i in A and Q_i in C* for C* in Permutations of C]) 

Я думал об этой проблеме, и я сделал алгоритм, который получит локальный оптимум, но не обязательно оптимальным:

Шаг 1) Найти ближайшую точку каждой точки в B. Если повторных точек нет, я нашел оптимальное подмножество и закончу алгоритм. Однако, если повторены точки, перейдите к шагу 2.

Шаг 2) Сравните их расстояния (конечно, я сравниваю расстояние между точками с одной и той же ближайшей точкой). Точка с минимальным расстоянием сохраняет найденную ранее точку, а остальные меняют желаемую точку для «ближайшей» ближайшей точки, которая еще не выбрана для другой точки.

Шаг 3) Проверьте, все ли разные точки. Если да, закончите. Если нет, то вернитесь к шагу 2.

Есть идеи? Попытка всех комбинаций не является хорошей (я должен вычислить глобальные расстояния M!/(MN)!)

Answer 1

Если M = N, эта проблема может быть сформулирована как идеальное соответствие минимального веса на двудольном графике или в другими словами, проблема присвоения. Известным методом решения задачи назначения является Hungarian algorithm.

Для того, чтобы венгерский алгоритм применим в случае N < М, можно расширить набор A с (М-Н) дополнительных элементов (каждый из которых имеет нулевое расстояние до всех элементов B).