-1

X2D 配列内のすべての s を s に変更する必要があるという問題があり、0そのために必要な最小ステップ (1 つのステップが行全体または列全体の変更で構成される) を計算する必要があります。たとえば、次のような配列で-

[[X, X, X],
 [X, 0, 0],
 [X、0、0]]

ここで必要なステップの最小数は 2 です。

私はブルートフォースアプローチを考えました（行ごとに1回、列ごとにチェックし、それらを比較して最小ステップ数をチェックします）が、それは3の答えを与えますが、これは望ましい出力ではありません.

これにアプローチする最適な方法は何でしょうか?

この問題にどのように取り組むべきかについての助けや手がかりをいただければ幸いです。

4

1 に答える 1

3

ヒント1

各行と各列に頂点を持つグラフを考えてみましょう。

M[i,j] の行列に X がある場合、頂点 r_i と c_j の間にエッジがあるとします。

ヒント2

問題は、すべてのエッジ (つまり、すべての X) がセット内の少なくとも 1 つの頂点に接するように、一連の頂点を選択しようとしている (つまり、行と列を選択しようとしている) と言えます。

これを最小頂点被覆問題と呼びます。

ヒント3

一般に、頂点カバーは NP 完全ですが、この場合、グラフは 2 部になります。

ヒント4

最大フロー アルゴリズムを使用して 2 部最小頂点カバーを解決し、行と列の間の最大一致を計算できます。(詳細については、 Konig の定理を参照してください。)

解決

Python の場合:

import networkx as nx

M=[ [1,1,1],
    [1,0,0],
    [1,0,0] ]

G = nx.DiGraph()
for i,row in enumerate(M):
    for j,c in enumerate(row):
        if c:
            G.add_edge('row'+str(i),'col'+str(j), capacity=1.0)

for i in range(len(M)):
    G.add_edge('x','row'+str(i), capacity=1.0)

for j in range(len(M[0])):
    G.add_edge('col'+str(j), 'y', capacity=1.0)

print nx.max_flow(G, 'x', 'y')
于 2013-10-05T20:15:51.443 に答える