algorithm - 二部图的边权重

Question

我很难理解某些逻辑。我有一个如下图。

我希望找到左侧所有顶点的最佳匹配（即，A1，A2，A3，A4）。我从朋友那里得到一个建议，可以使用边缘权重的总和来解决这个问题。但是，我不确定边缘权重的总和在这种情况下会有什么帮助。例如，对于 A1，我可以说 AL2 是最佳匹配，依此类推。但是，我的朋友建议边缘权重是解决此问题的最佳解决方案。我无法理解它如何成为最佳解决方案。他的想法是，所有 (A1,A2,A3,A4) 都将连接到所有 (AL1,AL2,..,AL6) 并且对于每条边，我们将计算边权重的总和。有人可以帮我理解他的实际意思吗？

编辑：我认为这可能不是二分图中完美匹配的情况，因为左侧的节点应该等于右侧的节点。

Answer 1

使用最大流算法可以在多项式时间内有效地计算最大加权二分匹配，这是线性程序的一种特殊情况。二分匹配、最大流和线性规划之间存在多种关系，但Hopkroft-Karp 算法是解决此特定问题的算法的最简洁表达。

也可以有效地计算非二分图的最大匹配。

（以上所有算法都有加权版本。）

编辑：从您的评论中不清楚您是否有稍微不同的问题。如果可以存在从左到右的一对多映射，但右节点只能映射到一个左节点，则实际上存在最大流问题，其中左节点具有无限容量流入，而右节点具有外流能力之一。请参阅最大流量算法以了解不同的解决方法。