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

Question

假设您在一个有 N 个开关的房间里，隔壁房间里有一个灯泡。只有当一些指定的开关全部打开时，灯泡才会发光。

设置

• switches = 所有开关的集合。 |开关| =N。
• required = 需要打开才能使灯泡发光的开关。

不需要的开关无关紧要。

只有进入下一个房间才能检查灯泡是否发光。你可以打开或关闭一些开关，去下一个房间检查灯泡，然后重复这个过程。让我们称之为一次尝试。

假设有 N 个开关，在最坏的情况下，找出一组 required 开关(使用优化策略)所需的最少尝试次数是多少？

---

例如，

• 开关 = { 1, 2, 3 }
• required = { 1, 2 }

让我们尝试一个简单的方法:

• 打开{ 1, 2 } ，灯亮了。 (确保不需要开关 3)
• 打开{ 1, 3 } ，灯不亮。 (确保需要开关 2)
• 打开{ 2, 3 } ，灯不亮。 (确保需要开关 1)

因此，通过 3 次尝试，我们可以确保 required = { 1, 2 }。

这个问题的优化算法是什么？

让 worst(N) 是考虑到最坏情况下 N 开关的最小尝试。你能找出worst(N)

更新:如果您认为 worst(N) = N，您能提供正式证明吗？

Answer 1

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

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

为了区分 2^N 个可能的集合，您可以认为我们需要通过摆弄开关来获得至少 N 位的信息。如果不是，则有可能有不止 1 组都可以符合我们目前已知的信息。

假设有 8 种可能的配置 (N = 3)，我们可以选择配置的子集并查询“所需”配置是否在所选子集中。执行此操作的最佳方法类似于二进制搜索，实现 log(2^N) 的复杂性，这只是 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 次尝试(即使在最坏的情况下)并且它是最佳解决方案之一(如前所述)。