algorithm - 如何找到匹配数据的最大数量？

Question

给定一个双向数组，例如:

 -----------------------
|   | 1 | 2 | 3 | 4 | 5 |
|-------------------|---|
| 1 | X | X | O | O | X |
|-------------------|---|
| 2 | O | O | O | X | X |        
|-------------------|---|
| 3 | X | X | O | X | X |       
|-------------------|---|
| 4 | X | X | O | X | X |       
 -----------------------

我必须找到 当前包含 O 的最大一组单元格，每行最多一个单元格，每列最多一个单元格。

例如，在前面的例子中，最佳答案是3，当:

1. 第 1 行与第 4 列一致；
2. 第 2 行与第 1(或 2)列一致；
3. 第 3(或 4)行与第 3 列一致。

看来我必须在 O(CR) 中找到一个算法(其中 C 是列数，R 是数字行数)。

我的第一个想法是根据 son 上的编号对行进行升序排序。下面是该算法的样子:

For i From 0 To R
    For j From 0 To N
        If compatible(i, j)
            add(a[j], i)

Sort a according to a[j].size

result = 0

For i From 0 To N
    For j From 0 to a[i].size
         if used[a[i][j]] = false
             used[a[i][j]] = true
             result = result + 1
             break

Print result

虽然我没有找到任何反例，但我不知道它是否总是给出最优答案。

这个算法正确吗？有没有更好的解决方案？

Answer 1

根据 Billiska 的建议，我在这里找到了 Python 中“Hopcroft-Karp”算法的一个很好的实现:

http://code.activestate.com/recipes/123641-hopcroft-karp-bipartite-matching/

该算法是解决最大二分匹配问题的几种算法之一，完全“按原样”使用该代码以下是我如何解决您帖子中的示例问题(使用 Python):

from collections import defaultdict
X=0; O=1;
patterns = [ [ X , X , O , O , X ],
             [ O , O , O , X , X ],        
             [ X , X , O , X , X ],       
             [ X , X , O , X , X ]] 

G = defaultdict(list)

for i, x in enumerate(patterns):
    for j, y in enumerate(patterns):
        if( patterns[i][j] ):
            G['Row '+str(i)].append('Col '+str(j))

solution = bipartiteMatch(G) ### function defined in provided link
print len(solution[0]), solution[0]