当前位置：文档之家 › 人工智能实验 传教士野人

人工智能实验 传教士野人

  • 格式：pdf
  • 大小：128.45 KB
  • 文档页数：9

下载文档原格式

  / 9

合集下载

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

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

人工智能实验报告班级：计研-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<<"传教士与野人过河问题。

人工智能：野人与修道士问题

人工智能：野人与修道士问题

野人与修道士问题（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分别表示在左岸的传教士与野人数。

传教士(牧师)与野人问题-模拟人工智能实验_CSDN博客_传教士与野人问题

传教士(牧师)与野人问题-模拟人工智能实验_CSDN博客_传教士与野人问题

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

人工智能课后答案32

人工智能课后答案32

人工智能课后答案321、对N＝5、k≤3时，求解传教士与野人问题的产生式系统各构成部分进行描述（给出综合数据库、规则集合的形式化描述，给出初始状态与目标条件的描述），并画出状态空间图。

2、对量水问题给出产生式系统描述，并画出状态空间图。

有两个无刻度标志的水壶，分别可装5升与2升的水。

设另有一水缸，可用来向水壶灌水或者倒出水，两个水壶之间，水也能够相互倾灌。

已知5升壶为满壶，2升壶为空壶，问如何通过倒水或者灌水操作，使能在2升的壶中量出一升的水来。

3、对梵塔问题给出产生式系统描述，并讨论N为任意时状态空间的规模。

相传古代某处一庙宇中，有三根立柱，柱子上可套放直径不等的N个圆盘，开始时所有圆盘都放在第一根柱子上，且小盘处在大盘之上，即从下向上直径是递减的。

与尚们的任务是把所有圆盘一次一个地搬到另一个柱子上去（不许暂搁地上等），且小盘只许在大盘之上。

问与尚们如何搬法最后能完成将所有的盘子都移到第三根柱子上（其余两根柱子，有一根可作过渡盘子使用）。

求N＝2时，求解该问题的产生式系统描述，给出其状态空间图。

讨论N为任意时，状态空间的规模。

4、对猴子摘香蕉问题，给出产生式系统描述。

一个房间里，天花板上挂有一串香蕉，有一只猴子可在房间里任意活动（到处走动，推移箱子，攀登箱子等）。

设房间里还有一只可被猴子移动的箱子，且猴子登上箱子时才能摘到香蕉，问猴子在某一状态下（设猴子位置为a，箱子位置为b，香蕉位置为c），如何行动可摘取到香蕉。

5、对三枚钱币问题给出产生式系统描述及状态空间图。

设有三枚钱币，其排列处在"正、正、反"状态，现同意每次可翻动其中任意一个钱币，问只许操作三次的情况下，如何翻动钱币使其变成"正、正、正"或者"反、反、反"状态。

6、说明如何才能用一个产生式系统把十进制数转换为二进制数，并通过转换141.125这个数为二进制数，阐明其运行过程。

人工智能的野人与传教士

人工智能的野人与传教士

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

要求：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--;}}四、测试数据和实验结果五、结果分析和实验体会通过本次实验，加深了对图搜索技术的理解，初步掌握了图搜索基本编程方法，并能运用图搜索技术解决一些基本的应用问题。

传教士野人问题

传教士野人问题

问题：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下：有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？解答一：一、算法分析先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，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。

二、基本数据结构仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。

传教士野人问题

问题：野人过河问题属于人工智能学科中的一个经典问题，问题描述如下：有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？解答一：一、算法分析先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，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。

二、基本数据结构仔细阅读问题，可以发现有些基本东西我们必须把握，例如：每时刻河两岸野人牧师各自的数目、船的状态、整个问题状态。

人工智能实验指导

人工智能实验指导实验一传教士和野人渡河问题目的：利用已经学习的某种搜索算法，编写状态空间搜索程序内容：使用某个编程工具编写解决问题的程序要求：程序必须把状态空间的搜索路径输出算法参考：1, OPEN:=(s), f(s):=g(s)+h(s);2, LOOP: IF OPEN=( ) THEN EXIT(FAIL);3, n:=FIRST(OPEN);4, IF GOAL(n) THEN EXIT(SUCCESS);5, REMOVE(n, OPEN), ADD(n, CLOSED);6, EXPAND(n) →{m i},计算f(n, m i):=g(n, m i)+h(m i);ADD(m j, OPEN), 标记m j到n的指针；IF f(n, m k)<f(m k) THEN f(m k):=f(n, m k),标记m k到n的指针；IF f(n, m l)<f(m l) THEN f(m l):=f(n, m l),标记m l到n的指针,ADD(m l, OPEN);7, OPEN中的节点按f值从小到大排序；8, GO LOOP；实验二逻辑关系模拟程序目的：在PIE中体会Prolog语言的推理，熟悉SWI-Prolog或Visual Prolog编程工具。

内容：在Visual Prolog自带的实例PIE中调试运行简单的逻辑关系推理程序。

要求：程序自选，但必须是描述某种逻辑关系的程序。

示例程序：(1)在PIE代码窗口输入以下事实和规则：not_(1,0).not_(0,1).and_(0,0,0).and_(0,1,0).and_(1,0,0).and_(1,1,1).or_(0,0,0).or_(0,1,1).or_(1,0,1).or_(1,1,1).xor(Input1,Inuput2,Output):-not_(Input1,N1),not_(Input2,N2),and_(Input1,N2,N3),and_(Input2,N1,N4),or_(N3,N4,Output).(2)在Dialog窗口中输入类似于”xor(1,0,X).”这样的目标语句让PIE求解,观察求解的结果是否正确。

传教士和野人过河

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

三、实验内容：设有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表。

传教士与野人

实验题目：产生式设计——野人与传教士过河问题专业班级：计算机11-2 学生姓名. 吴璨No. 1137074实验目的：1．掌握人工智能的基础思想2．熟练应用程序实现人工智能3．强化实践能力产生式设计：1．实验语言环境：c语言2．数据结构：typedef struct{int m; //传教士在左岸的实际人数int c; //野人在左岸的实际人数int wz; //为1时船在左岸int sm; //船上传教士的实际人数int sc; //船上野人是实际人数}Baidu;3.算法设计（以一组较小数据为例，假设N=3，K=2）（1）设定状态变量及确定值域。

左岸的传教士数为m，则有m={0，1，2，3}；对应右岸的传教士数为3—m；左岸的野人数为c，则有c={0，1，2，3}；对应右岸野人数为3—c；左岸船数为b，故又有b={0，1}；对应右岸的船数为1-b。

（2）确定状态组，分别列出初始状态集和目标状态集。

问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即右岸的状态可以不必标出。

S k=（m, c, b）初始状态只有一个：S=（3，3，1），初始状态表示全部成员在河的的左岸；目标状态也只有一个：S=（0，0，0），表示全部成员从河的左岸全部渡河完毕。

（3）定义并确定操作集。

以河的左岸为基点来考虑，把船从左岸划向右岸定义为L(Sm,Sc)操作。

其中，第一下标Sm表示船载的传教士数，第二下标Sc表示船载的野人数；同理，从右岸将船划回左岸称之为R(Sm,Sc)操作，下标的定义同前。

（4）估计全部的状态空间数，并尽可能列出全部的状态空间。

在这个问题世界中，S={3，3，1}为初始状态，S=（0，0，0）为目标状态。

全部的可能状态共有32个，如表所示。

值得注意的是按照题目规定的条件，我们应该划去不合法的状态。

例如，首先可以划去岸边野人数目超过传教士的情况，即Ｓ4、S8、S9、S20、S24、S25等6种状态是不合法的；其次，应该划去右岸边野人数目超过野人的情况，即S6、S7、S11、S22、S23、S27等情况；余下20种合法状态中，又有4种是不可能出现的状态；S15和S16不可能出现，因为船不可能停靠在无人的岸边；S3不可能出现，因为传教士不可能在数量占优势的野人眼皮底下把船安全地划回来；还应该划去S28，因为传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
return (pLift->m == pLift->c); }
void PrintLift(struct Lift *pLift) {
int rm=3-(pLift->m), rc=3-(pLift->c); printf("(%d, %d, %d) (%d, %d)\n", pLift->m, pLift->c, pLift->b,rm, rc); }
四、实验描述及要求：
（1） 设计该问题的状态。例如：((左岸牧师数，左岸野人数),(右岸牧师数，右岸野人 数),船的位置)。
（2） 定义目标状态。这里是：((0,0),(3,3),1) （3） 描述可能的动作。船上所能够载人的状态就是可能的操作。用谓词 move/2 表示。 （4） 判断合法状态 （5） 深度优先搜索
struct BOAT *CopyBoat(struct BOAT *pBoat) {
return NewBoat(pBoat->m, pBoat->c); }
struct Lift *In(struct Lift *pLift, struct Lift *pList) {
if (pList == NULL) return NULL; if (Equal(pLift, pList)) return pList; return In(pLift, pList->pNext); }
if (!Safe(pRData)) free(pRData);
{ continue;
}
pRDataList = ConsLift(pRData, pDataList); pPath = Backtrack1(pRDataList, bound);
if (pPath == FAIL) {
free(pRData); }
人工智能实验报告
题目：求解传教士和野人问题 姓名： 班级： 学号： 学院：计算机科学与信息 专业：计算机科学与技术 指导教师：
日期：2011 年 12 月 6 日
一、实验目的：
复习经典谓词演算中的归结原理，掌握人工智能程序设计语言 Prolog，理解通过搜索求 解问题实现人工智能的思想。
二、实验原理：
pData = pDataList; if (In(pData, pDataList->pNext)) {
return FAIL; } if (IsGoal(pData)) {
FreeLiftList(pDataList); return NULL; } if (!Safe(pData)) { return FAIL; } if (Length(pDataList) > bound) { return FAIL; }
else return 0;
}
int Safe(struct Lift *pLift) {
if (pLift->m < 0 || pLift->c < 0 || pLift->m > M || pLift->c > C || pLift->c > M) return 0;
if (pLift->m == M || pLift->m == 0) return 1;
void FreeLiftList(struct Lift *pLiftList) {
struct Lift *pLift = NULL; while (pLiftList) {
pLift = pLiftList; pLiftList = pLiftList->pNext; free(pLift); } }
continue;
pBoat = CopyBoat(pBoat); if (pBoat == NULL) return FAIL; return ConsBoat(pBoat, pPath); } return FAIL; }
void main(void) {
struct Lift *pData = NULL; struct BOAT *pPath = NULL; g_pBoatSet = InitBoats(); cout<<"3个?传ä?教¨¬士º?和¨ª3个?野°¡ã人¨?过y河¨®问¨º题¬a的Ì?答äe案ã?为a：êo\n 左Á¨®岸ã? 右®¨°岸ã?"<<endl; pData = NewLift(3, 3, 1); pPath = Backtrack1(pData, 20);
if (pLift1->m == pLift2->m && pLift1->c == pLift2->c && pLift1->b == pLift2->b) return 1;
else return 0;
}
struct Lift *NewLift(int m, int c, int b) {
struct Lift *pLift = NULL; pLift = (Lift*)malloc(sizeof(struct Lift)); if (pLift == NULL) return NULL; pLift->m = m; pLift->c = c; pLift->b = b; pLift->pNext = NULL; return pLift; }
PrintBoatList(pPath);
if (pPath == FAIL) {
free(pData); } FreeBoatList(pPath); FreeBoatList(g_pBoatSet); }
}
int Length(struct Lift *pList) {
if (pList == NULL) return 0; return Length(pList->pNext) + 1; }
struct Lift *ConsLift(struct Lift *pLift, struct Lift *pList) {
五、实验结果：
六：实验代码
#include "stdafx.h"
#include <cstdio> #include <cstdlib> #include <iostream> using namespace std;
#define #define #define #define
FAIL ((struct BOAT *)-1) M3 C3 K2
pLift->pNext = pList; return pLift; }
struct BOAT *ConsBoat(struct BOAT *pBoat, struct BOAT *pList) {
pBoat->pNext = pList; return pBoat; }
struct Lift *Gen(struct BOAT *pBoat, struct Lift *pData) {
if (pBoat == NULL) return NULL;
pBoat->pNext = pBoats;
pBoats = pBoat;
}
}
}
return pBoats;
}
int IsGoal(struct Lift *pLift) {
if (pLift->m == 0 && pLift->c == 0 && pLift->b == 0) return 1;
struct BOAT *NewBoat(int m, int c) {
struct BOAT *pBoat = NULL; pBoat = (BOAT*)malloc(sizeof(struct BOAT));
if (pBoat == NULL) return NULL; pBoat->m = m; pBoat->c = c; pBoat->pNext = NULL; return pBoat; }
struct Lift {
int m; int c;
int b; struct Lift *pNext;
};
struct BOAT {
int m; int c; struct BOAT *pNext; };
struct BOAT *g_pBoatSet = NULL;
int Equal(struct Lift *pLift1, struct Lift *pLift2) {
谓词演算中的消解法。
三、实验内容：
设有 3 个传教士和 3 个野人同在河的左岸，他们都要到对岸去；河里只有一条船，他们 都会划船，但每次渡船至多只能乘两人；如果在任何一边河岸上，野人的数量超过传教士， 野人就要吃掉传教士，问怎样才能用船将 3 个传教士和 3 个野人从左岸都渡到右岸，又不会 发生传教士被吃的事件呢？通过 Prolog 程序，给出乘船过河的动作序列。
if (pData->b == 1) {
return NewLift(pData->m - pBoat->m, pData->c - pBoatLeabharlann >c, 0); } else {
return NewLift(pData->m + pBoat->m, pData->c + pBoat->c, 1); } }
struct BOAT *InitBoats(void) {
struct BOAT *pBoats = NULL, *pBoat = NULL; int i, j;
for (i = 0; i <= 2; i++)