我正在开发一个程序，将对象分为两组，并且我有每个对象与其他对象相似度的测量结果，我想找到最佳匹配它们的方法。
如果这些集合是单词，距离由编辑距离定义，则“this”，“is”，“a”，“test”集合与“and”，“this”，“is”，“best”的最佳匹配方式是，我会将“this”与“this”（得分为0），“is”与“is”（得分为0），“a”与“and”（得分为2），并将“best”与“test”匹配（得分为1）。
我已经将问题简化为寻找最大二分匹配问题。下面是描述：
给定一个具有整数权重边的二分图，找到一组边，使得（a）每个顶点在集合中仅有一条边，（b）此集合中的权重之和最大。
我不认为这个问题是NP完全的（即使它并非如此，但算法可能非常慢），是否有某种方法可以近似答案至某种良好程度？
目前，我选择最小权重边，将其及其连接的节点删除，然后重复此过程，但这似乎不是最优解。我考虑将其简化为某种流问题（正如您对正常二分图匹配所做的那样），但在这种情况下，它不起作用。
如果这些集合是单词，距离由编辑距离定义，则“this”，“is”，“a”，“test”集合与“and”，“this”，“is”，“best”的最佳匹配方式是，我会将“this”与“this”（得分为0），“is”与“is”（得分为0），“a”与“and”（得分为2），并将“best”与“test”匹配（得分为1）。
我已经将问题简化为寻找最大二分匹配问题。下面是描述：
给定一个具有整数权重边的二分图，找到一组边，使得（a）每个顶点在集合中仅有一条边，（b）此集合中的权重之和最大。
我不认为这个问题是NP完全的（即使它并非如此，但算法可能非常慢），是否有某种方法可以近似答案至某种良好程度？
目前，我选择最小权重边，将其及其连接的节点删除，然后重复此过程，但这似乎不是最优解。我考虑将其简化为某种流问题（正如您对正常二分图匹配所做的那样），但在这种情况下，它不起作用。