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