实验报告
一、实验名称：
传教士和野人过河
二、实验目的：
这是经典的过河方案规划问题，通过本实验的设计与编程实现让学生掌握基于状态空间知识表示方法的一般搜索策略。
三、实验内容：
设有3个传教士和3个野人同在河的左岸，他们都要到对岸去；河里只有一条船，他们都会划船，但每次渡船至多只能乘两人；如果在任何一岸上，也认的数量超过传教士，野人就要吃掉传教士，要求设计算法，用船将3个传教士和3个野人安全的从左岸移到右岸。
四、实验设计
(一) 所用的语言：c++语言
(二) 数据结构
节点状态用列表(m，c，b)表示，其中m表示传教士在左岸的人数； c表示野人在左岸的人数；b表示船是否在左岸，当b=1时，表示船在左岸，当b=0时，表式船在右岸。
初始状态：(3，3，1)
目标状态：(0，0，0)
操作算子：船上人数组合（m，c）共5种 （1，0），（1，1），（2，0），（0，1），（0，2）
因此算法有10种
1)从右岸向左岸过1个传教士，0个野人
2)从右岸向左岸过1个传教士，1个野人
3)从右岸向左岸过2个传教士，0个野人
4)从右岸向左岸过0个传教士，1个野人
5)从右岸向左岸过0个传教士，2个野人
6)从左岸向右岸过1个传教士，0个野人
7)从左岸向右岸过1个传教士，1个野人
8)从左岸向右岸过2个传教士，0个野人
9)从左岸向右岸过0个传教士，1个野人
10) 从左岸向右岸过0个传教士，2个野人
状态节点：typedef struct st
{
int m； //传教士
int c； //野人
int b； //船左
}state； //状态
将有效的节点存储在树中
Tree 中的节点
typedef struct hnode
{
state s；
struct hnode *left；
struct hnode *right；
}node；
Open表，closed表 用队列存储
//定义队列中的节点
typedef structQueuenode
{
node* np；
struct Queuenode*next；
}Qnode； //队列中节点
//定义队列
typedef structQueue
{
Qnode *front；
Qnode *rear；
}queue；
(三) 算法流程
1. 用起始节点(3，3，1) 初始化tree，初始化open表，closed表。
2. 把tree中节点放到open表中。
3. 如果open表为空，则失败，退出，无解。
4. 从open表中取对头元素q。
5. 扩展节点q，对q中的节点值，进行五步操作计算，得到五个节点。
逐个检查五个节点
1) 如果该节点不合法，则继续检查下一个节点；如果合法，进行下一步。
2) 如果open表中含有节点，则修改q节点的左指针为查找到节点的地址；
否则，如果此节点的在closed表中，则生成一个新节点，为新节点赋值。如果为此树中q节点的第一孩子，则将该新节点赋值给q的左孩子；否则将其赋值给q的左孩子的右孩子的右孩子。将该新节点加入到open表中。
否则， 继续检查下一个节点。
6. 把节点q从open表中移出，并把它放入closed的扩展节点表中。
7. 取出open表队头节点q，判断是否为目标节点，如果是则返回，终止搜索，并且将其加入到closed表中；否则，转向步骤5。
8. 用栈遍历tree，将结果输出。
五、实验结果
如下图：总共有四种方法完成本题目
如果觉得《传教士 野人 过河问题》对你有帮助，请点赞、收藏，并留下你的观点哦！
