找到打开灯泡所需开关的算法

证明最坏情况至少需要N次尝试

如果有N个开关,则可以有2^N个可能的“必需”集合,因为每个开关都可以在“必需”的集合内或外。

为了区分2^N个可能的集合,您可以将其视为我们需要通过摆弄开关来获得至少N位的信息。如果没有,则有可能有超过1个集合都符合我们目前所知的信息。

假设有8种可能的配置(N=3),我们可以选择配置的子集,并查询“所需”配置是否在所选子集中。实现这一点的最佳方法类似于二进制搜索,只需N次尝试即可达到对数(2^N)的复杂性。如果我们使用少于3次的尝试,我们将至少剩下2种配置,我们无法决定哪种配置是正确的,因为每次尝试都将消除一半的可能配置。

回到最初的问题,让我们假设到目前为止使用K次尝试,其中K<N、 由于每次尝试都会提供1位信息(是,它亮起/否,它不亮起),每次尝试都可以消除一半可能的配置,因此在K次尝试后,我们将剩下2^(N-K)个可能的配置。

为了只得到“所需”集合的1个不同的可能配置,我们需要K=N,这将给我们2^(N-N)=2^0=1个可能的配置。

这为我们提供了这个问题的下限,因为每次尝试都会提供1位信息(是,它亮起/否,它不亮起)。因此,我们至少需要N次尝试。

使用不超过N次尝试的可能解决方案

由于“非必需开关不重要”,如果我正确解释,这意味着如果“必需”集合之外的开关打开,除了“必需”集中的开关之外,灯仍将打开。由于我们有N次尝试使用(并且仍然使其最佳),我们可以使用以下解决方案: 对于每个开关(按顺序),打开除此开关之外的所有其他开关。 检查灯是否关闭。如果灯已关闭,则唯一保持关闭的开关将处于“所需”设置。

该解决方案将使用N次尝试(甚至在更坏的情况下),并且是最佳解决方案之一(如前所述)。

假设有N个交换机,在最坏的情况下,找出所需交换机集(使用优化策略)所需的最小尝试次数是多少?

暴力方式,检查所有可能的开关组合,直到灯亮起,这将是 O(2^N) (尽管我们可能会很幸运,在第一次尝试后就打开了灯)。

通过更优化的搜索,可以在最坏的情况下找到所需的开关集 O(N) 尝试。这里有一种方法 O(N) :

• 全部翻转 N 打开:我们知道灯会亮。

• 关闭开关1。如果灯熄灭,则需要开关1,因此将其重新打开。如果灯一直亮着,则关闭开关1,因为 这不是必需的。(使用了一次尝试)。

• 关闭开关2:如果灯熄灭,则需要开关2,因此将其重新打开。如果灯一直亮着,则关闭开关2,因为不需要开关2。(使用了两次尝试)。

• 对其余每个开关重复此检查。( N 尝试次数)。

• 之后 N 尝试,我们将剩下一组所需的开关处于打开位置。

如其他回答/评论中所述,也可能在最佳情况下找到所需的开关集 O(log(N)) 最坏的情况 O(N) :

• 全部翻转 N 打开:我们知道灯会亮。

• 翻转第一个 N/2 开关关闭。在灯保持打开的情况下,这些开关都不需要,因此我们可以保持开关关闭。移动到 不适用于2 开关仍然打开并重复此步骤。。。

• 然而,如果灯熄灭,至少其中一个 不适用于2 需要开关:重新打开开关,将集合一分为二,然后重复上一步。。。

这种算法是最坏的情况 O(N) 因为我们可能必须单独检查每个交换机(例如,如果有10个交换机并且所需的配置是0101010101)。

假设我们需要尝试N个开关的所有可能组合。我们可以用二进制数表示,比如0101,我们要检查每个二进制数。一种简单的方法是依次检查每个数字:0000(全部关闭)、0001(开关4打开)、0010(开关3打开)、0011(开关3和4打开)。注意如何从0001到0010实际上需要两个步骤,即关闭4和打开3。

一个更好的算法叫做 Gray code 在每个数字中运行,因此每次只切换一个数字。顺序应该是 0000, 0001, 0011, 0010, 0110, 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.

编辑:我认为这解决了一个稍微不同的问题,即要打开一些开关,就需要关闭一些开关才能打开。