理解具有位移位和XOR的五维DP？

Question

我正在研究这 problem 这里的解决方案，但我不太明白动态编程(DP)是如何工作的。

问题的总结如下:给您一个9x9的1或0的网格，按以下方式排列在9个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));

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

谁能解释一下这些东西是怎么工作的吗？

Answer 1

解决方案中的算法是一个彻底的深度优先搜索和一对优化。不幸的是，描述并没有确切地解释这一点。

穷尽搜索意味着我们试图枚举每一个可能的比特组合。深度-首先意味着我们首先尝试将所有比特设置为1，然后将最后一个设置为零，然后是第二个到最后，然后是最后和第二个到最后，等等。

第一个优化是，一旦我们检测到奇偶性不是偶数，就立即回溯。因此，例如，当我们开始搜索并到达第一行时，我们检查该行是否具有零奇偶。如果没有，我们就不继续了。我们停止，回溯，并尝试将行中的最后一个位设置为零。

第二个优化是类似于DP的，因为我们缓存部分结果并重用它们。这利用了这样一个事实:就问题而言，搜索中的不同路径可以收敛到相同的逻辑状态。什么是逻辑搜索状态？解决方案中的描述开始解释它(“开始”是关键词)。本质上，诀窍是，在搜索的任何一点上，附加位翻转的最小数量并不取决于整个sudoku板的确切状态，而仅取决于我们需要跟踪的各种参数的状态。(见下文的进一步解释)我们正在跟踪的空间有27个(包括9列、9行和9 3x3框)。此外，我们还可以优化其中的一些。考虑到我们执行搜索的方式，所有较高行的奇偶性将始终是均匀的，而所有较低行的奇偶性(尚未被搜索所触及)不会改变。我们只跟踪1行的奇偶。按照同样的逻辑，上面和下面的框的奇偶性被忽略了，我们只需要跟踪“活动”的3个框。

因此，不是2^9 * 2^9 * 2^9 = 134,217,728个状态，而是只有2^9 * 2^1 * 2^3 = 8,192个状态。不幸的是，我们需要一个单独的缓存为每个深度级别的搜索。所以，我们用81种可能的深度乘以搜索，发现我们需要一个大小为663,552的数组。向临时胡枝子借款：

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

1<<9 simply means 2^9, given how integers and bit shifts work.

进一步的解释:由于奇偶校验的工作方式，一个位翻转总是会翻转它的三个对应的参数。因此，具有相同参数的sudoku板的所有排列都可以用相同的位翻转获胜模式来解决。这个函数给出了这个问题的答案：“假设你只能从(x，y)的单元格开始执行位翻转，那么得到解决板的位翻转的最小数量是多少？”所有同属的sudoku板都会给出相同的答案。搜索算法考虑了板的许多排列。它开始从顶部修改它们，计算它已经做了多少位翻转，然后请求函数“解决”，看看它还需要多少。如果已经用相同的值(x，y)和相同的参数调用了‘same’，我们可以只返回缓存的结果。

令人困惑的部分是实际执行搜索和更新状态的代码：

/* 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));

它可以更明确地表述为：

/* Try having this cell equal 0 */
bool areWeFlipping = A[r][c] == 1;
int nAdditionalFlipsIfCellIs0 = (areWeFlipping ? 1 : 0) + solve(r, c + 1, mc, mb, p); // Continue the search

/* Try having this cell equal 1 */
areWeFlipping = A[r][c] == 0;
// At the start, we assume the sudoku board is all zeroes, and therefore the column parity is all even. With each additional cell, we update the column parity with the value of tha cell. In this case, we assume it to be 1.
int newMc = mc ^ (1 << c); // Update the parity of column c. ^ (1 << c) means "flip the bit denoting the parity of column c"
int newMb = mb ^ (1 << (c / 3)); // Update the parity of 'active' box (c/3) (ie, if we're in column 5, we're in box 1)
int newP = p ^ 1; // Update the current row parity
int nAdditionalFlipsIfCellIs1 = (areWeFlipping ? 1 : 0) + solve(r, c + 1, newMc, newMb, newP); // Continue the search

ref = min( nAdditionalFlipsIfCellIs0, nAdditionalFlipsIfCellIs1 );

就我个人而言，我会把搜索的两个方面实现为“翻转”和“不要翻转”。这使得算法在概念上更有意义。它会让第二段读成：“深度--首先意味着我们先尝试不翻转任何比特，然后翻转最后一个，然后是第二个到最后，然后是最后和第二个到最后，等等。”此外，在开始搜索之前，我们需要为我们的板预先计算'mc‘、'mb’和'p‘的值，而不是传递0。

/* Try not flipping the current cell */
int nAdditionalFlipsIfDontFlip = 0 + solve(r, c + 1, mc, mb, p);

/* Try flipping it */
int newMc = mc ^ (1 << c);
int newMb = mb ^ (1 << (c / 3));
int newP = p ^ 1;
int nAdditionalFlipsIfFlip = 1 + solve(r, c + 1, newMc, newMb, newP);

ref = min( nAdditionalFlipsIfDontFlip, nAdditionalFlipsIfFlip );

但是，这种更改似乎不会影响性能。

更新

最令人惊讶的是，该算法的惊人速度的关键似乎是回忆录阵列最终变得相当稀疏。在每个深度级别，通常有512个(有时是256个或128个)访问状态(在8192个中)。此外，它始终是每列奇偶校验的一个状态。包厢和划船的问题似乎并不重要！将它们从回忆录数组中删除将提高30倍的性能。不过，我们能否证明这是真的呢？

Answer 2

我想我已经搞清楚了。这个想法是从上到下，从左到右。在每一步，我们尝试移动到下一个位置，将当前框设置为0或1。

在每一行的末尾，如果奇偶性为偶数，我们将移到下一行；否则，我们将返回。在第三行的末尾，如果所有三个框的奇偶相等，我们将移到下一行；否则我们将返回。最后，在板的末尾，如果所有列都有偶数奇偶，我们就完成了；否则我们就后退。

递归在任何点的状态可以用以下五条信息来描述：

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

这是回忆录表的样子：

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

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

为什么要使用异或和位移位？好的，XORing一个位向量A和第二个位向量B反转A中所有在B中设置的位，并保持所有其他位不变。如果要跟踪奇偶校验，可以使用XOR来切换单个位以表示奇偶转换；之所以会发生移位，是因为我们将多个奇偶位打包到一个机器字中。您所引用的分区是将列索引映射到它传递的框的水平索引。

希望这能有所帮助！