我正在寻找一种计算效率高的算法来解决以下类型的分配问题：
我有两组点。集合 A 有 N 个点，集合 B 有 M 个点。我想建立从 A 到 B 的一对多分配，其中 A 中的每个元素在 B 中最多可以有两个匹配且至少为零匹配。显然，在这个二分图中，边的成本不为零。此外，匹配是唯一的——A 中的两个元素不能分配给 B 中的同一个元素。
我首先想到了使用匈牙利算法，但它总是找到一对一的匹配，这使得它不能直接适用于我的情况。所寻求的算法也应该能够解释 1 对 0 和 1 对 2 分配。
你从文献中知道任何这样的算法吗？
我会用匈牙利算法来启动我的问题。这为您提供了最低成本分配。然后，我将遵循一个贪心程序：在 A 中选择一个点并将其分配给 B 中的点，与第一个分配的距离最近（通过匈牙利语获得）。如果该点已经包含 2 个匹配项，请跳至 B 中的下一个匹配项（如果您的分配是唯一的，则永远不会发生这种情况）。然后，在 A 中取第二点并迭代。您可以通过在集合 B 上维护动态 LUT 来有效地做到这一点。
这当然是贪婪的，绝不是最优的。然而，我的经验是，这样的算法在实践中给出了合理的结果。
这个问题可以通过匈牙利算法（或任何其他分配问题的算法）来解决。只需将 A 的每个元素复制两份。
如果连接到，从两个副本的每一个中添加一条边到 . 现在在这个二分图中寻找最大权重匹配。结果将解决您的问题。
这可以有效地找到您的问题的精确全局最优解。您不必满足于近似值或局部最优值；这找到了最好的解决方案。