5.7 修道士和野人问题。设有3个修道士和3个野人来到河边，打算用一条船从河的左岸渡到河的右岸去。但该船每次只能装载两个人,在任何岸边野人的数目都不得超过修道士的人数，否则修道士就会敲野人吃掉。假设野人服从任何一种过河安排，请使用状杰空间搜紫法，规划一使全部6人安全过河的方案。（提示：应用状态空间表示和搜素方法时，可用（Nm，N，）来表示状态描述，其中 No 和N。分别为传教士和野人的人数。初始状态为(3,3），而可能的中间状态为(0,1),(0,2),(0,3),（1,1),(2,1）,(2,2)，(3,0),(3,1)，(3,2）等。）

这是一个经典的搜索问题，可以使用状态空间搜索法来解决。首先，我们需要定义状态空间和搜索算法。

状态空间定义：

- 初始状态：(3, 3, 1)，表示左岸有3个修道士、3个野人和一艘船。
- 状态空间：(m, c, b)，其中m表示左岸修道士的数量，c表示左岸野人的数量，b表示船是否在左岸（1表示在左岸，0表示在右岸）。
- 目标状态：(0, 0, 0)，表示全部人和船都在右岸。

搜索算法：

使用广度优先搜索算法来遍历所有可能的状态，找到可以使得所有人安全过河的解。在每个节点处，需要对当前状态进行判断，如果不满足安全过河的条件，则需要剪枝，即不再继续搜索该节点的子节点。

具体实现时，可以使用队列来存储待扩展的节点，每次取出队首节点进行扩展，并将扩展得到的子节点加入队列中。当找到一种解法时，可以通过回溯法来找到所有的解，并输出结果。

代码实现如下：

def is_valid_state(state):
    m, c, b = state
    if m < 0 or c < 0 or m > 3 or c > 3 or (c > m and m > 0) or (c < m and m < 3):
        return False
    return True

def get_next_states(state):
    m, c, b = state
    next_states = []
    if b == 1:
        for i in range(3):
            for j in range(3):
                if i + j >= 1 and i + j <= 2:
                    next_m = m - i
                    next_c = c - j
                    next_b = 0
                    next_state = (next_m, next_c, next_b)
                    if is_valid_state(next_state):
                        next_states.append(next_state)
    else:
        for i in range(3):
            for j in range(3):
                if i + j >= 1 and i + j <= 2:
                    next_m = m + i
                    next_c = c + j
                    next_b = 1
                    next_state = (next_m, next_c, next_b)
                    if is_valid_state(next_state):
                        next_states.append(next_state)
    return next_states

def bfs():
    start_state = (3, 3, 1)
    end_state = (0, 0, 0)
    queue = [[start_state]]
    visited = set()
    while queue:
        path = queue.pop(0)
        state = path[-1]
        if state == end_state:
            return path
        if state in visited:
            continue
        visited.add(state)
        next_states = get_next_states(state)
        for next_state in next_states:
            if next_state not in visited:
                next_path = path + [next_state]
                queue.append(next_path)
    return []

solution = bfs()
for state in solution:
    print(state)

输出结果如下：

(3, 3, 1)
(3, 1, 0)
(3, 2, 1)
(3, 0, 0)
(3, 1, 1)
(1, 1, 0)
(2, 2, 1)
(0, 2, 0)
(0, 3, 1)
(0, 1, 0)
(0, 2, 1)
(0, 0, 0)

其中，每行输出一个状态，表示船和人在左岸或右岸的情况。可以看到，最后的状态为(0, 0, 0)，表示所有人和船都已经安全到达右岸。