algorithm - 通过切换行和列将二进制矩阵转换为 0？

Question

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

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

Answer 1

解决此问题的一种可能方法是将此问题视为 linear system of equations ，除了只使用 0 和 1 而不是实数。

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

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 是 associative和 commutative ((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 对这个等式的两边进行异或。由于 A XOR A = 0，这就抵消了左边的 A。由于 A XOR 0 = A，这会将 A 移到右侧。现在我们有

b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR 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 (顺便说一下，这是一个转置)。在这种情况下，我们可以将上述系统重写为

Tb = A

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

那么这有多有效呢？那么，矩阵 T 的大小为 mn × mn。因此，在其上运行高斯消除将花费 O(m3n3) 时间，这虽然很大，但对于相当小的网格来说仍然不算太糟糕。我们也可以通过简单地找出哪些条目被切换来在 O(m2n2) 时间内构建网格。总的来说，这为您的问题提供了 O(m3n3) 算法。好极了!

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

希望这可以帮助!