### Python 实现野人过河问题的解决方案 以下是基于深度优先搜索 (DFS) 的 Python 实现，用于解决“传教士与野人过河”问题。此实现涵盖了状态空间定义、初始状态设定、行动规则以及目标检测。 #### 状态表示 使用三元组 `(M, C, B)` 表示当前的状态： - `M`：起始岸边的传教士数量。 - `C`：起始岸边的野人数量。 - `B`：小船的位置（1 表示在起点岸，0 表示在终点岸）。 #### 动作集合 每次移动可以选择不同的人员组合跨河，动作由以下参数决定： - 小船容量 `capacity`。 - 移动方向（从小船当前位置到另一侧）。 #### 合法性检查 每一步都需要验证新状态是否合法： 1. 起始岸和终点岸上的传教士数量均不能小于对应的野人数量（除非传教士数量为零）。 2. 新状态未被访问过。 --- ```python from collections import deque def is_valid_state(state): """判断给定状态是否合法""" M1, C1, _ = state # 当前岸的情况 M2, C2 = 3 - M1, 3 - C1 # 对岸的情况 if M1 < 0 or C1 < 0 or M2 < 0 or C2 < 0: return False # 数量不能为负数 if M1 > 0 and M1 < C1: # 当前岸不安全 return False if M2 > 0 and M2 < C2: # 另一岸不安全 return False return True def get_next_states(current_state, capacity): """获取从当前状态出发的所有可能下一步状态""" M, C, B = current_state next_states = [] # 定义所有可能的动作（船上的人数） actions = [(m, c) for m in range(capacity + 1) for c in range(capacity + 1) if 1 <= m + c <= capacity] for action in actions: dm, dc = action if B == 1: # 如果船在左边 new_state = (M - dm, C - dc, 0) else: # 如果船在右边 new_state = (M + dm, C + dc, 1) if is_valid_state(new_state): # 检查合法性 next_states.append((new_state, action)) return next_states def dfs(start_state, goal_state, capacity): """深度优先搜索解决问题""" stack = [(start_state, [])] # 初始栈 visited = set() # 记录已访问过的状态 while stack: current_state, path = stack.pop() if current_state == goal_state: # 找到目标状态 return path if current_state not in visited: visited.add(current_state) for next_state, action in get_next_states(current_state, capacity): if next_state not in visited: new_path = path.copy() new_path.append((action, next_state)) # 添加新的动作和状态 stack.append((next_state, new_path)) return None # 主函数调用 if __name__ == "__main__": start_state = (3, 3, 1) # 初始状态：3名传教士，3名野人在左岸，船也在左岸 goal_state = (0, 0, 0) # 目标状态：所有人都到了右岸 boat_capacity = 2 # 小船最大承载能力 solution = dfs(start_state, goal_state, boat_capacity) if solution: print("Optimal Procedure:") prev_M, prev_C, prev_B = start_state for i, (action, state) in enumerate(solution): curr_M, curr_C, curr_B = state move_str = f"{prev_M}{prev_C}{prev_B} -> {curr_M}{curr_C}{curr_B}" print(move_str) prev_M, prev_C, prev_B = curr_M, curr_C, curr_B print("Successed") else: print("Failed") ``` --- ### 关键点说明 1. **状态合法性检验**：通过 `is_valid_state()` 函数确保任何时刻两岸的安全性[^1]^。 2. **动作生成器**：利用嵌套循环枚举所有可能的船上人员配置，并结合当前船只位置计算下一状态[^2]^。 3. **深度优先搜索**：采用显式堆栈结构存储待探索节点及其路径记录，避免重复访问同一状态[^4]^。 ---