通过切换行和列将二进制矩阵转换为0？ [英] Converting a binary matrix to 0s by toggling rows and columns?
问题描述
解决这个问题的一个可能办法是把这个问题当作线性方程组a>，除了使用0和1而不是实数。
数字0和1形成一个字段在操作XOR和AND（此字段称为 GF（2），顺便说一下）。也就是说，您可以通过将它们相加在一起来添加两个位，并且可以通过将它们进行AND运算来乘两个位。事实证明，XOR和AND的行为与正常乘法和加法乘法和加法的许多属性匹配是可交换和关联的，例如乘法分配。事实证明，这些属性足以让您使用高斯消除解决线性方程组超过0s和1s。例如，可以使用高斯消除来解决这个线性方程组：
x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0
因此，如果我们能说出你的问题在使用XOR和AND的线性方程组方程中，您可以通过在该字段上使用标准高斯消除来解决多项式时间中的问题。
要做到这一点，首先注意到反转一点相当于使用1进行异或：
- 0 XOR 1 = 1
- 1 XOR 1 = 0
这意味着如果您切换整个行和列，则相当于XORing一切该行和列的值为1。
现在，假设你有一个m× n矩阵为0和1。我们用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是其他地方。
请注意，网格中的每个位置都会产生这些切换矩阵之一，以便执行flip（i，j）操作的效果是使用切换矩阵号（X i，j）。
现在进行另一个关键观察：对于这个问题，没有最优解（最少的操作数）有两次翻转相同的位置。这样做的原因是XOR反转：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.由于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的第m列为T [m，n ]。然后让我们让b =（b [1,1]，b [1,2]，...，b [m，n]）^ T（顺便说一下是转置）。在这种情况下，我们可以将上述系统重写为
Tb = A
这是美丽的！我们现在试图求解一个向量b，使得T乘以b给出矩阵A.如上所述，由于具有XOR和AND的0和1形成一个字段，所以可以使用标准高斯消除来解决该系统。 / p>
那么这么高效？那么矩阵T的大小是mn×嗯因此，运行高斯消除将需要时间O（m 3 n 3 ），对于合理的小网格来说，这是很大的但仍然不太糟糕。我们可以在时间O（m 2 n 2 ）中构建网格，也可以简单地弄清楚哪些条目被切换。总的来说，这给你的问题的O（m 3 n 3 ）算法。 Yay！
我实施了一个 游戏的解决者亮出 ，这与这个问题非常相似，只是切换只能翻转（i，j）附近的灯光，而是比翻转整行和列。它基于完全相同的方法，所以如果你想采取代码并将其用作一个起点，你可能可以在短时间内对该求解器进行编码。我试图向代码的相关部分添加评论，以便于阅读，所以希望它很有用。
希望这有帮助！
Suppose that you're given a grid of 0s and 1s. Your goal is to turn the grid into a grid of all zeros by performing a series of "flip" operations: if you flip position (x, y) in the grid, then all of the bits in the same row or column as (x, y) get flipped.
Does anyone know of an efficient algorithm that can be used to solve this problem?
One possible way to solve this is to treat this problem as a linear system of equations, except using just 0 and 1 instead of real numbers.
The numbers 0 and 1 form a field under the operations XOR and AND (this field is called GF(2), by the way). That is, you can "add" two bits together by XOR-ing them together, and you can "multiply" two bits together by ANDing them. It turns out that the behavior of XOR and AND matches many properties of normal multiplication and addition - multiplication and addition are commutative and associative, and multiplication distributes over addition, for example. It turns out that these properties are sufficient to let you use Gaussian elimination to solve a linear system of equations over 0s and 1s. For example, Gaussian elimination can be used to solve this linear system of equations:
x XOR z = 1
x XOR y XOR z = 0
y XOR z = 0
Consequently, if we can phrase your problem in terms of a linear system of equations using XORs and ANDs, then you can solve the problem in polynomial time by just using standard Gaussian elimination over this field.
To do this, first notice that inverting a bit is equivalent to XOR-ing it with 1:
- 0 XOR 1 = 1
- 1 XOR 1 = 0
This means that if you toggle an entire row and column, it's equivalent to XORing everything in that row and column with the value 1.
Now, suppose that you have an m × n matrix of 0s and 1s. We'll denote by A[i][j] the value of the number in the ith row and the jth column. Since toggling (i, j) toggles all of the elements in the same row and column, you can imaging that toggling (i, j) is equivalent to XORing the original matrix A to a new matrix A that looks like this:
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
Here, the 1s are in row i and column j, and the 0s are everywhere else.
Note that every position in the grid gives rise to one of these "toggle matrices" such that the effect of performing operation "flip (i, j)" is XOR-ing the current matrix with toggle matrix number (i, j).
Now for another key observation: no optimal solution (one with the shortest number of operations) to this problem ever flips the same position twice. The reason for this is that XOR inverts itself: a XOR a = 0. Consequently, any solution that flips the same position twice can be shortened by removing two of the flips to get a shorter solution. Moreover, since XOR is associative and commutative ((x XOR y) XOR z = x XOR (y XOR z), and x XOR y = y XOR x), it doesn't matter what order we perform the flips in for an optimal solution. All you have to do is perform the flips in whatever order you'd like, once you know which flips to do.
Combining all this together, we have that we are trying to determine, for each possible flip, whether or not we should perform that flip. Ordering and quantity don't matter.
Here's where we get to actual linear systems of equations. We're given a starting matrix A and a bunch of different "toggle matrices", one for each of the different flips we can do. Let's denote the toggle matrix for position (i, j) by T[i, j]. We'll then introduce new variables b[i, j] to be a 0 or 1 value indicating whether or not we are supposed to actually flip position (i, j). Given this setup, we are looking for a set of values for the b[i, j]'s such that
A XOR b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = 0
Where 0 is the zero matrix. If it's possible to find a choice of b's that works, then you have your solution. If not, then no solution exists. The question now is how to find them.
To do this, we'll make one small change to the above system. Let's XOR both sides of this equation by A. Since A XOR A = 0, this cancels out the A from the left side. Since A XOR 0 = A, this moves the A to the right side. Now we have
b[1, 1]T[1, 1] XOR b[1, 2]T[1, 2] XOR ... XOR b[m, n]T[m, n] = A
Finally, we'll do one more change. Rather than representing A and the T[i, j]'s as matrices, let's represent them as column vectors in row-major order. This means that the above linear system of equations can actually be thought of not as a sum of matrices, but as a sum of column vectors.
To seal the deal, let's define a matrix T, where the first column of T is T[1, 1], the second column of T is T[1, 2], ..., and the mn-th column of T is T[m, n]. Then, let's let b = (b[1, 1], b[1, 2], ..., b[m, n])^T (that's a transpose, by the way). In that case, we can rewrite the above system as
Tb = A
This is beautiful! We're now trying to solve for a vector b such that T multiplied by b gives the matrix A. As mentioned above, since 0s and 1s with XORs and ANDs forms a field, you can use standard Gaussian elimination to solve this system.
So how efficient is this? Well, the matrix T has size mn × mn. Therefore, running Gaussian elimination on it will take time O(m3n3), which is large but still not too bad for reasonably small grids. We can construct the grid in time O(m2n2) as well by simply figuring out what entries get toggled. Overall, this gives an O(m3n3) algorithm for your problem. Yay!
I have an implementation of a solver for the game "Lights Out", which is extremely similar to this problem except that a toggle only flips the lights in the immediate neighborhood of (i, j), rather than flipping the entire row and column. It is based on the exact same approach, so if you wanted to take the code and use it as a starting point, you could probably code up this solver in a short amount of time. I've tried to add comments to the relevant parts of the code to make it easy to read, so hopefully it's useful.
Hope this helps!
这篇关于通过切换行和列将二进制矩阵转换为0？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
