带权边的二部匹配

Question

我正在开发一个程序，在这个程序中，我将对象分为两组，并测量每个对象与其他对象的相似度，我希望找到将它们匹配在一起的最佳方法。

如果集合是由edit-distance定义的单词和距离，那么集合"this“、"is”、"a“、"test”与" and“、"this”、"is“、"best”的最佳匹配，则我会将"this“与"this”(分数为0)、"is“与"is”(分数为0)、"a“与" and”(分数为2)以及"best“与"test”(分数为1)进行匹配。

我已经将问题简化为寻找一个最大二部匹配类问题。这里有一个描述：

给定一个边具有整数权的二部图，找出(a)每个顶点在该集合中只有一条边，并且(b)该集合中的权重之和具有最大尺寸的一组边。

我不相信这个问题是NP完全的(或者，即使它不是，但如果算法可能非常慢)，是否有某种方法可以在某种程度上近似答案？

目前我选择最小权重的边，移除它和它连接的节点，然后重复，但这似乎不是最优的。我曾想过将其简化为某种流问题(就像您对正常的二部匹配所做的那样)，但它在这种情况下不起作用。

Answer 1

这是maximum bipartite matching problem (加权)。它有一个使用扩充路径的多时间解决方案。