题目B
电影《虎胆龙威 3》中，塞谬尔和布鲁斯扮演的主角要拆除西蒙所放的炸弹。西蒙喷泉上面有两个壶，容量分别是5加仑和3加仑，向其中一个壶中加入刚好 4 加仑的水，计时器会停止，否则5分钟后会爆炸。 问题:能够安全拆弹吗?要怎么做?
解：每个状态可以表示为一个元组 (x, y)，其中 x 是 5 加仑壶中的水量，y 是 3 加仑壶中的水量。初始状态为 (0, 0)，即两个壶都是空的。目标状态是 x = 4，即 5 加仑壶中有 4 加仑水。
可以执行以下几种操作：
填满5加仑壶：(x, y) -> (5, y)
填满 3 加仑壶：(x, y) -> (x, 3)
倒空 5 加仑壶：(x, y) -> (0, y)
倒空 3 加仑壶：(x, y) -> (x, 0)
从 5 加仑壶倒水到 3 加仑壶：倒水，直到一个壶空或者另一个壶满。
从 3 加仑壶倒水到 5 加仑壶：同样的，直到一个壶空或者另一个壶满。
BFS搜索方案
from collections import deque
# 定义 BFS 函数，返回完整的操作过程
def water_jug_bfs():# 初始状态，两个壶都是空的 (0, 0)initial_state = (0, 0)# 队列用于 BFS，每个元素不仅记录状态，还记录从初始状态到达该状态的路径queue = deque([(initial_state, [])]) # 队列中存放 (状态, 操作路径)# 用于记录已经访问过的状态，防止重复搜索visited = set([initial_state])# 定义壶的容量jug1_capacity = 5jug2_capacity = 3goal = 4 # 我们的目标是 5 加仑壶中正好有 4 加仑水# BFS 搜索过程while queue:current_state, path = queue.popleft()x, y = current_state# 如果达到了目标状态 (5加仑壶中有4加仑水)，则返回成功和完整的操作路径if x == goal:return True, path + [(current_state, "最终状态")]# 产生所有可能的下一步状态，并附加上相应的操作说明next_states = [((jug1_capacity, y), "填满 5 加仑壶"), # 填满5加仑壶((x, jug2_capacity), "填满 3 加仑壶"), # 填满3加仑壶((0, y), "倒空 5 加仑壶"), # 倒空5加仑壶((x, 0), "倒空 3 加仑壶"), # 倒空3加仑壶# 从 5 加仑壶倒水到 3 加仑壶，倒的水量是 min(x, jug2_capacity - y)((x - min(x, jug2_capacity - y), y + min(x, jug2_capacity - y)), f"从 5 加仑壶倒 {min(x, jug2_capacity - y)} 加仑水到 3 加仑壶"), # 从 3 加仑壶倒水到 5 加仑壶，倒的水量是 min(y, jug1_capacity - x)((x + min(y, jug1_capacity - x), y - min(y, jug1_capacity - x)), f"从 3 加仑壶倒 {min(y, jug1_capacity - x)} 加仑水到 5 加仑壶")]# 对每个可能的下一状态进行处理for next_state, action in next_states:if next_state not in visited: # 如果没有访问过这个状态visited.add(next_state) # 标记为访问queue.append((next_state, path + [(current_state, action)])) # 加入到搜索队列中，并记录路径return False, [] # 如果找不到解，则返回 False 和空路径
# 运行 BFS
result, path = water_jug_bfs()
if result:print("可以安全拆除炸弹。操作步骤如下：")for i in range(len(path) - 1):state, action = path[i]print(f"当前状态 (5加仑壶: {state[0]} 加仑, 3加仑壶: {state[1]} 加仑) -> {action}")
else:print("无法安全拆除炸弹")
结果： 可以安全拆除炸弹。操作步骤如下： 当前状态 (5加仑壶: 0 加仑, 3加仑壶: 0 加仑) -> 填满 5 加仑壶 当前状态 (5加仑壶: 5 加仑, 3加仑壶: 0 加仑) -> 从 5 加仑壶倒 3 加仑水到 3 加仑壶 当前状态 (5加仑壶: 2 加仑, 3加仑壶: 3 加仑) -> 倒空 3 加仑壶 当前状态 (5加仑壶: 2 加仑, 3加仑壶: 0 加仑) -> 从 5 加仑壶倒 2 加仑水到 3 加仑壶 当前状态 (5加仑壶: 0 加仑, 3加仑壶: 2 加仑) -> 填满 5 加仑壶 当前状态 (5加仑壶: 5 加仑, 3加仑壶: 2 加仑) -> 从 5 加仑壶倒 1 加仑水到 3 加仑壶
故可以安全拆除炸弹，首先填满5加仑壶，然后将其中的3加仑倒入3加仑壶。接着倒空3加仑壶，并将5加仑壶剩下的2加仑倒入3加仑壶。随后再次填满5加仑壶，并将其中的1加仑倒入3加仑壶。这时，5加仑壶中剩下的正好是4加仑水，从而成功拆除炸弹。
