我有两套S_1和S_2。鉴于这两组，我需要将每个元素 fromS_1与一个元素 from配对S_2。
- 元素不可重复使用，所以如果
S_1[A]与 配对S_2[D]，那么我也不能S_1[B]与配对S_2[D]。 - 目标是使用所有元素生成配对，以使配对的距离最小化。
- 配对的距离被计算为每对之间的距离之和。
- 产生具有最低总配对点值的结果
是否有任何已知的算法可以有效地解决此类问题？
部分困难在于采取贪婪的方法是行不通的。如果S_1 = [A, B, C]and S_2 = [D, E, F], and distance(A, D) = 0.1, distance(A, E) = 0.3, distance(A, F) = 0.4, 你不能仅仅因为它在这个集合中的距离最小就天真地匹配A到。D假设distance(B, D) = 0.1,distance(B, E) = 0.8和distance(B, F) = 0.9。如果您在第一次迭代中天真地选择匹配(A, D)，那么您实际上会使总距离更高，因为这会迫使您匹配(B, E)或(B, D)。(A, E)匹配然后允许匹配将是一个更好的选择(B, D)。这意味着您不能S_1根据 的每个元素S_1与S_2.
这似乎类似于分配问题，我可以使用匈牙利算法（https://en.wikipedia.org/wiki/Hungarian_algorithm）之类的方法来解决，但我相信该算法允许重用元素，这对我来说不起作用案子。