AI传教士和野人渡河问题

2024-07-16 05:58| 来源: 网络整理| 查看: 265

一题目要求：

设有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 B or s.b

【本文地址】

公司简介

联系我们