AI基础：传教士与野人

设定：

河的左岸有3个传教士和3个野人，船的载重量是2。当传教士人数小于野人人数时，会被野人吃掉，现在要将传教士和野人都送过河。

代码实现：

from collections import deque  initial_men = 3  # 初始传教士人数
initial_cannibals = 3  # 初始野人人数
boat_capacity = 2  # 船的承载量
moves = []
def init():max_move = boat_capacityfor men_move in range(max_move + 1):for cannibal_move in range(max_move - men_move + 1):if (men_move == 0 and cannibal_move == 0) or (men_move + cannibal_move > max_move):continuemoves.append((men_move, cannibal_move))# 定义初始状态和目标状态  
initial_state = (3, 3, 0, 0, 'right')  # (右岸传教士人数, 右岸野人人数, 左岸传教士人数, 左岸野人人数, 船的位置)  
final_state = (0, 0, 3, 3, 'left')  # 目标状态：所有人都到左岸，且船在左岸  # 定义所有可能的动作  
actions = [  [(1, 0), (0, 1), (1, 1), (2, 0), (0, 2)],  # 传教士或野人单独过河，或传教士和野人一起过河  [(-1, 0), (0, -1), (-1, -1), (-2, 0), (0, -2)]    # 传教士或野人单独返回，或传教士和一个野人一起返回  
]  # 定义状态是否有效的函数  
def is_valid_state(missionaries, cannibals, side):  """missionaries: 左岸传教士人数 cannibals: 左岸野人人数side: 船的位置"""if missionaries < 0 or cannibals < 0:  return False  if side == 'left' and (missionaries < 3 and cannibals < missionaries):  #船在左岸，判断右岸return False  if side == 'right' and (missionaries > 0 and cannibals > missionaries):  #船在右岸，判断左岸return False  return True  def is_valid(missionaries, cannibals):if missionaries < 0 or cannibals < 0:return Falseif missionaries > 0 and cannibals > missionaries:  return Falsereturn True# 广度优先搜索  
def bfs():  queue = deque([initial_state])  visited = set([initial_state])  while queue:  current_state = queue.popleft()  current_path.append(current_state)if current_state == final_state:  return current_path  missionaries_right, cannibals_right, missionaries_left, cannibals_left, boat_side = current_state  new_boat_side = 'left' if boat_side == 'right' else 'right'moves = actions[0] if boat_side == 'right' else actions[1]for move in moves:    new_missionaries_right = missionaries_right - move[0]  new_cannibals_right = cannibals_right - move[1]  new_missionaries_left = missionaries_left + move[0]  new_cannibals_left = cannibals_left + move[1]new_state = (new_missionaries_right, new_cannibals_right, new_missionaries_left, new_cannibals_left, new_boat_side)  # if new_state not in visited and is_valid_state(new_missionaries_left, new_cannibals_left, 'left') and is_valid_state(new_missionaries_right, new_cannibals_right, 'right'):if new_state not in visited and is_valid(new_missionaries_left, new_cannibals_left) and is_valid(new_missionaries_right, new_cannibals_right):visited.add(new_state)    queue.append(new_state)  # 存储路径  
current_path = []  # 执行BFS  
result = bfs()  # 打印结果路径  
if result:  print("解决方案路径:")  for step in result:  print(step)  
else:  print("没有找到解决方案")