人工智能实验2传教士过河问题

实验 传教士野人过河问题37030602 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem ）。

在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。

此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

二、解答步骤(1) 设置状态变量并确定值域M 为传教士人数，C 为野人人数，B 为船数，要求M>=C 且M+C <= 3，L 表示左岸，R 表示右岸。

初始状态 目标状态L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(2) 确定状态组，分别列出初始状态集和目标状态集用三元组来表示f S ：（ML , CL , BL ）（均为左岸状态）其中03,03ML CL ≤≤≤≤,BL ∈{ 0 , 1}0S ：(3 , 3 , 1) g S ： (0 , 0 , 0)初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij 操作。

其中，第一下标i 表示船载的传教士数，第二下标j 表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。

则共有10种操作，操作集为F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P 10 if ( ML ,CL , BL=1 ) then ( ML –1 , CL , BL –1 )P 01 if ( ML ,CL , BL=1 ) then ( ML , CL –1 , BL –1 )P 11 if ( ML ,CL , BL=1 ) then ( ML –1 , CL –1 , BL –1 )P 20 if ( ML ,CL , BL=1 ) then ( ML –2 , CL , BL –1 )P 02 if ( ML ,CL , BL=1 ) then ( ML , CL –2 , BL –1 )Q 10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )Q 01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )Q 11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 )(4)当状态数量不是很大时，画出合理的状态空间图图1 状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。

有三个食人族人和三个传教士要过河，现在只有一条船，但一次只能载两个人，而无论在河的哪一边，只要食人族人比传教士多，食人族人就会把传教士吃掉。

问他怎么样才能安全的过河？
设：要从河的a岸到河的b岸。

1、一食人族和一传教士开船过河，到了b岸后食人族留在河的b岸，传教士把船开回a岸；（现在是三个传教士和两个食人族在a岸，一食人族在b岸）。

2、船开回a岸后，两个食人族开船过河，到了b岸后，一食人族留在河的b岸，让一名食人族把船开回a岸；（现在是三个传教士和一个食人族在a岸，两个食人族在b岸）
3、其中一食人族把船开回a岸后，食人族下船，让两名传教士开船过河，过河后（到b岸后）又让一食人族和一传教士把船开a岸；（现在是两个传教士和两个食人族在a岸，一传教士一食人族在b岸）
4、船到a岸后，让两个传教士开船过河，到了b岸后，传教士下船让在b岸的那个食人族把船开回a岸；（现在是三传教士在b岸，三食人族在a岸）
5、船回到a岸后，两食人族过河，到b岸后一食人族把船开回a岸，再两食人族开船渡河。

传教士(牧师)与野人问题-模拟人工智能实验_结缘缘的博客-CSDN博客_传教士与野人问题题目有n个牧师和n个野人准备渡河但只有一条能容纳c个人的小船为了防止野人侵犯牧师要求无论在何处牧师的人数不得少于野人的人数(除非牧师人数为0) 且假定野人与牧师都会划船试设计一个算法确定他们能否渡过河去若能则给出小船来回次数最少的最佳方案。

实验步骤输入牧师人数(即野人人数) n 小船一次最多载人量c。

输出若问题无解则显示Failed 否则显示Successed输出所有可行方案并标注哪一组是最佳方案。

用三元组(X1, X2, X3)表示渡河过程中的状态。

并用箭头连接相邻状态以表示迁移过程初始状态- 中间状态- 目标状态。

例当输入n 2 c 2时输出221- 200- 211- 010- 021- 000 其中X1表示起始岸上的牧师人数X2表示起始岸上的野人人数X3表示小船现在位置(1表示起始岸0表示目的岸)。

要求写出算法的设计思想和源程序并有用户界面实现人机交互控制台或者窗口都可以进行输入和输出结果如Please input n: 2 Please input c: 2 Optimal Procedure: 221- 200- 211- 010- 021- 000Successed or Failed?: Successed实现代码#include stdio.h #include iostream #include stdlib.h using namespace std;struct State { int Lsavage; int Lgodfather; int Rsavage; int Rgodfather; int boat; //boat at left 0 ; boat at right struct State *States new State[150];struct routesave { int savage; int godfather;struct routesave* routesaves new routesave[150];int godfather, savage, boatnum;void init(State m) { cout 请输入野人和牧师的人数n 以及船的最大载量c endl; int n, c; cin n c; m.Rgodfather n; m.Rsavage n; godfather n, savage n; boatnum c; m.Lgodfather m.Lsavage 0; m.boat 1;void boaloading(int i, int s, int g) { //s个野人和g个传教士if (States[i].boat 0) { routesaves[i].savage s*-1; //左边到右边是负数个野人routesaves[i].godfather g * -1; //左边到右边负数个传教士States[i 1].LsavageStates[i].Lsavage - s; States[i 1].Lgodfather States[i].Lgodfather - g; States[i 1].Rsavage States[i].Rsavage s; States[i 1].Rgodfather States[i].Rgodfather g; States[i 1].boat 1; else{ routesaves[i].savage s; //右边到左边是正数个野人routesaves[i].godfather g; //右边到左边正数个传教士States[i 1].Rsavage States[i].Rsavage-s; States[i 1].RgodfatherStates[i].Rgodfather - g; States[i 1].Lsavage States[i].Lsavage s; States[i 1].Lgodfather States[i].Lgodfather g; States[i 1].boat0;bool checkState(State m) { if (m.Rgodfather 0 m.Rgodfather m.Rsavage) return false; if (m.Lgodfather 0 m.Lgodfatherm.Lsavage) return false; else return true;void showSolution(int i) { cout 问题解决解决路径为endl; for (int c 0; c i; c ) { if (routesaves[c].savage 0) cout 第c 1 步routesaves[c].savage 个野人和routesaves[c].godfather 个传教士乘船去左边endl; else cout 第c 1 步routesaves[c].savage * -1 个野人和routesaves[c].godfather * -1 个传教士乘船去有右边endl; void nextstep(int i) { int c; if (i 150) cout 试探路径过大无法计算; exit(0); for (c 0; c i; c ) /*if the current state is same to previous,retrospect*/ if (States[c].Lsavage States[i].Lsavage States[c].Lgodfather States[i].Lgodfather States[c].Rsavage States[i].Rsavage States[c].Rgodfather States[i].Rgodfather States[c].boat States[i].boat) goto a; if (States[i].Rsavage 0 States[i].Rgodfather 0 States[i].boat 0) { showSolution(i); exit(0); if (States[i].boat 1) { //船在右边for (int s 1; s boatnum s States[i].Rsavage; s ) {//g 0 int g 0; boaloading(i, s, g); if (checkState(States[i 1])) { nextstep(i 1); for (int g 1; g boatnum g States[i].Rgodfather; g ) { //g! 0 for (int s 0; s boatnum - g s States[i].Rsavage s g; s ) { boaloading(i, s, g); if(checkState(States[i 1])) { nextstep(i 1); if (States[i].boat 0) { //船在左边for (int s 1; s boatnum s States[i].Lsavage; s ) {//g 0int g 0; boaloading(i, s, g); if (checkState(States[i 1])) { nextstep(i 1); for (int g 1; g boatnum g States[i].Lgodfather; g ) { //g! 0 for (int s 0; s boatnum - g s States[i].Lsavage s g; s ) { boaloading(i, s, g); if (checkState(States[i 1])) { nextstep(i 1);a:return;void main() { init(States[0]); nextstep(0);实验结果展示。

第二章知识表示方法2-2 设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。

该船的负载能力为两人。

在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。

他们怎样才能用这条船安全地把所有人都渡过河去（答案并不唯一，意思正确即可）用S i(nC, nY) 表示第i次渡河后，河对岸的状态，nC表示传教士的数目，nY表示野人的数目，由于总人数的确定的，河对岸的状态确定了，河这边的状态也即确定了。

考虑到题目的限制条件，要同时保证，河两岸的传教士数目不少于野人数目，故在整个渡河的过程中，允许出现的状态为以下3种情况：1. nC=02. nC=33. nC=nY>=0 (当nC不等于0或3)用d i(dC, dY)表示渡河过程中，对岸状态的变化，dC表示，第i次渡河后，对岸传教士数目的变化，dY表示，第i次渡河后，对岸野人数目的变化。

当i为偶数时，dC,dY同时为非负数，表示船驶向对岸，i为奇数时，dC, dY同时为非正数，表示船驶回岸边。

初始状态为S0(0, 0)，目标状态为S0(3, 3)，用深度优先搜索的方法可寻找渡河方案。

在此，用图求法该问题，令横坐标为nY, 纵坐标为nC，可行状态为空心点表示，每次可以在格子上，沿对角线移动一格，也可以沿坐标轴方向移动1格，或沿坐标轴方向移动2格。

第奇数次数状态转移，沿右方，上方，或右上方移动，第偶数次数状态转移，沿左方，下方，或左下方移动。

从(0,0)开始，依次沿箭头方向改变状态，经过11步之后，即可以到达目标状态(3,3)，相应的渡河方案为：d1(1,1)--d2(-1,0)--d3(0,2)--d4(0,-1)--d5(2,0)--d6(-1,-1)--d7(2,0)--d8(0,-1)--d9(0,2)--d10(-1,0)--d11(1,1)2-5 试用四元数列结构表示四圆盘梵塔问题，并画出求解该问题的与或图。

用四元数列 (nA, nB, nC, nD) 来表示状态，其中nA 表示A 盘落在第nA 号柱子上，nB 表示B 盘落在第nB 号柱子上，nC 表示C 盘落在第nC 号柱子上，nD 表示D 盘落在第nD 号柱子上。

实验 传教士野人过河问题37030602 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem ）。

在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。

此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

二、解答步骤(1) 设置状态变量并确定值域M 为传教士人数，C 为野人人数，B 为船数，要求M>=C 且M+C <= 3，L 表示左岸，R 表示右岸。

初始状态 目标状态L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(2) 确定状态组，分别列出初始状态集和目标状态集用三元组来表示f S ：（ML , CL , BL ）（均为左岸状态）其中03,03ML CL ≤≤≤≤,BL ∈{ 0 , 1}0S ：(3 , 3 , 1) g S ： (0 , 0 , 0)初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij 操作。

其中，第一下标i 表示船载的传教士数，第二下标j 表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。

则共有10种操作，操作集为F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P 10 if ( ML ,CL , BL=1 ) then ( ML –1 , CL , BL –1 )P 01 if ( ML ,CL , BL=1 ) then ( ML , CL –1 , BL –1 )P 11 if ( ML ,CL , BL=1 ) then ( ML –1 , CL –1 , BL –1 )P 20 if ( ML ,CL , BL=1 ) then ( ML –2 , CL , BL –1 )P 02 if ( ML ,CL , BL=1 ) then ( ML , CL –2 , BL –1 )Q 10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )Q 01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )Q 11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 )(4)当状态数量不是很大时，画出合理的状态空间图图1 状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。

实验 传教士野人过河问题王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem ）。

在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。

此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

二、解答步骤(1) 设置状态变量并确定值域M 为传教士人数，C 为野人人数，B 为船数，要求M>=C 且M+C <= 3，L 表示左岸，R 表示右岸。

初始状态 目标状态L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(2) 确定状态组，分别列出初始状态集和目标状态集用三元组来表示f S ：（ML , CL , BL ）（均为左岸状态）其中03,03ML CL ≤≤≤≤,BL ∈{ 0 , 1}0S ：(3 , 3 , 1) g S ： (0 , 0 , 0)初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij 操作。

其中，第一下标i 表示船载的传教士数，第二下标j 表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。

则共有10种操作，操作集为F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P 10 if ( ML ,CL , BL=1 ) then ( ML –1 , CL , BL –1 )P 01 if ( ML ,CL , BL=1 ) then ( ML , CL –1 , BL –1 )P 11 if ( ML ,CL , BL=1 ) then ( ML –1 , CL –1 , BL –1 )P 20 if ( ML ,CL , BL=1 ) then ( ML –2 , CL , BL –1 )P 02 if ( ML ,CL , BL=1 ) then ( ML , CL –2 , BL –1 )Q 10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )Q 01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )Q 11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 )(4)当状态数量不是很大时，画出合理的状态空间图图1 状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。

实验二 传教士与野人过河问题一、实验目的理解并熟悉掌握深度优先搜索和广度优先搜索算法。

二、实验内容设有3个传教士和3个野人来到河边，打算乘一只船从左岸到右岸去。

该船的负载能力为两人。

在任何时候，如果野人人数超过传教士人数，野人就会把传教士吃掉。

他们怎样才能用这条船安全的把所有人都渡过河去?三、实验内容（1）设置状态变量并确定值域设M 为传教士人数，C 为野人人数，B 为船数，要求M>=C 且M+C <= 3， L 表示左岸，R 表示右岸。

初始状态目标状态 L RL R M 3 0M 0 3 C 3 0C 0 3 B 1 0B 0 1（2）确定状态组，分别列出初始状态集和目标状态集用三元组来表示f S ：（ML , CL , BL ）（均为左岸状态） 其中，03,03ML CL ≤≤≤≤,BL ∈{ 0 , 1}0S ：(3 , 3 , 1) g S ： (0 , 0 , 0)初始状态0S ：表示全部成员在河的的左岸；目标状态g S ：表示全部成员从河的左岸全部渡河到河的右岸。

（3）定义并确定规则集合 以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij 操作。

其 中，第一下标i 表示船载的传教士数，第二下标j 表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。

则共有10种操作，操作集为： F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 ) P10Pif ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 ) 01if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) P11Pif ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 ) 20if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 ) P02if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 ) Q10Qif ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 ) 01if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 ) Q11if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 ) Q20if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) Q02（4）当状态数量不是很大时，画出合理的状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和野人数。

实验传教士野人过河问题37030602 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem）。

在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。

此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

二、解答步骤(1) 设置状态变量并确定值域M为传教士人数，C 为野人人数，B为船数，要求M>=C且M+C <= 3，L表示左岸，R表示右岸。

初始状态目标状态L R L RM 3 0 M 0 3C 3 0 C 03B 1 0 B 01(2) 确定状态组，分别列出初始状态集和目标状态集用三元组来表示：（ML , CL , BL）（均为左岸状态）其中,BL ∈{ 0 , 1}：(3 , 3 , 1)： (0 , 0 , 0)初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。

其中，第一下标i表示船载的传教士数，第二下标j表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij操作，下标的定义同前。

则共有10种操作，操作集为F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P10 if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 )P01 if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 )P11 if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 ) P20 if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 )P02 if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 )Q10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )Q01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )Q11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )Q02 if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 ) (4) 当状态数量不是很大时，画出合理的状态空间图图1 状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。

传教士-野人问题有N个传教士和N个野人要过河，现在有一条船只能承载K个人（包括野人），K<N，在任何时刻，如果有野人和传教士在一起，必须要求传教士的人数多于或等于野人的人数。

设M为传教士的人数，C为野人的人数，用状态空间发求解此问题的过程如下：M、C = N，boat = k，要求M>=C且M+C <= K初始状态目标状态L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(1)用三元组来表示（ML , CL , BL）其中0<=ML , CL <= 3 , BL ∈{ 0 , 1}(3 , 3 , 1) (0 , 0 , 0)(2)规则集合P10if ( ML ,CL , BL=1 ) then ( ML–1 , CL , BL –1 )P01if ( ML ,CL , BL=1 ) then ( ML , CL–1 , BL –1 )P11if ( ML ,CL , BL=1 ) then ( ML–1 , CL–1 , BL –1 )P20if ( ML ,CL , BL=1 ) then ( ML–2 , CL , BL –1 )P02if ( ML ,CL , BL=1 ) then ( ML , CL–2 , BL –1 )Q10if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )Q01if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )Q11if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 )(3)寻找一个启发式函数引导规则的选用右岸总人数6 – ML – CL 两岸中传教士数目>=野人数目f =–∞其它f=3 Q 01f=2 P 02 f=1 Q 01f=1 Q 11f=1 P 01 f=2 P 11 （3，3，1） （3，2，0）（2，2，0） （3，1，0） （3，2，1） （3，0，0） f=3 P 02（3，1，1） f=2 Q 01（1，1，0） f=4 P 20（2，2，1） f=2 Q 11（1，1，0） f=4 P 20（2，2，1） f=2 Q 11（0，2，0） f=4 P 20（0，3，1）f=3 Q 01（0，1，1）f=5 P 02（0，2，1） f=4 Q 01 （0，0，0） f=3 Q 01（1，1，1） f=4 Q 106.2.3 用状态空间法求解传教士和食人者问题传教士和食人者问题（The Missionaries and Cannibals Problem）。

实验 传教士野人过河问题37030602 王世婷一、实验问题传教士和食人者问题（The Missionaries and Cannibals Problem ）。

在河的左岸有3个传教士、1条船和3个食人者，传教士们想用这条船将所有的成员运过河去，但是受到以下条件的限制：（1）传教士和食人者都会划船，但船一次最多只能装运两个；（2）在任何岸边食人者数目都不得超过传教士，否则传教士就会遭遇危险：被食人者攻击甚至被吃掉。

此外，假定食人者会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。

二、解答步骤(1) 设置状态变量并确定值域M 为传教士人数，C 为野人人数，B 为船数，要求M>=C 且M+C <= 3，L 表示左岸，R 表示右岸。

初始状态 目标状态L R L RM 3 0 M 0 3C 3 0 C 0 3B 1 0 B 0 1(2) 确定状态组，分别列出初始状态集和目标状态集用三元组来表示f S ：（ML , CL , BL ）（均为左岸状态）其中03,03ML CL ≤≤≤≤,BL ∈{ 0 , 1}0S ：(3 , 3 , 1) g S ： (0 , 0 , 0)初始状态表示全部成员在河的的左岸；目标状态表示全部成员从河的左岸全部渡河完毕。

(3) 定义并确定规则集合仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij 操作。

其中，第一下标i 表示船载的传教士数，第二下标j 表示船载的食人者数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。

则共有10种操作，操作集为F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}P 10 if ( ML ,CL , BL=1 ) then ( ML –1 , CL , BL –1 )P 01 if ( ML ,CL , BL=1 ) then ( ML , CL –1 , BL –1 )P 11 if ( ML ,CL , BL=1 ) then ( ML –1 , CL –1 , BL –1 )P 20 if ( ML ,CL , BL=1 ) then ( ML –2 , CL , BL –1 )P 02 if ( ML ,CL , BL=1 ) then ( ML , CL –2 , BL –1 )Q 10 if ( ML ,CL , BL=0 ) then ( ML+1 , CL , BL+1 )Q 01 if ( ML ,CL , BL=0 ) then ( ML , CL+1 , BL +1 )Q 11 if ( ML ,CL , BL=0 ) then ( ML+1 , CL +1, BL +1 )Q20 if ( ML ,CL , BL=0 ) then ( ML+2 , CL +2, BL +1 )Q02if ( ML ,CL , BL=0 ) then ( ML , CL +2, BL +1 )(4)当状态数量不是很大时，画出合理的状态空间图图1 状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和食人者数。

传教士过河问题实验报告计研-12 2012312120115 宋玲玲1．实验目的（1）了解知识表示相关技术；（2）掌握问题规约法或者状态空间法的分析方法。

2．实验内容从前有一条河，河的左岸有m个传教士、m个野人和一艘最多可乘n人的小船。

约定左岸，右岸和船上或者没有传教士，或者野人数量少于传教士，否则野人会把传教士吃掉。

搜索一条可使所有的野人和传教士安全渡到右岸的方案。

3．实验原理及方法假设开始时传教士、野人和船都在右岸，用数组(a,b,c)分别表示右岸传教士个数、右岸野人个数、船的位置，则可分为三种情况讨论:A、n>m/2。

此种情况下，先把所有的野人度过去，每次返回一个野人，当出现(m,0,0)情况时，返回m-n个野人(若m==n,返回1个野人)。

然后渡n个传教士，此时野人==传教士，然后返回一个野人和传教士，再开始最大限度的渡传教士，每次返回一个野人,最终直到a==b==c==0；B、n<=3&&n<=m/2 || n==1，显然此时无解；C、n>=4&&n<=m/2，此时只能每次传n/2个传教士和野人,每次返回一个野人和传教士,直到最终结果。

程序流程图如下：4、源程序清单：本程序用C++语言编写。

#include"iostream"using namespace std;bool flag = false; //标记是否有解bool af = false; //标记a是否为0bool bf = false; //当b变为0后赋值为true;bool ef = false; //当a==b后赋值为truebool f = false; //判断n是否大于m/2int m;//传教士野人的个数int n;//船一次能装载的人数void mc(int a,int b,int c);int main(){cout<<"传教士与野人过河问题。

第二章知识表示方法2-2 设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。

该船的负载能力为两人。

在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。

他们怎样才能用这条船安全地把所有人都渡过河去?用S i(nC, nY) 表示第i次渡河后，河对岸的状态，nC表示传教士的数目，nY表示野人的数目，由于总人数的确定的，河对岸的状态确定了，河这边的状态也即确定了。

考虑到题目的限制条件，要同时保证，河两岸的传教士数目不少于野人数目，故在整个渡河的过程中，允许出现的状态为以下3种情况：1. nC=02. nC=33. nC=nY>=0 (当nC不等于0或3)用d i(dC, dY)表示渡河过程中，对岸状态的变化，dC表示，第i次渡河后，对岸传教士数目的变化，dY表示，第i次渡河后，对岸野人数目的变化。

当i为偶数时，dC,dY同时为非负数，表示船驶向对岸，i为奇数时，dC, dY同时为非正数，表示船驶回岸边。

初始状态为S0(0, 0)，目标状态为S0(3, 3)，用深度优先搜索的方法可寻找渡河方案。

在此，用图求法该问题，令横坐标为nY, 纵坐标为nC，可行状态为空心点表示，每次可以在格子上，沿对角线移动一格，也可以沿坐标轴方向移动1格，或沿坐标轴方向移动2格。

第奇数次数状态转移，沿右方，上方，或右上方移动，第偶数次数状态转移，沿左方，下方，或左下方移动。

从(0,0)开始，依次沿箭头方向改变状态，经过11步之后，即可以到达目标状态(3,3)，相应的渡河方案为：d1(1,1)--→d2(-1,0)--→d3(0,2)--→d4(0,-1)--→d5(2,0)--→d6(-1,-1)--→d7(2,0)--→d8( 0,-1)--→d9(0,2)--→d10(-1,0)--→d11(1,1)2-6 把下列句子变换成子句形式：(1) (x)｛P(x)→P(x)｝(2) xy(On(x,y)→Above(x,y))(3) xyz(Above(x,y)∧Above(y,z)→Above(x,z))(4) ～｛(x)｛P(x)→｛（y）［p(y)→p(f(x,y))］∧(y)［Q(x,y)→P(y)］｝｝｝1.(ANY x) { P(x)→P(x) }(ANY x) {~P(x) OR P(x)}~P(x) OR P(x)最后子句为~P(x) OR P(x)(2) (ANY x) (ANY y) { On(x,y)→Above(x,y) }(ANY x) (ANY y) { ~On(x,y) OR Above(x,y) }~On(x,y) OR Above(x,y)最后子句为~On(x,y) OR Above(x,y)(3) (ANY x) (ANY y) (ANY z) { Above(x,y) AND Above(y,z) → Above(x,z) }(命题联结词之优先级如下:否定→合取→析取→蕴涵→等价)(ANY x) (ANY y) (ANY z) { ~ [ Above(x,y) AND Above(y,z) ] OR Above (x,z) }~ [ Above(x,y) AND Above(y,z) ] OR Above (x,z)最后子句为~[Above(x,y), Above(y,z)] OR Above(x,z)(4) ~{ (ANY x) { P(x)→ { (ANY y) [ p(y)→p(f(x,y)) ] AND (ANY y) [ Q(x,y) → P(y) ] } } }~ { (ANY x) { ~P(x) OR { (ANY y) [ ~p(y) OR p(f(x,y)) ] AND (ANY y) [ ~Q(x,y) OR P(y) ] } } }(EXT x) { P(x) AND { (EXT x) [ p(y) AND ~p(f(x,y)) ] OR (EXT y) [ Q(x,y) AND ~P(y) ] } }(EXT x) { P(x) AND { (EXT w) [ p(y) AND ~p(f(w,y)) ] OR (EXT v) [ Q(x,v) AND ~P(v) ] } }P(A) AND { [ p(y) AND ~p(f(B,y)) ] OR [ Q(A,C) AND ~P(C) ] }P(A) AND { [ p(y) AND ~p(f(B,y)) OR Q(A,C) ] AND [ p(y) AND ~p(f(B,y)) OR ~P(C) ] }P(A) AND { { p(y), ~p(f(B,y)) } OR Q(A,C) } AND { { p(y), ~p(f(B,y)) } OR ~P(C) }最后子句为P(A){ p(x), ~p(f(B,x)) } OR Q(A,C){ p(y), ~p(f(B,y)) } OR ~P(C)2-7 用谓词演算公式表示下列英文句子(多用而不是省用不同谓词和项。