|
国科大学习资料–人工智能原理与算法-2020年期末考试题解析 张文生老师主讲 试卷共有6道题，题目不难，希望大家能取得好的成绩。
3.9 传教士和野人问题。三个传教士和三个野人在河的一岸，有一条能载一个人或者两个人的船。请设法使所有人都渡到河的另一岸，要求在任何地方野人数都不能多于传教士的人数。这个问题在AI领域中很有名，是因为它是第一个从分析的观点探讨问题形式化的论文的主题（Amarel，1968)。
a. 请对该问题进行详细形式化，只描述确保该问题求解所必需的特性。画出完整的状态空间图。
b. 应用合适的搜索算法求出该问题的最优解。对于这个问题检査重复状态是个好主意吗？
c. 这个问题的状态空间很简单，你认为是什么导致人们求解它很困难？
答： (a)状态：定义一个三元组（c,y,z）来描述河岸上情况，其中c和y分别代表某一岸上的传教士和野人数量，z只能取-1和1，其中1代表船在初始岸，-1代表对岸。其中c和y满足的约束条件为c>=y以及C+Y=1 or 2,C和Y分别代表船上的传教士和野人。 初始状态：3个传教士和3个野人都在河的初始岸，船也在初始岸。 转移模型：船可以每次至多渡两人过河，在满足限制的条件下即可进入下一状态。 目标测试：是否达到终态（0，0，-1） 路径消耗：船来回移动的路径 状态空间图如下图所示：
|