python深度优先搜索传教士和野人_传教士和野人问题解题思路

传教士和野人问题是一个经典的搜索问题，其目标是将三个传教士和三个野人从一岸经过一条河流运输到另一岸，但是在运输过程中必须遵守以下规则：

1. 每次只能运输一到两个人；
2. 在任何一边岸上，传教士的数量不能少于野人的数量，否则传教士会被野人吃掉。

下面是针对该问题的深度优先搜索解题思路：

1. 定义状态：我们可以用一个三元组来表示当前状态，其中第一项表示左岸上的传教士数量，第二项表示左岸上的野人数量，第三项表示当前船的位置（0表示左岸，1表示右岸）。
2. 定义目标状态：我们的目标状态是(0,0,1)，即所有人都已经过河到右岸。
3. 定义可行状态：对于任何一个状态，我们需要判断这个状态是否可行，即传教士数量是否大于等于野人数量，且传教士和野人的数量均不小于0。
4. 定义扩展状态：对于任何一个状态，我们可以把船上的1-2个人移动到对岸，这样会生成一个新的状态。
5. 深度优先搜索：我们可以从初始状态开始，不断扩展状态，直到找到目标状态为止。在扩展状态的过程中，需要保证新生成的状态是可行的，并且没有出现在先前的状态中（避免重复搜索）。

在实现深度优先搜索的过程中，我们可以使用递归函数来实现。具体实现细节可以参考以下示例代码：

def dfs(state, visited):
    # 判断是否已经到达目标状态
    if state == (0, 0, 1):
        return True
    # 判断当前状态是否已经搜索过
    if state in visited:
        return False
    # 将当前状态加入已访问列表
    visited.append(state)
    # 扩展状态
    for i in range(1, 3):
        for j in range(i + 1):
            # 移动i个传教士和j个野人
            if state[2] == 0:
                # 船在左岸
                new_state = (state[0] - i, state[1] - j, 1)
            else:
                # 船在右岸
                new_state = (state[0] + i, state[1] + j, 0)
            # 判断新状态是否可行
            if new_state[0] >= new_state[1] and new_state[0] >= 0 and new_state[1] >= 0 and new_state not in visited:
                # 递归搜索新状态
                if dfs(new_state, visited):
                    return True
    # 没有找到目标状态
    return False

# 搜索入口函数
def search():
    # 初始状态为(3, 3, 0)，即所有人都在左岸
    init_state = (3, 3, 0)
    visited = []
    if dfs(init_state, visited):
        print("找到解决方案！")
    else:
        print("没有找到解决方案！")

search()

当搜索到目标状态时，就可以输出所找到的解决方案。在以上代码中，我们使用递归函数 `dfs` 来实现深度优先搜索，使用列表 `visited` 来记录已经访问过的状态，以避免重复搜索。在扩展状态时，我们需要注意船只能运输1-2个人，因此需要分别枚举传教士和野人的数量。