algorithm - 了解具有位移位和 XOR 的五维 DP？

Question

我正在查看 this 的解决方案问题 here ，我不太明白动态规划 (DP) 是如何工作的。

---

问题的总结如下:给定一个由 1 或 0 组成的 9x9 网格，排列成九个 3x3 子网格，如下所示:

000 000 000
001 000 100
000 000 000

000 110 000
000 111 000
000 000 000

000 000 000
000 000 000
000 000 000

您需要找到所需的最少更改次数，以使九行、九列和 3x3 子网格中的每一个都包含偶数个 1。在这里，更改被定义为将给定元素从 1 切换到 0，反之亦然。

---

该解决方案涉及动态规划，每个状态都包含最少数量的移动，使得直到当前行的所有行都具有偶数奇偶校验(偶数个)。

但是，我不明白它们的实现细节。首先，在他们的内存数组中

int memo[9][9][1<<9][1<<3][2];

每个索引代表什么？我收集到前两个用于当前行和列，第三个用于列奇偶校验，第四个用于子网格奇偶校验，第五个用于行奇偶校验。但是，为什么列校验需要 2^9 个元素，而行校验只需要 2 个？

接下来，如何处理状态之间的转换？我会假设你穿过行尝试每个元素并在完成后移动到下一行，但在看到他们的代码后我很困惑

  int& ref = memo[r][c][mc][mb][p];

  /* Try setting the cell to 1. */
  ref = !A[r][c] + solve(r, c + 1, mc ^ 1 << c, mb ^ 1 << c / 3, !p);

  /* Try setting the cell to 0. */
  ref = min(ref, A[r][c] + solve(r, c + 1, mc, mb, p));

他们如何通过翻转网格中的当前位来尝试将单元格设置为 1？我明白当你把它变成一个时，行奇偶校验是如何改变的，如 !p 所示。但我不明白列奇偶校验将如何受到影响，或者是什么 mc ^ 1 << c确实——为什么需要异或和移位？子网格奇偶校验也是如此——mb ^ 1 << c / 3 .它在做什么？

有人可以解释一下这些是如何工作的吗？

Answer 1

我想我已经弄明白了。这个想法是从上到下，从左到右扫过。在每一步，我们都尝试通过将当前框设置为 0 或 1 来移动到下一个位置。

在每一行的末尾，如果奇偶校验是偶数，我们继续下一行；否则我们回溯。在每三行的末尾，如果所有三个框的奇偶校验都是偶数，我们继续下一行；否则否则我们回溯。最后，在棋盘的最后，如果所有的列都相等，我们就完成了；否则我们回溯。

任何一点的递归状态都可以用以下五种信息来描述:

• 当前行和列。
• 所有列的奇偶性。
• 我们当前所在的三个框的奇偶性(每行与三个相交)。
• 列的当前奇偶性。

这是内存表的样子:

int memo[9][9][1<<9][1<<3][2];
         ^  ^    ^     ^   ^
         |  |    |     |   |
   row --+  |    |     |   |
   col -----+    |     |   |
column parity ---+     |   |
  box parity ----------+   |
current row parity---------+

要了解为什么会有移位，让我们看一下列奇偶校验。有 9 列，所以我们可以将它们的奇偶校验写成 9 位的位向量。等效地，我们可以使用九位整数。 1 << 9给出可能的九位整数的数量，因此我们可以使用单个整数同时对所有列奇偶校验进行编码。

为什么要使用 XOR 和移位？好吧，将位向量 A 与第二个位向量 B 进行异或运算会反转 A 中在 B 中设置的所有位，并保持所有其他位不变。如果您正在跟踪奇偶校验，则可以使用 XOR 来切换各个位以表示奇偶校验翻转；发生移位是因为我们将多个奇偶校验位打包到一个机器字中。你说的划分是从列索引映射到它所经过的框的水平索引。

希望对您有所帮助!