假设你在一个带N开关的房间里,隔壁房间里有一个灯泡.只有当某些指定的开关全部打开时,灯泡才会发光.
组
switches=所有开关的集合.|switches| = N.required =需要打开的开关才能使灯泡发光. 不需要的开关无关紧要.
只有进入下一个房间,才能检查灯泡是否发光.您可以打开或关闭某些开关,转到下一个房间检查灯泡,然后重复此过程.让我们称之为ATTEMPT.
假设N在WORST CASE中有一些开关,找出这组required开关所需的最小尝试次数(使用优化策略)是多少？
例如,
switches = { 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,您能提供正式证明吗？
Ran*_*Lam 11
证明最坏情况需要至少N次尝试
如果有N个开关,则可以有2 ^ N个可能的"必需"组,因为每个开关可以在"必需"组中或者在"必需"组中.
为了区分2 ^ N个可能的集合,您可以考虑它,因为我们需要通过摆弄交换机来获得至少N位的信息.如果没有,那么有可能存在多于1套,它们都能适合我们目前所知的信息.
让我们假设有8种可能的配置(N = 3),我们可以选择配置子集并查询"required"配置是否在所选子集中.执行此操作的最佳方法类似于二进制搜索,实现log(2 ^ N)的复杂性,这只是N次尝试.如果我们使用少于3次尝试,我们将留下至少2个配置,我们无法确定哪个是正确的,因为每次尝试将消除一半可能的配置.
回到最初的问题,让我们假设我们使用K尝试到目前为止K <N.因为每次尝试都会提供1位信息(是的,它点亮/不亮,它不亮),每次尝试都可以消除一半可能的配置数量,我们将在K次尝试后留下2 ^(NK)个可能的配置.
为了得到'所需'集合的仅1个不同的可能配置,我们将需要K = N,这将给出2 ^(NN)= 2 ^ 0 = 1个可能的配置.
这给了我们这个问题的下限,因为每次尝试都会提供1位信息(是的,它亮起/不亮,它没有点亮).因此,我们至少需要N次尝试.
使用不超过N次尝试的可能解决方案
由于"非必需开关无关紧要",如果我正确解释它,则意味着如果"必需"组外的开关打开,除了"必需"组中的开关外,灯仍将亮起.由于我们有N次尝试使用(并且仍然是最佳),我们可以使用以下解决方案:对于每个开关(按顺序),打开除此开关之外的所有其他开关.检查灯是否已关闭.如果关闭,唯一保持关闭的开关将处于"必需"设置.
这个解决方案将使用N次尝试(即使在更糟糕的情况下),它是最佳解决方案之一(如前所述).