1

给定一个二维数组，例如：

 -----------------------
|   | 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数和行数在哪里）。

我的第一个想法是根据儿子的编号按升序对行进行排序。下面是算法的样子：

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

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

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

4

1 回答 1

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]
于 2013-05-23T20:53:43.033 回答