传教士和野人问题实验报告

人工智能实验报告班级：计研-12班学号：2012312120105 姓名：孔德星实验二知识表示方法1．实验目的（1）了解知识表示相关技术；（2）掌握问题规约法或者状态空间法的分析方法。

2．实验内容（2个实验内容可以选择1个实现）（1）梵塔问题实验。

熟悉和掌握问题规约法的原理、实质和规约过程；理解规约图的表示方法；（2）状态空间法实验。

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

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

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

3．实验报告要求（1）简述实验原理及方法，并请给出程序设计流程图。

实验原理：假设开始时传教士、野人和船都在右岸，用数组(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个传教士和野人,每次返回一个野人和传教士,直到最终结果。

程序流程图：（2）源程序清单：本程序用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<<"传教士与野人过河问题。

传教士与野人过河问题实验报告1 问题定义河的两岸有三个传教士和三个野人需要过河，目前只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会被野人攻击，怎么找出一种安全的渡河方案呢？2 算法分析首先，先来看看问题的初始状态和目标状态，定义河的两岸分别为左岸和右岸，设定状态集合为（左岸传教士人数，右岸野人数，右岸传教士人数，右岸野人数，船的位置），船的位置：-1表示船在左岸，1表示船在右岸。

初始状态：（3,3,0,0,0，-1）目标状态：（0，0，3，3，1）然后，整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。

问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士根据船的位置，向左移或向右移通过递归依次执行5种算符，判断是否找到所求，并排除不符合实际的状态，就可以找到所有可能的解，如图1所示为递归函数流程图。

数据结构方面采用如下所示的结构体存储当前传教士、野人、船三者的状态。

struct riverSides {int churchL;//左岸传教士数int wildL;//左岸野人数int churchR; //右岸传教士数int wildR; //右岸野人数int boat;//船的位置，-1在左岸，1在右岸};图 1 传教士与野人过河递归函数流程图3 编程实现程序使用C++实现，具体代码如下：#include<iostream>#include<vector>#include<string>using namespace std;struct riverSides{int churchL;//左岸传教士数int wildL;//左岸野人数int churchR; //右岸传教士数int wildR; //右岸野人数int boat;//船的位置，-1在左岸，1在右岸};int mycount = 0;//统计成功过河次数int CvsWdfs(riverSides lastcurrentState, vector <riverSides> lastParameters, vector<string> operation, int ifboacurrentStatety){if (lastcurrentState.churchR == 3 && lastcurrentState.wildR == 3){mycount++;cout << "第" << mycount << "次成功过河" << endl;cout << "传教士野人 | 移动方向" << endl;for (int i = 0; i < operation.size(); i++){cout << operation[i] << endl;}cout << endl;return 0;}//判断过河操作否重复，去除死循环for (int i = 0; i < lastParameters.size() - 1; i++){if (lastParameters[i].wildL == lastcurrentState.wildL&&lastParameters[i].churchL == lastcurrentState.churchL){if (lastcurrentState.boat == lastParameters[i].boat)return 0;}}//检验人数数据合法性if (lastcurrentState.churchL < 0 || lastcurrentState.wildL < 0 || lastcurrentState.churchR < 0 || lastcurrentState.wildR < 0)return 0;//传教士是否被吃if ((lastcurrentState.churchL < lastcurrentState.wildL&&lastcurrentState.churchL != 0) || (lastcurrentState.churchR < lastcurrentState.wildR&&lastcurrentState.churchR != 0)) return 0;//递归执行五类过河操作，boat=-1船在左岸，boat=1船在右岸，传入boat为上一次船位置//下次应当取反riverSides currentState;//两个传教士过河if (lastcurrentState.boat == 1)operation.push_back(" 2 0 | 左岸->右岸");elseoperation.push_back(" 2 0 | 右岸->左岸");currentState.churchL = lastcurrentState.churchL - 2 * lastcurrentState.boat;currentState.wildL = lastcurrentState.wildL;currentState.churchR = lastcurrentState.churchR + 2 * lastcurrentState.boat;currentState.wildR = lastcurrentState.wildR;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters,operation, 0);operation.pop_back();lastParameters.pop_back();//两个野人过河if (lastcurrentState.boat == 1)operation.push_back(" 0 2 | 左岸->右岸");elseoperation.push_back(" 0 2 | 右岸->左岸");currentState.churchL = lastcurrentState.churchL;currentState.wildL = lastcurrentState.wildL - 2 * lastcurrentState.boat;currentState.churchR = lastcurrentState.churchR;currentState.wildR = lastcurrentState.wildR + 2 * lastcurrentState.boat;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters, operation, 0);lastParameters.pop_back();operation.pop_back();//一个野人，一个传教士if (lastcurrentState.boat == 1)operation.push_back(" 1 1 | 左岸->右岸");elseoperation.push_back(" 1 1 | 右岸->左岸");currentState.churchL = lastcurrentState.churchL - 1 * lastcurrentState.boat;currentState.wildL = lastcurrentState.wildL - 1 * lastcurrentState.boat;currentState.churchR = lastcurrentState.churchR + 1 * lastcurrentState.boat;currentState.wildR = lastcurrentState.wildR + 1 * lastcurrentState.boat;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters,operation, 0);operation.pop_back();lastParameters.pop_back();//一个传教士过河if (lastcurrentState.boat == 1)operation.push_back(" 1 0 | 左岸->右岸");elseoperation.push_back(" 1 0 | 右岸->左岸");currentState.churchL = lastcurrentState.churchL - 1 * lastcurrentState.boat;currentState.wildL = lastcurrentState.wildL;currentState.churchR = lastcurrentState.churchR + 1 * lastcurrentState.boat;currentState.wildR = lastcurrentState.wildR;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters, operation, 0);operation.pop_back();lastParameters.pop_back();//一个野人过河if (lastcurrentState.boat == 1)operation.push_back(" 0 1 | 左岸->右岸");elseoperation.push_back(" 0 1 | 右岸->左岸");currentState.churchL = lastcurrentState.churchL;currentState.wildL = lastcurrentState.wildL - 1 * lastcurrentState.boat;currentState.churchR = lastcurrentState.churchR;currentState.wildR = lastcurrentState.wildR + 1 * lastcurrentState.boat;currentState.boat = -lastcurrentState.boat;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters, operation, 0);operation.pop_back();lastParameters.pop_back();return 0;}int main(){int churchL = 3, wildL = 3, churchR = 0, wildR = 0;//分别用来计算左岸和右岸的传教士和野人vector <riverSides> lastParameters;//保存每一步移动操作的两岸传教士、野人人数vector <string> operation;//保存当前操作的描述//初始化左岸参数，可以认为是从右岸移动至左岸的操作//boat=-1 表示船在左岸，boat=1表示船在右岸riverSides currentState;currentState.churchL = 3;currentState.wildL = 3;currentState.churchR = 0;currentState.wildR = 0;currentState.boat = 1;lastParameters.push_back(currentState);CvsWdfs(currentState, lastParameters,operation, 0);lastParameters.pop_back();system("pause");return 0;}4 程序结果最终得到如图2、3所示的四种过河方式。

修道⼠和野⼈问题 休闲时刻看看神经⽹络⽅⾯的书，发现了修道⼠和野⼈的问题，不禁勾引起我写算法的欲望，曾经的三只⼤⽼虎三只⼩⽼虎过河问题、⼈狼⽺⽩菜过河问题、汉诺塔、哈夫曼等等各种算法瞬间在脑海中约隐约现，修道⼠和野⼈问题我以前好像没有解开，中午吃饭的时候在脑海中重新构造思路，下午耗了点时间把它⼲掉。

（算法不在代码⾥，⽽在思想中；所以尽量不要看我的代码，⽽要仔细分析我写的思路）　题⽬： 设有３个修道⼠和３个野⼈来到河边，打算⽤⼀条船从河的左岸渡到河的右岸。

但该船每次只能装载两个⼈，在任何岸边野⼈的数⽬都不得超过修道⼠的⼈数，否则修道⼠就会被野⼈吃掉。

假设野⼈服从任何⼀种过河安排，请问如何规划过河计划才能把所有⼈都安全地渡过河去。

⾸先考虑总共有（3+1）*（3+1）= 16 种不同的状态(因为左岸可以有0，1，2，3个传教⼠，左岸可以有0，1，2，3个野⼈)，所以可以考虑使⽤穷举法。

使⽤如下C#程序语⾔：int MaxNum = 3;for (int monk = MaxNum; monk >= 0; monk--){for (int savage = MaxNum; savage >= 0; savage--){Console.Write("{{" + monk + "," + savage + "},{" + (MaxNum - monk) + "," + (MaxNum - savage) + "}} ");}Console.Write("\n");}⽣成16种状态图↓↓↓↓↓↓↓↓↓↓↓状态图含义：{a,b}：a，左岸修道⼠数量；b，左岸野⼈数量。

--------仅考虑左岸传教⼠和野蛮⼈数量(所有状态图)------------------------{3,3} {3,2} {3,1} {3,0}{2,3} {2,2} {2,1} {2,0}{1,3} {1,2} {1,1} {1,0}{0,3} {0,2} {0,1} {0,0}其中{3,3}是起始状态图；{0,0}是终⽌状态图。

传教士(牧师)与野人问题-模拟人工智能实验_结缘缘的博客-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);实验结果展示。

一、目的与要求目的：使学生加深对图搜索技术的理解，初步掌握图搜索基本编程方法，并能运用图搜索技术解决一些应用问题。

要求：1、可使用第3章中的状态图搜索通用程序，这时只需编写规则集程序；也可用PROLOG语言或其他语言另行编程。

2、程序运行时，应能在屏幕上显示程序运行结果。

二、实验内容与题目内容：传教士和野人问题。

有三个传教士和三个野人一起来到河边准备渡河，河边有一条空船，且传教士和野人都会划船，但每次最多可供两人乘渡。

河的任何一岸以及船上一旦出现野人人数超过传教士人数，野人就会把传教士吃掉。

为安全地渡河，传教士应如何规划渡河方案？题目：图搜索问题求解——过河问题三、实验步骤与源程序源程序：#include <stdlib.h>class CRiver{public:enum{LEFT_BANK = 1, RIGHT_BANK = 0};enum{CHUCHMEN = 0, GOTH = 1};friend ostream & operator << (ostream & Out, CRiver river);bool L01();bool L10();bool L11();bool L02();bool L20();bool R01();bool R10();bool R11();bool R02();bool R20();bool Compare(const CRiver & riverDet);CRiver(const CRiver & pSrc);CRiver();virtual ~CRiver();int m_nShipPos;int m_nChuchmenAndGoth[2][2];CRiver * m_pParent;CRiver * m_pNextStep;protected:private:};CRiver::CRiver(){int i = 0;m_nShipPos = LEFT_BANK;m_pParent = NULL;m_pNextStep = NULL;for (i=0; i<2; i++){m_nChuchmenAndGoth[LEFT_BANK][i] = 3;m_nChuchmenAndGoth[RIGHT_BANK][i] = 0;}}CRiver::~CRiver(){}ostream & operator << (ostream & Out, CRiver river){Out<<"(m, c, b): ";Out<<"(";Out<<river.m_nChuchmenAndGoth[CRiver::LEFT_BANK][CRiver::CHUCHMEN]<<", ";Out<<river.m_nChuchmenAndGoth[CRiver::LEFT_BANK][CRiver::GOTH]<<", ";Out<<river.m_nShipPos<<")";return Out;}bool CRiver::Compare(const CRiver & riverDet){int i = 0;int j = 0;if (m_nShipPos != riverDet.m_nShipPos){return false;}for (i=0; i<2; i++){for (j=0; j<2; j++){if (m_nChuchmenAndGoth[i][j] != riverDet.m_nChuchmenAndGoth[i][j]){return false;}}}return true;}CRiver::CRiver(const CRiver & pSrc){int i = 0;int j = 0;m_pParent = pSrc.m_pParent;m_nShipPos = pSrc.m_nShipPos;for (i=0; i<2; i++){for (j=0; j<2; j++){m_nChuchmenAndGoth[i][j] = pSrc.m_nChuchmenAndGoth[i][j];}}}bool CRiver::L01(){CRiver oldRiver = *this;if (LEFT_BANK == m_nShipPos&& m_nChuchmenAndGoth[LEFT_BANK][GOTH] >= 1&& 0 == (m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] % 3)){m_nShipPos = RIGHT_BANK;m_nChuchmenAndGoth[LEFT_BANK][GOTH]--;m_nChuchmenAndGoth[RIGHT_BANK][GOTH]++;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::L10(){CRiver oldRiver = *this;if (LEFT_BANK == m_nShipPos&& ((2==m_nChuchmenAndGoth[LEFT_BANK][GOTH] &&3==m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN])|| (1==m_nChuchmenAndGoth[LEFT_BANK][GOTH] &&1==m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]))){m_nShipPos = RIGHT_BANK;m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]--;m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]++;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::L11(){CRiver oldRiver = *this;if (LEFT_BANK == m_nShipPos&& m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] >= 1&& (m_nChuchmenAndGoth[LEFT_BANK][GOTH] ==m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN])){m_nShipPos = RIGHT_BANK;m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]--;m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]++;m_nChuchmenAndGoth[LEFT_BANK][GOTH]--;m_nChuchmenAndGoth[RIGHT_BANK][GOTH]++;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::L02(){CRiver oldRiver = *this;if (LEFT_BANK == m_nShipPos&& m_nChuchmenAndGoth[LEFT_BANK][GOTH] >= 2&& 0 == (m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] % 3)){m_nShipPos = RIGHT_BANK;m_nChuchmenAndGoth[LEFT_BANK][GOTH] = m_nChuchmenAndGoth[LEFT_BANK][GOTH] - 2;m_nChuchmenAndGoth[RIGHT_BANK][GOTH]= m_nChuchmenAndGoth[RIGHT_BANK][GOTH] + 2;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::L20(){CRiver oldRiver = *this;if (LEFT_BANK == m_nShipPos&& ((2==m_nChuchmenAndGoth[LEFT_BANK][GOTH] &&2==m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN])|| (1==m_nChuchmenAndGoth[LEFT_BANK][GOTH] &&3==m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]))){m_nShipPos = RIGHT_BANK;m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] =m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] - 2;m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]=m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] + 2;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::R01(){CRiver oldRiver = *this;if (RIGHT_BANK == m_nShipPos&& m_nChuchmenAndGoth[RIGHT_BANK][GOTH] >= 1&& 0 == (m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] % 3)) {m_nShipPos = LEFT_BANK;m_nChuchmenAndGoth[RIGHT_BANK][GOTH]--;m_nChuchmenAndGoth[LEFT_BANK][GOTH]++;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::R10(){CRiver oldRiver = *this;if (RIGHT_BANK == m_nShipPos&& ((2==m_nChuchmenAndGoth[RIGHT_BANK][GOTH] &&3==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN])|| (1==m_nChuchmenAndGoth[RIGHT_BANK][GOTH] &&1==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]))){m_nShipPos = LEFT_BANK;m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]--;m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]++;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::R11(){CRiver oldRiver = *this;if (RIGHT_BANK == m_nShipPos&& m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] >= 1&& (m_nChuchmenAndGoth[RIGHT_BANK][GOTH] ==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN])){m_nShipPos = LEFT_BANK;m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]--;m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]++;m_nChuchmenAndGoth[RIGHT_BANK][GOTH]--;m_nChuchmenAndGoth[LEFT_BANK][GOTH]++;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::R02(){CRiver oldRiver = *this;if (RIGHT_BANK == m_nShipPos&& m_nChuchmenAndGoth[RIGHT_BANK][GOTH] >= 2&& 0 == (m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] % 3)){m_nShipPos = LEFT_BANK;m_nChuchmenAndGoth[RIGHT_BANK][GOTH] = m_nChuchmenAndGoth[RIGHT_BANK][GOTH] - 2;m_nChuchmenAndGoth[LEFT_BANK][GOTH]= m_nChuchmenAndGoth[LEFT_BANK][GOTH] + 2;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}bool CRiver::R20(){CRiver oldRiver = *this;if (RIGHT_BANK == m_nShipPos&& ((2==m_nChuchmenAndGoth[RIGHT_BANK][GOTH] &&2==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN])|| (1==m_nChuchmenAndGoth[RIGHT_BANK][GOTH] &&3==m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN]))){m_nShipPos = LEFT_BANK;m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] =m_nChuchmenAndGoth[RIGHT_BANK][CHUCHMEN] - 2;m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN]=m_nChuchmenAndGoth[LEFT_BANK][CHUCHMEN] + 2;if (NULL != m_pParent){if (Compare(*m_pParent)&& m_nShipPos == m_pParent->m_nShipPos){*this = oldRiver;return false;}}return true;}return false;}void main(){bool bFinded = false;CRiver * pRiverOpenQueue[1024];int nHeadOpen = 0;int nRearOpen = 0;CRiver * pRiverClosedQueue[1024];int nHeadClosed = 0;int nRearClosed = 0;CRiver * pRiverS[1024];int nNo = -1;CRiver * pRiverCur = NULL;int i = 0;CRiver riverTemp;CRiver riverSg;// 初始化目标结点riverSg.m_nShipPos = CRiver::RIGHT_BANK;riverSg.m_pParent = NULL;for (i=0; i<2; i++){riverSg.m_nChuchmenAndGoth[CRiver::LEFT_BANK][i] = 0;riverSg.m_nChuchmenAndGoth[CRiver::RIGHT_BANK][i] = 3;}// 初始化pRiverSfor (i=0; i<1024; i++){pRiverS[i] = NULL;pRiverOpenQueue[i] = NULL;pRiverClosedQueue[i] = NULL;}// 把S0放入OPEN表pRiverS[++nNo] = new CRiver;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}while (nRearOpen > nHeadOpen) // OPEN表不为空{// 把第一个结点n，从OPEN表中移出，并把它放入CLOSED表中pRiverCur = pRiverOpenQueue[nHeadOpen++];if (nRearClosed < 1024){pRiverClosedQueue[nRearClosed++] = pRiverCur;}// 扩展n，把它的后继结点放入OPEN表的末端，提供回到n的指针riverTemp = *pRiverCur;if (CRiver::LEFT_BANK == riverTemp.m_nShipPos){if (riverTemp.L01()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{// 成功bFinded = true;break;}}if (riverTemp.L10()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{// 成功bFinded = true;break;}}if (riverTemp.L11()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{bFinded = true;break;}}if (riverTemp.L02()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{// 成功bFinded = true;break;}}if (riverTemp.L20()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{bFinded = true;break;}}}else{if (riverTemp.R01()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{// 成功bFinded = true;break;}}if (riverTemp.R10()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{bFinded = true;break;}}if (riverTemp.R11()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{// 成功bFinded = true;break;}}if (riverTemp.R02()){// 成功生成一个后继结点pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{bFinded = true;break;}}if (riverTemp.R20()){pRiverS[++nNo] = new CRiver;*pRiverS[nNo] = riverTemp;pRiverS[nNo]->m_pParent = pRiverCur;if (NULL == pRiverS[nNo]){cout<<"内存不足!"<<endl;exit(1);}if (nRearOpen < 1024){pRiverOpenQueue[nRearOpen++] = pRiverS[nNo];}riverTemp = *pRiverCur;if (pRiverS[nNo]->Compare(riverSg)) // 有后继结点为目标结点{bFinded = true;break;}}}}if (bFinded){CRiver * riverP = NULL;pRiverS[nNo]->m_pNextStep = NULL;riverP = pRiverS[nNo];while (riverP->m_pParent != NULL){(riverP->m_pParent)->m_pNextStep = riverP;riverP = riverP->m_pParent;}cout<<"D052 翁克松："<<endl;while (riverP != NULL){cout<<riverP->m_nChuchmenAndGoth[CRiver::LEFT_BANK][CRiver::CHUCHMEN]<<","; cout<<nShipPos<<")"<<endl;cout<<*riverP<<endl;riverP = riverP->m_pNextStep;}}while (nNo > 0){delete pRiverS[nNo];pRiverS[nNo] = NULL;nNo--;}}四、测试数据和实验结果五、结果分析和实验体会通过本次实验，加深了对图搜索技术的理解，初步掌握了图搜索基本编程方法，并能运用图搜索技术解决一些基本的应用问题。

野人与修道士问题（Missionaries-and-Cannibals Problem ）[修道士与野人问题]：三个野人与三个传教士来到河边，打算乘一只船从右岸渡到左岸去，该船的最大负载能力为两个人。

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

用状态空间法表示修道士与野人问题并设计编写计算机程序求问题的解。

问题分析：从上图可知，修道士、野人和船一共有六种可能，M L 、C L 、B L 、M R 、C R 、B R 。

可以表示为q ＝（M ，C ，B ），其中m 表示修道士的数目（0、1、2、3）、c 表示野人的数目（0、1、2、3）、b 表示船在左岸（1）或右岸（0）。

1、定义状态的描述形式：（m ，c ，b ）2、表示所有可能的状态，并确定初始状态集和目标状态集：s0(3,3,1) s8(1,3,1) s16(3,3,0) s24(1,3,0)s1(3,2,1) s9(1,2,1) s17(3,2,0) s25(1,2,0)s2(3,1,1) s10(1,1,1) s18(3,1,0) s26(1,1,0)s3(3,0,1) s11(1,0,1) s19(3,0,0) s27(1,0,0)s4(2,3,1) s12(0,3,1) s20(2,3,0) s28(0,3,0)s5(2,2,1) s13(0,2,1) s21(2,2,0) s29(0,2,0)s6(2,1,1) s14(0,1,1) s22(2,1,0) s30(0,1,0)s7(2,0,1) s15(0,0,1) s23(2,0,0) s31(0,0,0)初始状态：（3,3,1）目标状态：（0,0,0）3、定义算符：L ij ：把i 个修道士，j 个野人从河的左岸送到右岸R ij ：把i 个修道士，j 个野人从河的右岸送到左岸整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。

问修道士M野 人C 左L 右R题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1牧师、渡1野人1牧师、渡2野人、渡2牧师即：L01或R01，L10或R10，L11或R11，L02或R02，L20或R204、状态空间图：5、设计编写计算机程序求问题的解：算法：在应用状态空间表示和搜索方法时，用（M，C，B）来表示状态描述，其中M和C分别表示在左岸的传教士与野人数。

实验报告一、实验名称：传教士和野人过河二、实验目的：这是经典的过河方案规划问题，通过本实验的设计与编程实现让学生掌握基于状态空间知识表示方法的一般搜索策略。

三、实验内容：设有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 struct Queuenode{node * np；struct Queuenode* next；}Qnode；//队列中节点//定义队列typedef struct Queue{Qnode *front；Qnode *rear；}queue；(三)算法流程1.用起始节点(3，3，1) 初始化tree，初始化open表，closed表。

传教士和野人问题（Missionaries and Cannibals）传教士和野人问题是一个经典的智力游戏问题。

在这个问题中，实际上隐含了这样一个条件：如果在河的某一岸只有野人，而没有传教士，也同样被认为是合法状态。

在具体书写某些条件时，为了简便，这一点有时并没有考虑，但我们默认这个条件是被考虑了的。

有N个传教士和N个野人来到河边准备渡河，河岸有一条船，每次至多可供k人乘渡。

问传教士为了安全起见，应如何规划摆渡方案，使得任何时刻，在河的两岸以及船上的野人数目总是不超过传教士的数目。

即求解传教士和野人从左岸全部摆渡到右岸的过程中，任何时刻满足M（传教士数）≥C （野人数）和M＋C≤k的摆渡方案。

设N＝3，k＝2，则给定的问题可用图1.2表示，图中L和R表示左岸和右岸，B＝1或0分别表示有船或无船。

约束条件是：两岸上M≥C，船上M＋C≤2。

图1.2 M－C问题实例由于传教士和野人数是一个常数，所以知道了一岸的情况，另一岸的情况也就知道了。

因此为了简便起见，在描述问题时，只描述一岸--如左岸--的情况就可以了。

另外，该问题我们最关心的是在摆渡过程中，两岸状态的变化情况，因此船上的情况并不需要直接表达出来。

在一次摆渡过程中，船上究竟有几个传教士和野人，可以通过两个相连的状态简单得到。

这样表达更简练，突出了问题的重点。

（1）综合数据库：用三元组表示左岸的情况，即（，，），其中0≤，≤3，∈{0，1}，其中表示在左岸的传教士人数，表示在左岸的野人数，＝1表示船在左岸，＝0表示船在右岸。

则此时问题描述可以简化为：（3，3，1）→（0，0，0）N＝3的M－C问题，状态空间的总状态数为4×4×2＝32，根据约束条件的要求，可以看出只有20个合法状态。

再进一步分析后，又发现有4个合法状态实际上是不可能达到的。

因此实际的问题空间仅由16个状态构成。

下表列出分析的结果：（）（001）达不到（传教士（）（000）均在右，船在左）（011）（021）（031）（101）不合法（右岸野人多）（111）（121）不合法（左岸野人多）（131）不合法（左岸野人多）（201）不合法（右岸野人多）（211）不合法（右岸野人多）（221）（231）不合法（左岸野人多）（301）达不到（311）（321）（331）（010）（020）（030）达不到（100）不合法（右岸野人多）（110）（120）不合法（左岸野人多）（130）不合法（左岸野人多）（200）不合法（右岸野人多）（210）不合法（右岸野人多）（230）不合法（右岸野人多）（300）（220）（310）（320）（330）达不到规则集可以划分为两组：一组是从左岸到右岸，称为p 操作，另一组是从右岸到左岸，称为q操作。

6．修道士与野人问题这是一个古典问题。

假设有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数（除非修道士个数为0）。

如果两种人都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。

要求：（1）用一个三元组（x1,x2,x3）表示渡河过程中各个状态。

其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。

例如（2,1,1）表示起始岸上有两个修道士，一个野人，小船在起始岸一边。

采用邻接表做为存储结构，将各种状态之间的迁移图保存下来。

（2）采用广度搜索法，得到首先搜索到的边数最少的一条通路。

（3）输出数据若问题有解（能渡过河去），则输出一个最佳方案。

用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态。

若问题无解，则给出“渡河失败”的信息。

（4）求出所有的解。

1．需求分析有n个修道士和n个野人准备渡河，但只有一条能容纳c人的小船，为了防止野人侵犯修道士，要求无论在何处，修道士的个数不得少于野人的人数,否则修道士就会有危险，设计一个算法，确定他们能否渡过河去，若能，则给出一个小船来回次数最少的最佳方案。

用三元组（x1,x2,x3）来表示渡河过程中各个状态，其中，x1表示起始岸上修道士个数，x2表示起始岸上野人个数，x3表示小船位置（0——在目的岸，1——在起始岸）。

若问题有解（能渡过河去），则输出一个最佳方案。

用三元组表示渡河过程中的状态，并用箭头指出这些状态之间的迁移：目的状态←…中间状态←…初始状态，若问题无解，则给出“渡河失败”的信息。

2．设计2.1 设计思想（1）数据结构设计逻辑结构设计: 图型结构存储结构设计: 链式存储结构采用这种数据结构的好处：便于采用广度搜索法，得到首先搜索到的边数最少的一条通路，输出一个最佳方案，采用图的邻接表存储结构搜索效率较高。

数据结构实验报告第七章实验名称：修道士野人问题实验类型：综合性实验班级：学号：姓名：实验日期：2014年5月21日1.问题描述河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制：●修道士和野人都会划船，但船一次只能载C人。

●在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否则修道士将会被野人吃掉。

假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。

2.数据结构设计用一个三元组（num1，num2，an）表示渡河过程中的各个状态。

num1表示左岸上修道士的个数，num2表示左岸上野人的个数，an表示小船位置（0-在右岸上，1-在左岸上）。

定义一个结构体，用于存放各个时刻的状态：typedef struct{int num1;//修道士人数int num2;//野蛮人人数int an;//表示两岸，0在右岸，1在左岸}DataType;用邻接表存储结构实现图的操作，其存储结构为：typedef struct Node{int dest; //邻接表的弧头结点序号struct Node *next;}Edge; //邻接表单链表的结点结构体typedef struct{DataType data; //结点数据元素int sorce; //邻接表的弧尾结点序号Edge *adj; //邻接边的头指针int pre; //指向此点的点的序号}AdjLHeight; //数组的数据元素类型结构体typedef struct{AdjLHeight a[10000]; //邻接表数组int numOfVerts; /结点个数int numOfEdges; //边个数}AdjLGraph; //邻接表结构体3.算法设计一侧的野人数目和修道士数目以及船在哪一岸共同构成一种状态，分析一会发现合法的状态是有限且固定的。

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

二、实验内容设有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）当状态数量不是很大时，画出合理的状态空间图箭头旁边所标的数字表示了Ｐ或Ｑ操作的下标，即分别表示船载的传教士数和野人数。

传教士和野人渡河问题刘宪国050422023野人过河问题描述如下：有三个传教士和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险.一、算法分析先来看看问题的初始状态和目标状态，假设分为甲岸和乙岸：初始状态：甲岸，3野人，3传教士；乙岸，0野人，0传教士；船停在甲岸，船上有0个人；目标状态：甲岸，0野人，0传教士；乙岸，3野人，3传教士；船停在乙岸，船上有0个人；整个问题就抽象成了怎样从初始状态经中间的一系列状态达到目标状态。

问题状态的改变是通过划船渡河来引发的，所以合理的渡河操作就成了通常所说的算符，根据题目要求，可以得出以下5个算符（按照渡船方向的不同，也可以理解为10个算符）：渡1野人、渡1传教士、渡1野人1传教士、渡2野人、渡2传教士。

算符知道以后，剩下的核心问题就是搜索方法了，本文采用深度优先搜索，通过一个FindNext(…)函数找出下一步可以进行的渡河操作中的最优操作，如果没有找到则返回其父节点，看看是否有其它兄弟节点可以扩展，然后用Process(…)函数递规调用FindNext(…)，一级一级的向后扩展。

搜索中采用的一些规则如下：1、渡船优先规则：甲岸一次运走的人越多越好（即甲岸运多人优先），同时野人优先运走；乙岸一次运走的人越少越好（即乙岸运少人优先），同时传教士优先运走；2、不能重复上次渡船操作（通过链表中前一操作比较），避免进入死循环;3、任何时候河两边的野人和传教士数均分别大于等于0且小于等于3；4、由于只是找出最优解，所以当找到某一算符（当前最优先的）满足操作条件后，不再搜索其兄弟节点，而是直接载入链表。

5、若扩展某节点a的时候，没有找到合适的子节点，则从链表中返回节点a的父节点b，从上次已经选择了的算符之后的算符中找最优先的算符继续扩展b。

二、基本数据结构定义如下几个数据结构：typedef struct _riverside{ // 岸边状态类型int wildMan; // 野人数int churchMan; // 传教士数}RIVERSIDE;typedef struct _boat{ // 船的状态类型int wildMan; // 野人数int churchMan; // 传教士数}BOAT;typedef struct _question{ // 整个问题状态RIVERSIDE riverSide1; // 甲岸RIVERSIDE riverSide2; // 乙岸int side; // 船的位置, 甲岸为-1, 乙岸为1 BOAT boat; // 船的状态_question* pPrev; // 指向前一渡船操作_question* pNext; // 指向后一渡船操作}QUESTION;用QUESTION来声明一个最基本的链表。

传教士和野人问题实验报告1.上机内容传教士与野人问题求解（宽度搜索算法）二二问题背景：从前有一条河，河的左岸有 m 个传教士(Missionary)和 m 个野人(Cannibal)，和一艘最多可乘 n 人的小船。

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

三三实验内容：编程，接收 m 和 n，搜索一条可让所有的野人和传教士安全渡到右岸的方案，例如下图: （M 表示传教士(Missionary)，C 表示野人(Cannibal)）初态目标 Left Bank River Right bankLeft Bank River Right bank M....M....C....C....注：本实验的举例均以 3 个传教士和 3 个野人同在左岸作为初始状态。

四四实验方案和算法：1 ．数据结构：本实验需要用到的数据结构主要是队列和堆栈，其实现均包含于 dso.h 头文件中，分别命名为 class stack 和 class queue。

2 2 ．宽度搜索算法：(1) 结点结构：class Move {public:int missionary;//要移动的传教士数量int cannibal;//野人}; class ElemType : Move {//继承 Move 类，获得传教士，野人数据成员。

private:bool boat;//船是否在左岸？public:ElemType_flag;// 标示前一状态即扩展出本结点的父结点信息ElemType(int MA__PEOPLE) {//创建初始状态missionary = cannibal = MA__PEOPLE;boat = true;flag = NULL;} ......在这里，Elemtype 集成了 Move，从而获得 Move 类的传教士和野人数据成员。

以上两个类的数据成员用于保存所有扩展生成的结点。

野人与传教士问题（A*算法）SY0903620 赵磊一、实验题目请用A*算法实现传教士和野人问题问题：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。

该船的负载能力为两人。

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

他们怎样才能用这条船安全地把所有人都渡过河去？算法设计要求给出：状态表示，规则库，启发函数等二、实验目的通过具体问题的编程求解，利用A*算法解决此经典问题，了解人工智能的启发式搜索算法的基本过程与原理。

三、设计思想1、编程工具采用C++语言在Visual Studio 6.0环境下编写；2、整体思想(1)把初始结点So放入OPEN 表中，计算f(So)。

(2)如果OPEN为空，则搜索失败，退出。

(3)把OPEN中的第一个节点(记为节点n)从表中移出放入CLOSED表。

(4)考察节点n是否为目标节点。

若是，则求得问题的解，退出。

(5)若节点n不可扩展，则转第(2)步。

(6)扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送到OPEN表中，然后对OPEN表中的全部节点按估价值从小到大的顺序排列。

3、具体说明用A*算法求解传教士与野人问题。

M=C=5, K=3。

节点估价值设为f(n)=h(n)+g(n)，g(n)设为节点搜索深度，而h(n)= m(n) + c(n) - 2b(n),其中m：河左岸的传教士人数；c：河左岸的野人人数；b：船是否在左岸，1：表示在左岸，0：表示不在左岸。

采用结构体定义形式，定义状态节点*NewNode(int m, int c, int b)，其中包含m左岸传教士人数、c左岸野人人数、b船状态（左或右）。

开始状态为（3，3，1），目标状态为（0，0，0）。

若需要条件满足，即任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉，要对状态结点的安全性进行判断，判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。

传教士-野人问题有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 用状态空间法求解传教士和食人者问题例6-2 传教士和食人者问题（The Missionaries and Cannibals Problem）。