1

次のような 2 次元配列があるとします。

 -----------------------
|   | 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 |       
 -----------------------

行ごとに最大 1 つのセルと列ごとに 1 つのセルを含む、現在含まれている最大のセルのセット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/

このアルゴリズムは、最大二部マッチング問題を解決するいくつかのアルゴリズムの 1 つであり、そのコードを正確に「そのまま」使用して、投稿 (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 に答える