熄灯算法：求解开启全部开关的最少切换次数及步骤输出的可行方案问询

这个开关切换问题的规则很有意思，本质上是一个状态空间最短路径问题，我们可以用两种方式解决：一种是通过BFS（广度优先搜索）生成完整的操作过程并保证最少步数，另一种是通过数学规律直接计算最少切换次数。

一、核心思路解析 #

首先再明确规则：

• 最右侧开关：随时可以切换状态
• 非最右侧开关i：仅当右侧紧邻开关i+1处于开启状态，且**i+1右侧的所有开关都关闭**时，才能切换状态

要达到"全开"的目标，我们需要从全关状态出发，每次只做符合规则的切换，找到最短路径——这正好是BFS的擅长场景，因为BFS会优先探索所有距离起点最近的状态，第一个到达目标状态的路径就是最短路径。

二、代码实现：BFS生成完整过程 #

下面是Python代码，输入开关数量n，返回最少切换次数和每一步的开关状态：

from collections import deque

def min_switch_operations(n):
    start_state = tuple([0] * n)
    target_state = tuple([1] * n)
    
    # 队列元素：(当前状态, 到该状态的路径列表)
    queue = deque()
    queue.append((start_state, [list(start_state)]))
    visited = set()
    visited.add(start_state)
    
    while queue:
        current, path = queue.popleft()
        
        # 到达目标状态，返回结果
        if current == target_state:
            return len(path) - 1, path
        
        # 遍历所有开关，尝试切换
        for switch_idx in range(n):
            if switch_idx == n - 1:
                # 最右侧开关，直接切换
                new_state = list(current)
                new_state[switch_idx] = 1 - new_state[switch_idx]
                new_state_tuple = tuple(new_state)
                if new_state_tuple not in visited:
                    visited.add(new_state_tuple)
                    queue.append((new_state_tuple, path + [new_state]))
            else:
                # 非最右侧开关，检查切换条件
                # 条件1：右侧紧邻开关必须开启
                if current[switch_idx + 1] != 1:
                    continue
                # 条件2：右侧紧邻开关的所有右侧开关必须全关
                all_right_off = all(current[j] == 0 for j in range(switch_idx + 2, n))
                if all_right_off:
                    new_state = list(current)
                    new_state[switch_idx] = 1 - new_state[switch_idx]
                    new_state_tuple = tuple(new_state)
                    if new_state_tuple not in visited:
                        visited.add(new_state_tuple)
                        queue.append((new_state_tuple, path + [new_state]))
    
    # 理论上不会走到这里，因为总能到达目标
    return -1, []

测试示例 #

当n=3时，运行代码：

count, steps = min_switch_operations(3)
print("最少切换次数：", count)
print("操作过程：")
for state in steps:
    print(" --> ".join(map(str, state)))

输出结果：

最少切换次数： 5
操作过程：
0 --> 0 --> 0
0 --> 0 --> 1
0 --> 1 --> 1
0 --> 1 --> 0
1 --> 1 --> 0
1 --> 1 --> 1

完全匹配你给出的示例！

三、最少切换次数的数学规律 #

如果只需要计算最少次数，不需要过程，可以用递归公式直接计算：

• 当n=1时，最少次数为1
• 当n为偶数时，f(n) = 2 * f(n-1)
• 当n为奇数时，f(n) = 2 * f(n-1) + 1

验证一下：

• n=1 → 1
• n=2 → 2*1=2
• n=3 → 2*2+1=5
• n=4 → 2*5=10
• n=5 → 2*10+1=21

这个规律是从BFS的结果中归纳出来的，本质是因为偶数个开关时，完成目标的过程是重复两次n-1的操作（一次配合最右开关开启，一次配合关闭）；奇数个开关时，会多一次最右开关的切换操作。

内容的提问来源于stack exchange，提问作者KiLLCode