algorithm - 用最少的步数将矩阵中的所有 X 变为 0

Question

我有一个问题，我必须将X2D 数组中的所有 s 更改为0s，并且我必须计算这样做所需的最小步骤（其中单个步骤包括更改整个行或列）。例如，在一个数组中 -

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

此处所需的最小步骤数为 2。

我想到了一种蛮力方法（我按行检查一次，然后按列检查，然后比较它们以检查哪个步骤最少），但这会给我一个 3 的答案，这不是所需的输出.

解决此问题的最佳方法是什么？

任何关于我应该如何解决这个问题的帮助或线索将不胜感激，谢谢！

Answer 1

提示 1

考虑每行和每列都有一个顶点的图。

如果在 M[i,j] 处的矩阵中存在 X，则在顶点 r_i 和 c_j 之间存在一条边。

提示 2

您的问题可以描述为试图选择一组顶点（即选择行和列），使得每条边（即每个 X）至少接触集合中的一个顶点。

这称为最小顶点覆盖问题。

提示 3

一般来说，顶点覆盖是 NP 完全的，但在这种情况下，图是二分的。

提示 4

您可以使用最大流算法求解二分最小顶点覆盖，以计算行和列之间的最大匹配。（有关详细信息，请参阅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')