在多项式时间内将网格变为全 1 的相邻位的最小切换

Question

我想出了一个类似这样的编程问题：

假设您有一个 NxN 二进制网格。 “点击”一个方块会切换它以及所有边缘相邻的方块。找到将网格转换为全 1 的最短“抽头”序列。

最容易看到的算法是 BFS，我们从全 1 的网格开始，重复访问距离当前板仅一“点击”的每个板，同时确保我们不会两次访问板。然而，由于有 2^(n^2) 个棋盘状态，这是一个非常低效的算法。

我能够找到 N <= 3, but it breaks down for N>=4 的多项式时间 (O(n^2)) 算法，因为它依赖于每个棋盘都是可解的这一事实。

有N>=4的多项式时间算法吗？

谢谢！

Answer 1

你确实可以在这里使用记忆功能。

首先我们来分析一下递归关系。

定义：

• 𝑆_𝑛 是从顶点到自身的长度为 𝑛 的路径数。

• 𝐷_𝑛 是从一个顶点到选定的不同 的长度为𝑛 的路径数。我们选择哪个目标顶点并不重要，因为四面体是完全对称的。

现在递归关系：

要递归地获取到原始顶点 (𝑆_𝑛) 的长度为 𝑛 的路径数，您可以从三个邻居中选择一个邻居，然后计算从那里回到起始顶点的（较短）路径的数量，即由𝐷给出。所以：

• 𝑆_𝑛 = 3𝐷_𝑛−1

要递归地获取到不同顶点（𝐷_𝑛）的长度为𝑛的路径数，您可以选择that邻居并计算从那里到自身的（较短）路径的数量，或者您可以选择其他两个邻居之一，并计算从那里到目标顶点的（较短）路径的数量。所以：

• 𝐷_𝑛 = 𝑆_𝑛−1 + 2𝐷_𝑛−1

后一个方程可以通过替换到这个方程来展开：

• 𝐷_𝑛 = 3𝐷_𝑛−2 + 2𝐷_𝑛−1

实施

由于𝐷有一个很好的递归关系，我们可以首先实现一个函数，返回从一个顶点到另一个顶点的路径数。然后使用第一个递归关系将原始查询（指向 same 顶点的路径数）转换为该问题：

// Memoize the number of paths from one vertex to a different one
const memo = new Map().set(0, 0).set(1, 1);

function numPathsToOther(size) {
    if (!memo.has(size)) {
        memo.set(size, 3*numPathsToOther(size-2) + 2*numPathsToOther(size-1));
    }
    return memo.get(size);
}

function numPathsToSelf(size) {
    return size ? 3 * numPathsToOther(size - 1) : 1;
}

// Demo runs for the first few path-sizes:
for (let i = 0; i <= 10; i++) {
    console.log(i, numPathsToSelf(i));
}