algorithm - 在非指数时间内解决灯泡切换难题？

Question

灯泡开关问题:

You are given few switches and few bulbs, not necessarily equal, and each button may connect to multiple bulbs, and when a switch is toggled on, it switches on the already off and off the already on bulbs. We need to find if all bulbs can be lighted up by switching some of these switches?

我们可以在 O(2^n.n.m.x)(n，开关数量；m，灯泡总数；x，任何开关打开的最大灯泡数量)中暴力解决这个问题。我们尝试所有开关组合 O(2^n) 并在从选定开关 O(n.x) 打开所有灯泡后检查所有灯泡是否打开 O(m)

这能否在非求幂时间内完成，也许是一种启发式方法。 这在某种程度上与集合打包和集合覆盖问题有关，并且两者似乎都只有近似算法(NP-hard，IIRC)

Answer 1

答案是肯定的，你可以在 O(min((m^2) n, (n^2) m)) 时间内解决这种难题。

您的问题可以视为 matrix整数 mod 2，其中乘法变为 bool “与”，加法变为 bool “异或”。

为了使事情更具体:您可以将“原始”灯泡状态(所有开关都关闭)表示为一个 bool 列向量，将每个开关的状态表示为另一个 bool 向量，并将每个开关切换的一组灯泡表示为 bool 矩阵的相应列:

output     original         matrix      switches
  [v]        [u]        [m m m m m m]     [x]
  [v]   =    [u]   +    [m m m m m m]  *  [x]
  [v]        [u]        [m m m m m m]     [x]
                                          [x]
                                          [x]

这是一组整数模 2 下的线性方程组，您可以使用标准 linear equation solvers 的适当修改版本有效地解决此类问题。 .

请注意，这样做的原因是翻转开关总是会切换同一组灯泡。如果不是这种情况，则方程不是是线性的，您无法用这种方法求解。一般来说，如果你在这类问题中将“或”与“和”混在一起，你可能会得到 "SAT" problem 的一些变体。 , 这是 NP 完全的。