我正在开发一个程序，我将对象分成两组，并且我测量了每个对象与其他对象的相似程度，我想找到将它们匹配在一起的最佳方法。
如果集合是由edit-distance定义的单词和距离，那么集合“this”、“is”、“a”、“test”与“and”、“this”、“is”的最优匹配， “best”，然后我会将“this”与“this”（得分为 0）、“is”与“is”（得分为 0）、“a”与“and”（得分为2)，以及“最好”与“测试”（得分为 1）。
我已经将问题简化为找到一个最大的二分匹配问题。这是一个描述：
给定一个边具有整数权重的二部图，找到一组边，使得 (a) 每个顶点在集合中只有一条边，并且 (b) 该集合中的权重之和具有最大大小。
我不相信这个问题是 NP 完全的（或者，即使不是，但如果算法可能非常慢），是否有某种方法可以在一定程度上近似答案？
目前我选择最小权重边缘，删除它和它连接的节点，然后重复，但这似乎不是最理想的。我曾考虑将其减少为某种流问题（就像您使用正常的二分匹配一样），但在这种情况下它不起作用。