野人与传教士

用遍历方法寻找所有可能路径，因此用DFS比较合适，因此BFS虽然能找到目标状态，但是要找到目标状态的前一路径比较困难）

设定状态表示，虽然可以直接用（M，C，b）三元组分别表示左岸传教士，野人数量以及船是否在左岸。实现时为了方便还是定义一个class类state分别表示

1
2
3
4
5
6
7
class State:
    def __init__(self,lm,rm,lc,rc,ship):
        self.lm = lm
        self.rm = rm
        self.lc = lc
        self.rc = rc
        self.ship = ship

因此初始状态init为

1
init = State(M,0,C,0,1)

定义一个函数判断是否为目标状态

1
2
3
4
5
def is_goal(state):
    
    if state.lm == 0 and state.lc == 0 and state.rm == M and state.rc == C:
        return 1
    return 0

能实施的操作用operators表示

1
2
3
4
5
6
7
8
9
# 合法操作
operators = []

# 根据k（船最大可容纳人数）生成合法操作，i为野人与传教士人数和，c为传教士数量
def get_operator(k):
    for i in range(1,k + 1):
        for c in range(i + 1):
            if (c >= i - c) or (c == 0):
                operators.append([c,i-c])

定义完毕后，DFS进行遍历：

  1. 终止条件：达到目标状态，则依次输出路径
  2. 遍历operators中的操作，并模拟执行对应的操作，并判断模拟执行后是否有危险以及该状态是否已经存在，若都没有，则将该状态加入路径中，然后递归进行dfs遍历。退出对应dfs后应该恢复状态，即从状态列表中删除对应状态

遍历过程代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
def is_dangerous(state):
    if state.lm >= 0 and state.lc >= 0 and state.rm >= 0 and state.rc >= 0:
        if (state.lm >= state.lc and state.rm >= state.rc) or (state.lm == 0 and state.rm >= state.rc) or (state.rm == 0 and state.lm >= state.lc):
            return 0
    else:
        return 1
    

def is_existed(state):
    for i in statelist:
        if (i.lm == state.lm and i.lc == state.lc and i.rm == state.rm and i.rc == state.rc and i.ship == state.ship):
            return 1
    return 0
def dfs(start):
    global index,sum
    if is_goal(start):

        sum += 1
        print("第"+str(sum)+"种方案")
        
        for i in statelist:
            print(i.lm,i.lc,i.rm,i.rc,i.ship)

    for i in  operators:
        x = i[0]
        y = i[1]

        if start.ship == 1:
            tmp = State(start.lm - x,start.rm + x, start.lc - y , start.rc + y, -1)
            if is_dangerous(tmp) == 0 and is_existed(tmp) == 0:
                statelist.append(tmp)
                dfs(tmp)
                statelist.pop()
                
        else:
            tmp = State(start.lm + x, start.rm - x,start.lc + y , start.rc - y, 1)
            if is_dangerous(tmp) == 0 and is_existed(tmp) == 0:
                statelist.append(tmp)
                dfs(tmp)
                statelist.pop()

完整代码见py文件，定义M=C=3，k=2的情况下，成功输出四种解决方案