一 题目要求：
设有m个传教士和n个野人来到河边，打算乘一只船从左岸渡到右岸去，该船每次最多载3人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？试采用宽带优先和深度优先方法分析搜索过程。（说明：传教士和野人都会划船，测试：m=n=3）
二 构造状态空间：
这个题目的状态空间秒数为一组整数对（a，b，flag）。
a是左边岸上剩下的传教士数
b是左边岸上剩下的野人数目
flag取值为1时，船在左岸；flag取值为0是，船在右岸。
所以，初始状态为（m，n，1），目的状态为（0，0，0）。
三 对题目的理解：
可以想象到，这个题目应该采用树形结构来解，所以如何建立每个节点的数据结构就是难点。这里用Python写的算法，结点的数据结构如下：
class Point:
def __init__(self, a, b, flag):
self.a = a # 左岸传教士数量
self.b = b # 左岸野人数量
self.flag = flag # flag = 1: 船在左岸；flag = 0: 船在右岸
self.father = None
self.node = [a, b, flag]
比较重要的是Point结点的father属性，指明了子节点与父节点的关系，保证了树形结构的准确性。
四 代码解释：
- 首先定义了传教士数目、野人数目、open表、closed表，声明了Point类，定义了初始节点init（3，3，3）和目的节点（0，0，0）。
- 在开始进行BFS算法或者DFS算法之前，先定义几个函数：
1） safe：判断该节点内在左岸、右岸、船舶上的传教士数目是否大于野人数目或者有一方为0；
2） equal：判断两个节点是否相同。这里防止组合“爆炸”（老师上课说的）或者说是死循环。这里是为了检测OPEN表和CLOSED表写的函数；
3） back：判断该节点是否是父节点，防止节点重复；
4） in_list：判断这个节点是否在某个表中。用来判断新生成的节点是否在OPEN表或者CLOSED表中。 - 开始编写BFS算法和DFS算法：
1） 首先，先把初始节点init放入到OPEN表中，然后遍历OPEN表；
2） 如果OPEN中取出的节点是目的节点goal，那么结束遍历；否则把这个节点从OPEN表取出，放入CLOUSED表；
3） 然后根据此节点，来得到它的子节点，它的子节点要满足几个规则：符合题目规定的安全问题；不是父节点；不在OPEN表中；不在CLOUSED表中；
4） 如果3的条件满足，那么把这个新节点放入OPEN表。深度优先和广度优先的区别在于，深度优先把新节点放在OPEN表的OPEN[0]位置，而广度优先把新节点放在OPEN表的末尾（这也是老师上课强调的）。 - 最后打印一下路径，就可显示出解。
五 算法输出分析：
1、 BFS宽度优先算法 结果分析
如图1，是BFS算法打印出OPEN表的部分截图（太多了，就不全粘贴了），然后根据OPEN表可以写出宽度优先的遍历路径如图2。
图1-BFS算法结果
图2-BFS算法结果分析
2、 DFS宽度优先算法 结果分析
如图3，是DFS算法打印出OPEN表的部分截图（太多了，就不全粘贴了），然后根据OPEN表可以写出深度优先的遍历路径如图4。
图3-DFS算法结果
图4-DFS算法结果分析
六 代码：
A = 3 # 传教士数量
B = 3 # 野人数量
K = 3 # 最大乘坐人数量
OPEN = [] # open表
CLOSED = [] # closed表
class Point:
def __init__(self, a, b, flag):
self.a = a # 左岸传教士数量
self.b = b # 左岸野人数量
self.flag = flag # flag = 1: 船在左岸；flag = 0: 船在右岸
self.father = None
self.node = [a, b, flag]
init = Point(A, B, 1) # 初始节点
goal = Point(0, 0, 0) # 目标节点
# 判断传教士是否安全
def safe(s):
if s.a > A or s.a < 0 or s.b > B or s.b < 0 or (s.a != 0 and s.a < s.b) or (s.a != A and A - s.a < B - s.b):
return False
else:
return True
def equal(a, b):
if a.node == b.node:
return True
# 判断当前状态与父状态是否一致
def back(new, s):
if s.father is None:
return False
return equal(new, s.father)
# 扩展节点时在open表和closed表中找原来是否存在相同mcb属性的节点
def in_list(new, l):
for item in l:
if new.node == item.node:
return True
return False
def BFS(s):
global OPEN, CLOSED
OPEN = [s]
CLOSED = []
while OPEN: # open表非空
get = OPEN[0] # 取出open表第一个元素get
if get.node == goal.node: # 判断是否为目标节点
return get
OPEN.remove(get) # 将get从open表移出
CLOSED.append(get) # 将get加入closed表
# 以下得到一个get的新子节点new并考虑是否放入open
for i in range(A): # 上船传教士
for j in range(B): # 上船野人
# 船上非法情况
if i + j == 0 or i + j > K or (i != 0 and i < j):
continue
if get.flag == 1: # 当前船在左岸，下一状态统计船在右岸的情况
new = Point(get.a - i, get.b - j, 0)
else: # 当前船在右岸，下一状态统计船在左岸的情况
new = Point(get.a + i, get.b + j, 1)
if not safe(new) or back(new, get): # 状态非法或new折返了
pass
# 如果要拓展的节点满足以上情况，将它的父亲设为当前节点，计算f，并对open_list排序
else:
new.father = get
if in_list(new, OPEN):
pass
elif in_list(new, CLOSED):
pass
else:
OPEN.append(new)
print('OPEN表：')
for o in OPEN:
print(o.node)
def DFS(s):
global OPEN, CLOSED
OPEN = [s]
CLOSED = []
while OPEN: # open表非空
get = OPEN[0] # 取出open表第一个元素get
if get.node == goal.node: # 判断是否为目标节点
return get
OPEN.remove(get) # 将get从open表移出
CLOSED.append(get) # 将get加入closed表
# 以下得到一个get的新子节点new并考虑是否放入open
for i in range(A): # 上船传教士
for j in range(B): # 上船野人
# 船上非法情况
if i + j == 0 or i + j > K or (i != 0 and i < j):
continue
if get.flag == 1: # 当前船在左岸，下一状态统计船在右岸的情况
new = Point(get.a - i, get.b - j, 0)
else: # 当前船在右岸，下一状态统计船在左岸的情况
new = Point(get.a + i, get.b + j, 1)
if not safe(new) or back(new, get): # 状态非法或new折返了
pass # CHILD.pop()
# 如果要拓展的节点满足以上情况，将它的父亲设为当前节点，计算f，并对open_list排序
else:
new.father = get
if in_list(new, OPEN):
pass
elif in_list(new, CLOSED):
pass
else:
OPEN.insert(0,new)
print('OPEN表：')
for o in OPEN:
print(o.node)
# 递归打印路径
def printPath(f):
if f is None:
return
printPath(f.father)
# 注意print()语句放在递归调用前和递归调用后的区别。放在后实现了倒叙输出
print(f.node)
if __name__ == '__main__':
final = DFS(init)
if final:
print('有解，解为：')
printPath(final)
else:
print('无解！')