algorithm - 找到关闭灯的最少按下次数

Question

我试图解决一个编程问题，但我无法看到一个有效的算法。情况是这样的:我们有一套n可以打开的灯 (1)或关闭 (0)像这样:1110001011101 .该字节串表示有 13灯形成一个圆圈，其中前三个灯亮，然后 3下关等和circle意味着最后一盏灯在第一盏灯旁边。

然后我们得到了一个整数 m>0 .这意味着在任何时候我们都可以选择一盏灯，然后选择它和它的m adjacent灯改变状态 s to 1-s . IE。如果 m=2和灯状态是 1110001011101然后将该过程应用于第一盏灯，我们得到序列 0000001011110 .

现在的问题是，如果字符串的长度约为 2200和 m关于 110是固定的，如何开发algorithm那个shut downs all灯带 minimum转弯数量？

Answer 1

这个问题类似于众所周知的“熄灯”问题。 http://en.wikipedia.org/wiki/Lights_Out_%28game%29一种方法是使用线性代数。使用较小的数字更容易理解，例如长度 = 5 和 m = 1。

首先请注意，选择一盏灯并更改它(及其邻居的)状态两次没有任何影响。其次请注意，灯(及其邻居)的开关顺序无关紧要。因此，策略只是一组灯。我们将用 1 表示被选择作为策略一部分的灯和未被 0 选择的灯。我们将 1 和 0 放在列向量中，例如，(0 1 1 0 1)^T其中 T 用于转置(行变成列)。该策略意味着在位置 1(当然从位置 0 开始)及其两个相邻位置切换灯；然后是位置 2 的灯和它的两个邻居，最后是位置 4 的灯和它的两个邻居。

策略的效果可以通过域 GF(2) 上的矩阵乘法来计算。 GF(2) 只有 2 个元素，0和 1 , 除了规则 1 + 1 = 0 之外，还有普通的算术规则.那么上面策略的效果就是矩阵乘以一个矩阵，结果是选择灯i在 i-th列，换句话说，由“循环矩阵”组成，如下所示:

[ 1 1 0 0 1 ] [0]   [0]
[ 1 1 1 0 0 ] [1]   [0]
[ 0 1 1 1 0 ] [1] = [0]
[ 0 0 1 1 1 ] [0]   [0]
[ 1 0 0 1 1 ] [1]   [1]

策略结果 (0 1 1 0 1)^T是只切换最后一个位置的灯。因此，如果您开始时只点亮最后一个位置的灯并应用该策略，则所有灯都将关闭。

在这个简单的例子中，我们用列向量 b 表示初始配置。 .解决方案策略则是一个列向量 x满足矩阵方程 Ax = b .

现在的问题是，对于给定的 b , 1) 是否存在满足 Ax=b 的 x ? 2)是解决方案 x独特的？如果没有，哪个 x最少 1的？ 3)如何计算？

上述问题的答案将取决于手头特定问题的数字“长度”和“米”。在上面考虑的length = 5, m = 1 问题中，线性代数理论告诉我们对于任何 b 都有唯一的解。 .我们可以获得 b的解决方案形式 (0 0 ... 1 ... 0)^T ，换句话说，通过“旋转”解 (0 1 1 0 1)^T，一个 1，其余的为零.我们可以将任何解决方案唯一地表示为这些解决方案的线性组合，因此具有最小数量 1 的策略/解决方案与任何给定初始状态的唯一解决方案相同。

另一方面，长度 = 6 且 m = 1，所有三个策略 (100100)^T , (010010)^T , 和 (001001)^T映射到结果 (111111)^T ，因此在某些情况下没有唯一的解决方案；根据线性代数理论，在其他一些情况下没有解。

通常，我们可以使用高斯消元法判断解是否存在且唯一。在上面的 5x5 情况下，将第 0 行添加到第 1 行和第 4 行；

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 1 0 0 1 ] [1 0 0 0 0]
[ 1 1 1 0 0 ] [0 1 0 0 0]    [ 0 0 1 0 1 ] [1 1 0 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] -> [ 0 1 1 1 0 ] [0 0 1 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 1 0 0 1 1 ] [0 0 0 0 1]    [ 0 1 0 1 0 ] [1 0 0 0 1]

然后交换第 1 行和第 2 行；然后将第 1 行添加到第 0 行和第 4 行，

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 0 1 1 1 ] [1 0 1 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0]    [ 0 1 1 1 0 ] [0 0 1 0 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 0 1 0 1 0 ] [1 0 0 0 1]    [ 0 0 1 0 0 ] [1 0 1 0 1]

然后将第 2 行添加到第 0、1、3、4 行；然后将第 3 行添加到第 1、2 行；

[ 1 0 0 1 0 ] [0 1 1 0 0]    [ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 1 1 ] [1 1 1 0 0]    [ 0 1 0 0 1 ] [0 0 1 1 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 0 1 0 ] [1 1 0 1 0]    [ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]    [ 0 0 0 0 1 ] [0 1 1 0 1]

最后将第 4 行添加到第 1、2 行:

[ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 0 0 ] [0 1 0 1 1]
[ 0 0 1 0 0 ] [1 0 1 0 1]
[ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]

您可以在右侧矩阵的列中读出解的基础。例如，我们上面使用的解决方案在右矩阵的最后一列。

您应该在上面讨论的 length = 6, m = 1 情况下尝试高斯消元法，看看会发生什么。

在给定的情况下(长度 = 2200，m = 110)，我怀疑解总是存在并且是唯一的，因为在一次移动中切换的灯数是 221，这是 2200 的质数，但我建议你使用高斯消元法为任何起始位置找到明确的策略 b .如果没有独特的策略，您将如何最小化移动次数？