我有两个点列表，我们称它们为 L1( P1(x1, y1 ), ... Pn(xn, yn)) 和 L2 (P'1(x'1, y'1), ... P'n(x 'n, y'n))。
我的任务是找到它们点之间的最佳匹配，以最小化它们的距离总和。
关于某种算法的任何线索吗？这两个列表包含大约。 200-300分。
谢谢并致以最美好的祝愿。
最佳答案
如果您的问题的用例涉及将列表 L1 中存在的点与列表 L2 中的点进行匹配，则 Hungarian Algorithm将是一个完美的选择。
与匈牙利矩阵对应的权重是行注释点与列注释点之间的距离。优化匈牙利算法的总体运行时间为 O(n3)，这将非常适合您给定的 n = 300
一个涵盖匈牙利算法的思想和实现的非常好的教程是 https://www.topcoder.com/community/competitive-programming/tutorials/assignment-problem-and-hungarian-algorithm/
如果不是匈牙利算法，您还可以将给定问题转化为 max-flow-min-cost 问题 - 我现在将省略其详细信息，但如果需要的话可以讨论.
关于c# - 两组点之间的最佳匹配，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/52500239/