人工智能及其应用实验一
传教士与野人问题
实验报告
学号：
姓名：
年级：
院系：
一、实验内容
编写一个计算机程序，求出传教士与野人问题安全渡河的解
答
二、实验理解
这是人工智能领域比较经典的一个题目，目前已知的较好的
解决方案是应用状态空间法，状态空间是一个表示待求解问题
所有可能状态及其关系的图。
在解决一个复杂问题时，我们经常采用试探的方法，通过在
当前问题所处的状态上施以某些操作，产生可能包含问题最终
解答的多个状态，然后按照某种顺序，将某种操作逐一应用在
这些状态上，继续产生新的状态集，如此往复，直道最后找到
一个可行解。传教士与野人问题就属于这类问题。
起初没有什么思路，看了网上别人的想法，大家几乎都采用
的都是人工生成所有状态的方法，但是如果题目要求的总人数
增多，则这种方法必然行不通，即不具有普适性。本实验中我
力求能够让计算机自动地生成所有可行状态，使得问题中的人
数不限为 6 人，具有更好的普适性。
这是我实验分析阶段打的草稿：
三、概要设计
1
、问题概览
可以认为该问题初始时有两个状态，A 岸设为源地点，B 岸
设为目的地点，状态设为一个四元组 (Nm,Nc,level,ag)，其中
Nm 为传教士人数，Nc 为野人人数，level 表示该状态在状态树
中所处的层次，方便最终结果的输出，ag 表示目前船所处的位
置，ag=1 表示在 A 岸，ag=-1 表示在 B 岸。
问 题 初 始 状 态 为 所 有 人 都 在 源 地 点 ， 船 在 源 地 点 ， 即
SA={(3,3,0,1)},SB={(0,0,0,1)}。
问题的操作符集合 OP 就是船每次载人的方式，根据问题需
要此处 OP={(0,1),(1,0),(1,1),(0,2),(2,0)}，例如操作符（1,1）表示
此次船上载了一个传教士和一个野人，其他类似。
问题的目标状态 G 应当是源地点的所有人都被送到了目的地
船停在目的地，即 A 岸状态为 GA={（0,0,level,-1）}，B 岸状态
为 GB={（3,3,level,-1）}。
综上可知，该问题的状态空间可以记为三元状态(S,OP,G)，问
题的求解过程就是在初始状态 S 上应用操作符 OP，使得最终找
到一个满足条件的状态 G。
初始状态图
小
河
A 岸
源地点
(Nm,Nc,0,1)
B 岸
目的地
(0,0,0,1)
