algorithm - 覆盖网格中的单元所需的最少激光器数量？

我在一次采访中被问到这个问题。我正在修改这个问题，以防止它被明确地用 Google 搜索，但要点是:

您将获得一个 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”，但打开激光很昂贵，杀死好的细胞很糟糕。

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

什么是“GoodConfig”，它可以最大限度地减少杀死的好细胞数量？

最佳答案

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

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

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

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

关于algorithm - 覆盖网格中的单元所需的最少激光器数量？，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/23416131/