设定：

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

代码实现：

from collections import deque  

initial_men = 3  # 初始传教士人数
initial_cannibals = 3  # 初始野人人数
boat_capacity = 2  # 船的承载量
moves = []
def init():
    max_move = boat_capacity
    for 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):
                    continue
                moves.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 False
    if missionaries > 0 and cannibals > missionaries:  
        return False
    return 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("没有找到解决方案")