8

假设给定一个由 0 和 1 组成的网格。您的目标是通过执行一系列“翻转”操作将网格变成全零的网格：如果您翻转网格中的位置 (x, y)，则与 (x) 位于同一行或列中的所有位, y) 被翻转。

有谁知道可以用来解决这个问题的有效算法？

4

1 回答 1

29

解决这个问题的一种可能方法是将这个问题视为一个线性方程组，除了只使用 0 和 1 而不是实数。

数字 0 和 1 在 XOR 和 AND 操作下形成一个字段（顺便说一下，这个字段称为GF(2)）。也就是说，您可以通过 XOR 将两个位“相加”在一起，并且您可以通过 AND 将两个位“相乘”在一起。事实证明，XOR 和 AND 的行为与正常乘法和加法的许多属性相匹配——例如，乘法和加法是可交换的和结合的，并且乘法分布在加法之上。事实证明，这些属性足以让您使用高斯消元法求解 0 和 1 上的线性方程组。例如，可以使用高斯消元法求解这个线性方程组：

x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0

因此，如果我们可以用 XOR 和 AND 的线性方程组来表达您的问题，那么您可以通过在该字段上使用标准高斯消元法在多项式时间内解决问题。

要做到这一点，首先要注意反转一个位等效于与 1 进行异或运算：

  • 0 异或 1 = 1
  • 1 异或 1 = 0

这意味着，如果您切换整个行和列，则相当于将该行和列中的所有内容与值 1 进行异或。

现在，假设您有一个由 0 和 1 组成的 m × n 矩阵。我们将用 A[i][j] 表示第 i 行第 j 列中的数字的值。由于切换 (i, j) 切换同一行和列中的所有元素，您可以想象切换 (i, j) 相当于将原始矩阵 A 异或到一个新矩阵 A，如下所示：

0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
1 1 ... 1 1 1 ... 1
0 0 ... 0 1 0 ... 0
        ...
0 0 ... 0 1 0 ... 0
0 0 ... 0 1 0 ... 0

在这里，1 在第 i 行和第 j 列中，而 0 在其他任何地方。

请注意，网格中的每个位置都会产生这些“切换矩阵”之一，因此执行“翻转（i，j）”操作的效果是将当前矩阵与切换矩阵编号（i，j）进行异或。

现在进行另一个关键观察：对于这个问题，没有最佳解决方案（一个操作次数最少的解决方案）会两次翻转相同的位置。这样做的原因是 XOR 自身反转：a XOR a = 0。因此，任何翻转相同位置两次的解都可以通过移除两次翻转来缩短以获得更短的解。此外，由于 XOR 是关联和可交换的（(x XOR y) XOR z = x XOR (y XOR z) 和 x XOR y = y XOR x），我们执行翻转的顺序无关紧要以获得最优解决方案。一旦您知道要进行哪些翻转，您所要做的就是按照您想要的任何顺序进行翻转。

将所有这些结合在一起，我们试图确定，对于每个可能的翻转，我们是否应该执行该翻转。订购和数量无关紧要。

这是我们得到实际线性方程组的地方。我们得到了一个起始矩阵 A 和一堆不同的“切换矩阵”，一个用于我们可以做的每个不同的翻转。让我们用 T[i, j] 表示位置 (i, j) 的切换矩阵。然后我们将引入新变量 b[i, j] 为 0 或 1 值，指示我们是否应该实际翻转位置 (i, j)。鉴于此设置，我们正在寻找 b[i, j] 的一组值，使得

A XOR b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = 0

其中 0 是零矩阵。如果可以找到可行的 b 选项，那么您就有了解决方案。如果不是，则不存在解决方案。现在的问题是如何找到它们。

为此，我们将对上述系统进行一个小改动。让我们用 A 对这个等式的两边进行 XOR。由于 A XOR A = 0，这从左侧抵消了 A。由于 A XOR 0 = A，这会将 A 移到右侧。现在我们有

b[1, 1]T[1, 1] 异或 b[1, 2]T[1, 2] 异或 ...异或 b[m, n]T[m, n] = A

最后，我们将再做一项更改。与其将 A 和 T[i, j] 表示为矩阵，不如将它们表示为行优先顺序的列向量。这意味着上述线性方程组实际上不能被认为是矩阵的和，而是列向量的和。

为了达成交易，让我们定义一个矩阵 T，其中 T 的第一列是 T[1, 1]，T 的第二列是 T[1, 2], ...，T 的第 mn 列是 T[m, n]。然后，让我们让 b = (b[1, 1], b[1, 2], ..., b[m, n])^T （顺便说一下，这是一个转置）。在这种情况下，我们可以将上述系统重写为

结核病=一个

这很漂亮！我们现在尝试求解向量 b，使得 T 乘以 b 得到矩阵 A。如上所述，由于具有 XOR 和 AND 的 0 和 1 形成一个场，您可以使用标准高斯消元法来求解该系统。

那么这效率如何？好吧，矩阵 T 的大小为 mn × mn。因此，对其运行高斯消元法将花费时间 O(m 3 n 3 )，这虽然很大，但对于相当小的网格来说仍然不算太糟糕。我们也可以在 O(m 2 n 2 ) 时间内构建网格，只需弄清楚哪些条目会被切换。总体而言，这为您的问题提供了 O(m 3 n 3 ) 算法。耶！

我为游戏“Lights Out”提供了一个求解器的实现，它与这个问题非常相似，只是切换只翻转 (i, j) 附近的灯，而不是翻转整个行和列。它基于完全相同的方法，因此如果您想获取代码并将其用作起点，您可能可以在短时间内编写此求解器。我试图在代码的相关部分添加注释以使其易于阅读，因此希望它有用。

希望这可以帮助！

于 2013-01-05T07:15:44.943 回答