匹配加权不平衡二部图

Question

我正在寻找一种解决赋值问题的方法，但我在找到正确的算法时遇到了一些问题。

我有两个节点A和B的列表，在我的问题中，A的长度可能不等于B。

此外，A中的节点a可能不是与B中所有节点的潜在匹配。优先顺序由双倍提供，其中0对非常感兴趣的1不感兴趣，然后在后面删除边缘为0的所有匹配(因为可能存在不可能的匹配)。

如果a有x到b的偏好，那么b对a也有相同的偏好。

示例图：

我感兴趣的是创建最优匹配，这意味着边之和是最大的可能。在上面的例子中，我会对匹配(1,1)和(3,2)感兴趣，使左行中的2不匹配，总边缘权重为1.9。

我一直在研究稳定婚姻和匈牙利算法，但这两种算法都要求两边都有相同数量的节点，而它们并没有找到最大的总边缘权重。

(最高或最低的是罚款，因为我只需要倒转边的重量)

你们中有人能为我指出解决这个问题的算法吗？

Answer 1

您可以将虚拟节点添加到具有权重为0的B到A中的节点，然后反转边的权重。检查http://en.wikipedia.org/wiki/Assignment_问题和我认为你可以应用匈牙利算法对这个问题进行修改，并在找到最小总成本后，你可以再次倒置权重。