两组点之间的最佳匹配 [英] Best match between two sets of points

问题描述

我有两个点列表，我们称它们为L ₁ (P ₁ (x ₁ ，y ₁)，... P _n (x _n ，y _n ))和L ₂ (P' ₁ (x' ₁ ，y' ₁ )，... P' _n (x' _n ，y' _n )).

I've got two lists of points, let's call them L₁( P₁(x₁, y₁), ... P_n(x_n, y_n)) and L₂(P'₁(x'₁, y'₁), ... P'_n(x'_n, y'_n)).

我的任务是找到两点之间的最佳匹配，以最小化它们的距离之和.

My task is to find the best match between their points for minimizing the sum of their distances.

关于某种算法的任何线索吗?这两个列表包含大约.200-300点.

Any clue on some algorithm? The two lists contain approx. 200-300 points.

感谢和最好.

推荐答案

如果问题的用例涉及将列表L ₁ 中存在的所有点与列表L _{2中的点进行匹配}，那么匈牙利算法将是一个完美的选择.

If the use case of your problem involves matching ever point present in list L₁ with a point in list L₂, then the Hungarian Algorithm would serve as a perfect fit.

与您的匈牙利矩阵对应的权重将是为行注释的点与列注释的点之间的距离.优化的匈牙利算法的总体运行时间为O(n ³ )，可以轻松满足您给定的 n = 300

The weights corresponding to your Hungarian matrix would be the distance between the point annotated for the row vs the column. The overall runtime for the optimized Hungarian algorithm is O(n³) which will comfortably fit for your given constraint of n = 300

如果不是匈牙利算法，也可以将给定问题变成 max-flow-min-cost 问题-我现在将省略其详细信息，但可以根据需要进行讨论

If not for the Hungarian algorithm, you can also morph the given problem into a max-flow-min-cost problem - the details of which I'll omit for now but can discuss if required.

这篇关于两组点之间的最佳匹配的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！