Лучший матч между двумя наборами очков

Question

У меня есть два списка точек, назовем их L ₁ (P ₁ (x ₁ , y ₁ ), ... P _n (x _n , y _n )) и L ₂ (P ' ₁ (x ' ₁ , y' ₁ ), ... P ' _n (x' _n , y ' _п )).

Моя задача - найти наилучшее совпадение между их точками для минимизации суммы их расстояний.

Есть какие-нибудь подсказки по какому-то алгоритму?Два списка содержат ок.200-300 баллов.

Спасибо и самое лучшее.

Answer 1

Если вариант использования вашей проблемы включает в себя сопоставление любой точки, присутствующей в списке L ₁ , с точкой в ​​списке L ₂ , то Венгерский алгоритм будетслужить идеальной подгонкой.

Весами, соответствующими вашей венгерской матрице, будет расстояние между точкой, аннотированной для строки, против столбца.Общее время выполнения для оптимизированного венгерского алгоритма - O (n ³ ), которое будет удобно соответствовать вашему заданному ограничению n = 300

Довольно хороший учебник, охватывающий идеологию и реализацию венгерскогоАлгоритм: https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/

Если не использовать венгерский алгоритм, вы также можете превратить данную проблему в проблему max-flow-min-cost - подробности, которую я пока опущу, но при необходимости можем обсудить.