algorithm - 覆盖网格中的细胞所需的最少激光数量？

Question

我在面试中被问到这个问题。我正在稍微修改这个问题，以防止它被明确地谷歌化，但要点是:

给你一个 N x M 网格。网格中的一些单元格是“坏的”(用数字 1 表示)，其余的是“好”的(用 0 表示)。您在每个 N 行和每个 M 列上放置了激光，当这些激光打开时会杀死其各自行或列中的所有细胞，例如如果你有:

   L1 L2 L3 L4
L5  0  1  0  0
L6  0  1  0  1
L7  0  1  1  0
L8  0  0  0  0

您可以打开(L2、L3、L4)之一:

   L1 L2 L3 L4
L5  0  x  x  x
L6  0  x  x  x
L7  0  x  x  x
L8  0  x  x  x

或者您可以打开(L2、L6、L7):

   L1 L2 L3 L4
L5  0  x  0  0
L6  x  x  x  x
L7  x  x  x  x
L8  0  x  0  0

一组打开的激光被称为“GoodConfig”，前提是它杀死了所有邪恶的细胞。请注意，您始终可以打开一行或一列的所有激光器并杀死所有东西，这将是“GoodConfig”，但打开激光器的成本很高，杀死好细胞是不好的。

1. “GoodConfig”的最小尺寸是多少，即在杀死所有邪恶细胞之前我们可以打开的最少激光数量？

2. 什么是最小化杀死的好细胞数量的“GoodConfig”？

Answer 1

这个问题可以重新表述为二部图上的最小顶点覆盖问题。

考虑一个图:顶点是行(一部分)和列(另一部分)。当且仅当相应的单元格 (row, col) 是邪恶的时，顶点 row 和 col 之间存在边。

我们现在的问题是找到一组具有最小可能大小的顶点，以便我们图形的每条边(前单元格)在我们的集合(行或列)中至少有一个顶点。

根据 Koenig's Theorem ，我们可以在我们的二分图中找到最大匹配，然后在匹配的每条边上准确标记一个顶点，使得生成的顶点集覆盖上述意义上的图。特别地，最大匹配的大小等于最小顶点覆盖的大小。