用python语言实现传教士与野人过河问题

传教士与野人过河问题是经典的算法问题，它涉及到状态转移和决策树的概念。在这个问题中，我们有两个角色：传教士和野人，以及一条船，船上只能容纳一个人。传教士不能单独留下与野人在一起，因为传教士不会保护野人。以下是使用Python实现的基本步骤：

class Person:
    def __init__(self, status):
        self.status = status

class Boat:
    def __init__(self, passengers=[]):
        self.passengers = passengers

def can_cross(boat, person1, person2):
    # 如果只有一个人或者两个人都是同一种身份，可以过河
    if len(boat.passengers) == 0 or (person1.status == person2.status and not boat.passengers):
        boat.passengers.append(person1)
        return True
    elif (len(boat.passengers) == 1 and boat.passengers[0].status != person1.status) or \
         (len(boat.passengers) == 2 and boat.passengers[-1].status == person1.status):
        boat.passengers.pop()
        boat.passengers.append(person1)
        return True
    else:
        return False

# 初始化情况：传教士、野人都在对岸
island1 = [Person('missionary'), Person('cannibal')]
island2 = []

# 初始状态
current_island = island1
target_island = island2
boat = Boat()

while current_island:
    for person in current_island:
        if can_cross(boat, person, None):  # 检查是否能将当前岛屿的人带到对岸
            target_island.append(person)
            current_island.remove(person)

print("传教士和野人都成功到达了对岸的岛上。")