C 实现传教士与野人过河问题实验报告
传教士与野人过河问题实验报告
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
#include
#include
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
{
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 | 左岸->右岸");
else
operation.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 | 左岸->右岸");
else
operation.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 | 左岸->右岸");
else
operation.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 | 左岸->右岸");
else
operation.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 | 左岸->右岸");
else
operation.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
vector
//初始化左岸参数，可以认为是从右岸移动至左岸的操作
//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所示的四种过河方式。
图 2 过河方式1、2
图 3 过河方式3、4
人工智能实验一指导
实验1: Prolog语言程序设计 人工智能（AI）语言是一类适应于人工智能和知识工程领域的、具有符号处理和逻辑推理能力的计算机程序设计语言。能够用它来编写求解非数值计算、知识处理、推理、规划、决策等具有智能的各种复杂问题。 Prolog是当代最有影响的人工智能语言之一，由于该语言很适合表达人的思维和推理规则，在自然语言理解、机器定理证明、专家系统等方面得到了广泛的应用，已经成为人工智能应用领域的强有力的开发语言。 尽管Prolog语言有许多版本，但它们的核心部分都是一样的。Prolog的基本语句仅有三种，即事实、规则和目标三种类型的语句，且都用谓词表示，因而程序逻辑性强，方法简捷，清晰易懂。另一方面，Prolog是陈述性语言，一旦给它提交必要的事实和规则之后，Prolog就使用内部的演绎推理机制自动求解程序给定的目标，而不需要在程序中列出详细的求解步骤。 一、实验目的 1、加深学生对逻辑程序运行机理的理解。 2、掌握Prolog语言的特点、熟悉其编程环境。 3、为今后人工智能程序设计做好准备。 二、实验内容 1、编写一个描述亲属关系的Prolog程序，然后再给予出一些事实数据，建立一个小型演绎数据库。 提示：可以以父亲和母亲为基本关系（作为基本谓词），再由此来描述祖父、祖母、兄弟、姐妹以及其他所属关系。 2、编写一个路径查询程序，使其能输出图中所有路径。 提示：程序中的事实描述了下面的有向图，规则是图中两节点间通路的定义。 e
3、一个雇主在发出招聘广告之后，收到了大量的应聘申请。为了从中筛选出不量的候选人，该雇主采用下列判据：申请者必须会打字、开车，并且住在伦敦。 （a）用Prolog规则表述这个雇主的选择准则。 （b）用Prolog事实描述下列申请者的情况： 史密斯住在剑桥，会开车但不会打字。 布朗住在伦敦，会开车也会打字。 简住在格拉斯哥，不会开车但会打字。 埃文斯住在伦敦，会开车也会打字。 格林住在卢顿，会开车也会打字。 （c）要求Prolog提供一个候选人名单。 4、实现递归谓词remove(X,Y,Z),它用于从表Y中除去所有整型数X的倍数值后得到新表Z。例如，对于询问 remove(2,[3,4,5,6,7,8,9,10],Z). 的回答为： Z=[3,5,7,9] 三、实验建议 1、首先运行Prolog安装目录中PROGRAM目录下的示例程序，对Prolog功能有一个感性认识。 （1）HANOI．PRO 实现汉诺塔演示的程序。 程序运行界面如图所示。
传教士野人过河问题-两种解法思路
实验 传教士野人过河问题 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 R M 3 0 M 0 3 C 3 0 C 0 3 B 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 )
商人过河实验报告
数学模型实验—实验报告6 学院：工商学院专业：电气二类（计算机）姓名：辛文辉尚磊张亨 学号：___ 2012484019 2012484091 2012484055 ____ 实验时间：__ 3.18 ____ 实验地点：b3 一、实验项目： Matlab程序设计 安全渡河问题可以看成一个多步决策过程。每一步，即船由此岸驶向彼岸或从彼岸驶回此岸，都要对船上的人员(商人随从各几人)作出决策，在保证安全的前提下(两岸的商人数都不比随从数少)，在有限步内使人员全部过河。用状态(变量)表示某一岸的人员状况，决策(变量)表示船上的人员状况，可以找出状态随决策变化的规律。问题转化为在状态的允许变化范围内(即安全渡河条件)，确定每一步的决策，达到渡河的目的。 此类智力问题经过思考，可以拼凑出一个可行方案。但是，我们现在希望能找到求解这类问题的规律性，并建立数学模型，用以解决更为广泛的问题。 二、实验目的和要求 a.了解Matlab程序设计有关基本操作 b.掌握有关程序结构 三、实验内容
允许的状态向量 0 0 0 1 0 2 0 3 0 4 0 5 0 6 0 7 0 8 0 9 0 10 0 11 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 11 0 11 1 11 2
11 3 11 4 11 5 11 6 11 7 11 8 11 9 11 10 允许的决策向量: 0 1 0 2 0 3 0 4 0 5 0 6 1 0 1 1 2 0 2 1 2 2 3 0 3 1 3 2 3 3 4 0 4 1 4 2 5 0 5 1 6 0 过河步骤： 第1步：0商5仆过河，0商1仆返回 第2步：5商1仆过河，1商1仆返回 第3步：3商3仆过河，1商1仆返回 第4步：3商3仆过河，1商1仆返回 第5步：3商3仆过河，完成 过河过程中状态变化： 步骤此岸商此岸仆方向彼岸商彼岸仆 1 11 6 ==> -8 -3
农夫过河数据结构
郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限：2012/6/21 指导教师签名： 课程负责人签名： 年月日
郑州轻工业学院 本科 数据结构课程设计总结报告 设计题目：农夫过河 学生姓名： 系别：计算机与通信工程学院 专业：计算机科学与技术 班级：计算机科学与技术 学号： 指导教师： 2012年6 月21 日
一，设计题目 问题描述： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二，运行环境（软、硬件环境） VC6.0 Windows7系统 三，算法设计的思想 对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径，这样做只能搜到一种合理方法，因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四，算法的流程图 要写算法的流程图，必须要先很了解自己的函数结构，我先在纸上手动的把整个过程在纸上画一遍，了解它的大体流程，然后把各个函数给分开，下面是我自己根据我的代码中画的各个函数画的流程图，希望老师满意。 主函数的流程图：
修道士与野人问题
实验课名称：数据结构实验五 实验名称：修道士与野人问题 班级：20130612 学号：2013061213 姓名：李寅龙时间：2015-6-8 1.问题描述 河的左岸有N个野人和N个修道士以及一条小船，修道士们想用这条小船把所有的人都运到河的右岸，但又受到以下限制： ●修道士和野人都会划船，但船一次只能载C人。 ●在任何岸边，为了防止野人侵犯修道士，野人数不能超过修道士数，否 则修道士将会被野人吃掉。 假定野人愿意服从任何一种过河的安排，本设计的主要任务是规划出一种确保修道士安全的过河方案。 ②设计要求 ●设计表示野人、修道士、船的位置信息等数据的逻辑结构和存储结构。 ●从键盘输入修道士与野人的人数N和船可容纳的人数C。 ●设计检测某一时刻两岸修道士是否安全的算法。 ●输出安全过河的详细路径。 界面友好，操作简单。 2.数据结构设计 （1）采用图的邻接表存储结构搜索。 typedef struct { int xds; //修道士个数 int yr; //野人个数 int cw; //船的位置 }DataType; typedef struct node//结构体定义 { DataType data;
struct node *son;//儿子 struct node *bro;//兄弟 struct node *par;//双亲 struct node *next; }Link; 3.算法设计 （1）对所有的可能渡河情况进行安全检测，，以减去修道士少于野人的情况： int safe(DataType x,int n) { if ((x.xds>=x.yr||x.xds==0)&&((n-x.xds)>=(n-x.yr) ||x.xds==n)&&x.xds>=0&&x.xds<=n&&x.yr>=0&&x.yr<=n) return 1; else return 0; } （2）用广度搜索法搜索边数最少的一条通路： void guangdu(Link *p,int n,int c) { Link *q,*t; DataType tem; int i,flag1,flag2,g=0,j,count=0; q=p->son; while (q!=NULL)/ { flag1=0; j=boatcase(q->data,c); for (i=0;i
人工智能实验报告
计算机科学与技术1341901301 陈敏 实验一：知识表示方法 一、实验目的 状态空间表示法是人工智能领域最基本的知识表示方法之一，也是进一步学习状态空间搜索策略的基础，本实验通过牧师与野人渡河的问题，强化学生对知识表示的了解和应用，为人工智能后续环节的课程奠定基础。 二、问题描述 有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。 三、基本要求 输入：牧师人数(即野人人数)：n；小船一次最多载人量：c。 输出：若问题无解，则显示Failed，否则，显示Successed输出一组最佳方案。用三元 组(X 1, X 2 , X 3 )表示渡河过程中的状态。并用箭头连接相邻状态以表示迁移过程：初始状态-> 中间状态->目标状态。 例：当输入n=2，c=2时，输出：221->110->211->010->021->000 其中：X 1表示起始岸上的牧师人数；X 2 表示起始岸上的野人人数；X 3 表示小船现在位置(1表 示起始岸，0表示目的岸)。 要求：写出算法的设计思想和源程序，并以图形用户界面实现人机交互，进行输入和输出结果，如： Please input n: 2 Please input c: 2 Successed or Failed?: Successed Optimal Procedure: 221->110->211->010->021->000 四、算法描述
MC牧师过河问题
人工智能上机实验报告 学号：姓名：所在系：信息学院班级： 实验名称：实验日期2016年12月3日 实验指导教师实验机房A401 ------------------------------------------------------------------------------------------------------ 1.实验目的： (1)在掌握状态空间搜索策略的基础上，理解知识表示的方法。 (2)能够应用知识表示方法，解决实际问题 2. 实验内容： (1)M-C问题描述 有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。 3．算法设计（编程思路或流程图或源代码） #include
农夫过河问题状态图及程序
农夫过河问题状态图及程序 一、问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？ 二、算法选择 求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。 广度优先： u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。u 要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中，
然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。 u 由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。 三、算法的精化 要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。 四、算法的实现 完成了上面的准备工作，现在的问题变成： 从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。
农夫过河实验报告――数据结构
数据结构实验报告 ——实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 一、【问题描述】 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。 二、【数据结构设计】 求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。 现在问题变成：从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。 实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步
传教士和野人问题
状态空间法详解传教士和野人问题 传教士和野人问题（The Missionaries and Cannibals Problem） 在河的左岸有三个传教士、一条船和三个野人，传教士们想用这条船将所有的成员都运过河去，但是受到以下条件的限制： ①教士和野人都会划船，但船一次最多只能装运两个； ②②在任何岸边野人数目都不得超过传教士，否则传教士就会遭遇危险：被野人攻击甚至被吃掉。 此外，假定野人会服从任何一种过河安排，试规划出一个确保全部成员安全过河的计划。（1）设定状态变量及确定值域。 为了建立这个问题的状态空间，设左岸传教士数为m，则 m ={0,1,2,3}； 对应右岸的传教士数为3－m；左岸的野人数为c，则有 c ={0,1,2,3}； 对应右岸野人数为3－c；左岸船数为b，故又有b={0,1}，右岸的船数为1－b. （2）确定状态组，分别列出初始状态集和目标状态集。 问题的状态可以用一个三元数组来描述，以左岸的状态来标记，即 Sk =（m,c,b）， 右岸的状态可以不必标出。 初始状态一个：S0 =（3,3,1），初始状态表示全部成员在河的左岸； 目标状态也只一个：Sg =（0,0,0），表示全部成员从河左岸渡河完毕。 （3）定义并确定操作集。 仍然以河的左岸为基点来考虑，把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数, 第二下标j表示船载的野人数；同理，从右岸将船划回左岸称之为Qij 操作，下标的定义同前。则共有10种操作，操作集为
F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20} （4）估计全部的状态空间数，并尽可能列出全部的状态空间或予以描述之。 在这个问题世界中，S0 =（3,3,1）为初始状态，S31 = Sg =（0,0,0）为目标状态。全部的可能状态共有32个，如表所示。 表1 传教士和野人问题的全部可能状态 注意：按题目规定条件，应划去非法状态，从而加快搜索效率。 1）首先可以划去左岸边野人数目超过传教士的情况，即S4、S8、S9、S20、S24、S25等6种状态是不合法的； 2）应划去右岸边野人数目超过修道士的情况，即S6、S7、S11、S22、S23、S27等情况； 3）应划去4种不可能出现状态：划去S15和S16——船不可能停靠在无人的岸边；划去S3——传教士不可能在数量占优势的野人眼皮底下把船安全地划回来；划去S28——传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。可见，在状态空间中，真正符合题目规定条件的只有16个合理状态。 （5）当状态数量不是很大时，按问题的有序元组画出状态空间图，依照状态空间图搜索求解。
数学模型实验商人过河
《数学模型实验》实验报告 姓名：王佳蕾学院：数学与信息科 学学院 地点：主楼402 学号：055专业：数学类时间：2017年4 月16日 实验名称： 商人和仆人安全渡河问题的matlab实现 实验目的： 1.熟悉matlab基础知识，初步了解matlab程序设计； 2.研究多步决策过程的程序设计方法； 3.（允许）状态集合、（允许）决策集合以及状态转移公式的matlab表示；实验任务： 只有一艘船，三个商人三个仆人过河，每一次船仅且能坐1-2个人，而且任何一边河岸上仆人比商人多的时候，仆人会杀人越货。怎么在保证商人安全的情况下，六个人都到河对岸去，建模并matlab实现。 要求：代码运行流畅，结果正确，为关键语句加详细注释。 实验步骤： 1.模型构成 2.求决策 3.设计程序 4.得出结论（最佳解决方案） 实验内容： （一）构造模型并求决策
设第k次渡河前此岸的商人数为xk，随从数为yk，k=1,2,...，xk，yk=0,1,2,3.将二维向量sk=（xk，yk）定义为状态，安全渡河条件下的状态集合称为允许状态集合，记作S，S 对此岸和彼岸都是安全的。 S={(x,y)|x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2} 设第k次渡船上的商人数为uk，随从数vk，将二维变量dk=（uk，vk）定义为决策，允许决策集合记为D,由小船的容量可知， D={(u,v)|1<=u+v<=2,u,v=0,1,2} k为奇数时，船从此岸驶向彼岸，k为偶数时，船从彼岸驶向此岸，状态sk随决策变量dk的变化规律为sk+1=sk+(-1)^k*dk（状态转移律） 这样制定安全渡河方案归结为如下的多步决策模型： 求决策dk∈D(k=1,2,...,n)，使状态sk∈S，按照转移律，由初始状态s1=（3,3）经有限步n到达状态sn+1=（0,0）。 （二）程序设计
AStar算法解决野人渡河问题
江南大学物联网工程学院实验报告 课程名称人工智能实验名称A*算法解决8数码问题实验日期2018.3.20 班级计科1501 姓名周启航学号1030415127 一、实验目的： 问题描述：设有3个传教士和3个野人来到河边，打算乘一只船从左岸渡到右岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡河过去？试采用A*算法编一程序实现这一搜索过程。 二、算法描述： 1.状态描述 以河岸左边传教士的数目M，野人的数目C，船是否在B作为一个三元组作为一个状态即（M，C，B）。 2.启发函数设计 以现在的状态到目的状态所需的最少步数作为启发函数，即为h()=M+C-2*B。 3.规则的判断条件 岸边传教士不能少于野人个数，即M>=C,或者M=0，船在左岸时B=1。 4.算法流程图 5.核心代码
操作算子： void Astar() { while(!Q.empty()) Q.pop(); PathNode.clear(); memset(st, -1, sizeof(st)); PathNode.push_back(Node(M, C, B, 0, -1)); Q.push(AstarNode(0, PathNode[0])); st[M][C][B] = 0; int m, c, b, flag, id; while(!Q.empty()) { AstarNode as = Q.top(); Q.pop(); //printf("----%d %d %d %d %d----\n", as.f, as.g, as.node.m, as.node.c, as.node.b); if(as.node.m == 0 && as.node.c == 0) { printf("渡河方案如下：\n"); printf(" (M, C, B)\n"); printPath(as.node.id); printf("可以安全渡河，来回最少需%d 次便可!\n", as.g); Safe = true; return; } if(as.node.b == 1) flag = -1; else flag = 1; b = 1 - as.node.b; id = PathNode.size() - 1; for(int i = 0; i < 5; ++i) { m = as.node.m + flag * add[i][0]; c = as.node.c + flag * add[i][1]; if(OK(m, c, b)) { ++id; st[m][c][b] = as.g + 1; PathNode.push_back(Node(m, c, b, id, as.node.id)); Q.push(AstarNode(as.g + 1, PathNode[id])); } } } } 主函数： int main(int argc, char *argv[]) { int i=3;
农夫过河实验报告
“数据结构与算法综合实验”课程设计报告题目：农夫过河问题 学院计算机科学技术 年级2014级 专业计算机科学与技术 学号20142060 姓名高晗 日期2016年3月30日星期三 成绩 评语 黑龙江大学 计算机科学技术学院、软件学院
《数据结构与算法综合实验》报告 1.系统概述 （1）一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。 （2）为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。 （3）掌握顺序表和队列的逻辑结构和存储结构。 2.系统需求分析 (1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。 (2)题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到，不接受非法输入。 (3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。 (4)实验运行环境为VC++6.0. 3.系统概要设计 (1)数据结构设计 要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。则问题的初
有N个传教士和N个野人来到河边渡河
有N个传教士和N个野人来到河边渡河,河岸有一条船,每次至多可供k人乘渡。问传教士为了安全起见,应如何规划摆渡方案,使得任何时刻,河两岸以及船上的野人数目总是不超过传教士的数目(否则不安全,传教士有可能被野人吃掉)。即求解传教士和野人从左岸全部摆渡到右岸的过程中,任何时刻满足M(传教士数)≥C(野人数)和M+C≤k的摆渡方案。 我们此处举例,只讨论N为3、k为2的乘渡问题,这样传教士和野人问题的描述就具体为如下: 三个传教士与三个野人来到河边,有一条船可供一人或两人乘渡,问题是如何用这条船渡河才能使得河的任一岸上野人的数目总不超过传教士的数目(当然,如果某一岸上只有野人而没有传教士是允许的)? 我们用一个三元组(m c b)来表示河岸上的状态,其中m、c分别代表某一岸上传教士与野人的数目,b=1表示船在这一岸,b=0则表示船不在。 设N=3,k=2,则给定的问题可用下图表示,图中L和R表示左岸和右岸,B=1或0分别表示有船或无船。约束条件是:两岸上M≥C,船上M+C≤2。 我们采用产生式系统来解决这一问题。由于传教士与野人的总数目是一常数,所以只要表示出河的某一岸上的情况就可以了,为方便起见,我们选择传教士与野人开始所在的岸为所要表示的岸,并称其为左岸,另一岸称为右岸。但显然仅用描述左岸的三元组描述就足以表示出整个情况,因此必须十分重视选择较好的问题表示法。以后的讨论还可以看到高效率的问题求解过程与控制策略有关,合适的控制策略可缩小状态空间的搜索范围,提高求解的效率。因而问题的初始状态是(331),目标状态是(000)。 (1)综合数据库:用三元组表示,即(ML,CL,BL),其中0≤ML,CL≤3,BL∈{0,1} 此时问题述简化为(3,3,1)®(0,0,0) N=3的M-C问题,状态空间的总状态数为4×4×2=32,根据约束条件的要求,可以看出只有20个合法状态。再进一步分析后,又发现有4个合法状态实际上是不可能达到的。因此实际的问题空间仅由16个状态构成。下表列出分析的结果: (ML,CL,BL)(ML,CL,BL) (001)达不到(000) (011)(010) (021)(020) (031)(030)达不到 (101)不合法(100)不合法 (111)(110) (121)不合法(120)不合法 (131)不合法(130)不合法 (201)不合法(200)不合法 (211)不合法(210)不合法 (221)(220) (231)不合法(230)不合法 (301)达不到(300) (311)(310) (321)(320) (331)(330)达不到 (2)规则集合:由摆渡操作组成。该问题主要有两种操作:pmc操作(规定为从左岸划向右岸)和qmc操作(从右岸划向左岸)。每次摆渡操作,船上人数有五种组合,因而组成有10条规则的集合。下面定义的规则前5条为pmc操作(从左岸划向右岸),后5条为qmc操作(从右岸划向左岸)。 if(ML,CL,BL=1)then(ML-1,CL,BL-1);(p10操作) if(ML,CL,BL=1)then(ML,CL-1,BL-1);(p01操作) if(ML,CL,BL=1)then(ML-1,CL-1,BL-1);(p11操作)
LAB05+队列的操作及应用
Lab05．队列的操作及应用 【实验目的和要求】 1．掌握队列的顺序表示和链表表示下的基本操作； 2．深入理解深度优先搜索和广度优先搜索的思想并能正确描述其算法； 3．会应用广度优先搜索算法解决较复杂的问题。 【实验内容】 1．编写一个C源程序，其中包含顺序表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。 2．编写一个C源程序，其中包含链表表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。 3. 简述深度优先搜索和广度优先搜索的思想，并给出具体的算法步骤。 4．应用广度优先搜索算法求解农夫过河问题。 【实验仪器与软件】 1．CPU主频在1GHz以上，内存在512Mb以上的PC； 2．VC6.0，Word 2003及以上版本。 实验讲评： 实验成绩： 评阅教师： 2012 年月日
Lab05．队列的操作及应用 一、顺序表示的队列基本操作 1．顺序表示的队列操作基本源程序 #include
C实现传教士与野人过河问题实验报告
C实现传教士与野人过河问题实验报告 Document serial number【LGGKGB-LGG98YT-LGGT8CB-LGUT-
传教士与野人过河问题实验报告 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;ildL == &&lastParameters[i].churchL == { if == lastParameters[i].boat) return 0; } } //检验人数数据合法性 if < 0 || < 0 || < 0 || < 0) return 0; //传教士是否被吃
研究性学习实验报告
研究性学习实验报告 课题名称：有关全息投影的研究 班级：1403班 小组组长：郭嘉昕 小组成员：郭京伟段泽华王捷聪孙泽錡 日期：2015年3月
有关全息投影的实验报告
第一部分 有关实验选材的研究 一、实验设计思想 （1）实验目的 通过对比，研究不同材料对于光线的折射和漫反射的效果，并且在其中寻找效果最佳、性价比高的材料，进行下一步实验。 （2）实验原理 当一束平行的入射光线射到粗糙的表面时，表面会把光线向着四面八方反射，所以入射线虽然互相平行，由于各点的法线方向不一致，造成反射光线向不同的方向无规则地反射，这种反射称之为“漫反射”。 （3）实验方法 从成本方面考虑，先将不同材料做成面积的板状模型和立方体状模型，再将我们的光源设备调节到最高亮度，以最佳效果的角度将画面投射到不同的材料上。在同样暗度的房间里，用高度、距离固定的摄影机进行拍摄，再将不同材料的照片转入Photoshop,通过其内置的亮度数值初步判断不同材料的反射效果。将亮度（p）、材料制作的难易程度(q)以及其它视觉效果(w)三项各10分的标准分数按一定比例绘制出总分数，来选取实验材料。
实验测量表格如下： （4）实验仪器：各种实验材料*1、投影光源（4.7英寸）*1、摄像机*1、Windows电脑（Photoshop软件）*1 二、实验过程记录 （1）实验分工 （2）实验步骤
第一步—确定材料。因为我们是初次进行研究，对于具体的实验材料并不能确定，所以我们进行了解后，一共选取了4种材料： 第二步--选取材料。因为我们进行的实验成本非常有限所以我们必须先走向市场，来查看和询问有些材料是否可以被加工和购买到（具体材料价格请见附录）。将他们的难易程度（q）进行量化，10分为很容易得到，1分为基本不可能得到，以此绘制表格： 第三步—对比亮度。在了解了我们选取的材料的基础上，以节约环保为本，我们购买或借到了这四种材料。并选择在2015年3月8日的晚上，在教室里进行亮度测试。我们先将光源设备调节到最大亮度，拍摄的得到了一张照片，再不断尝试不同的角度，以求能用最好的效果反射光源并拍摄下来。我们将五张照片导入电脑，用Photoshop软件分别查看他们的RGM指数（具体RGM指数请见附录），来进行评分，但因为镜子的超好反射效果，我们改进了我们算法，以分段函数的方式来进行得分评判（p）。 评分结果如下
农夫过河问题
课程设计题目：农夫过河 一．问题描述 一个农夫带着一只狼、一只羊和一箩白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。过河有以下规则： (1)农夫一次最多能带一样东西（或者是狼、或者是羊、或者是白菜）过河； (2)当农夫不在场是狼会吃羊； (3)当农夫不在场是羊会吃掉白菜。 现在要求为农夫想一个方案，能将3样东西顺利地带过河。从出事状态开始，农夫将羊带过河，然后农夫将羊待会来也是符合规则的，然后农夫将羊带过河仍然是符合规则的，但是如此这般往返，搜索过程便进入了死循环，因此，在这里，采用改进的搜索算法进行搜索。 二．基本要求 (1)为农夫过河问题抽象数据类型，体会数据模型在问题求解中的重要性； (2)要求利用数据结构的方法以及Ｃ＋＋的编程思想来完成问题的综合设 计； (3)在问题的设计中，使用深度优先遍历搜索方式，避免死循环状态； (4)设计一个算法求解农夫过河问题，并输出过河方案； (5)分析算法的时间复杂度。 三．概要设计 (1)数据结构的设计 typedef struct // 图的顶点 { int farmer; // 农夫 int wolf; // 狼 int sheep; // 羊 int veget; // 白菜 }Vertex;
设计Vertex结构体的目的是为了存储农夫、狼、羊、白菜的信息，因为在遍历图的时候，他们的位置信息会发生变化，例如1111说明他们都在河的北岸，而0000说明他们都在河的南岸。 t ypedef struct { int vertexNum; // 图的当前顶点数 Vertex vertex[VertexNum]; // 顶点向量（代表顶点） bool Edge[VertexNum][VertexNum]; // 邻接矩阵. 用于存储图中的边，其矩阵元素个数取决于顶点个数，与边数无关 }AdjGraph; // 定义图的邻接矩阵存储结构 存储图的方法是用邻接矩阵，所以设计一个简单的AdjGraph结构体是为了储图的顶点数与边数，农夫过河问题我采用的是图的深度优先遍历思想。 (2)算法的设计 深度优先遍历基本设计思想：设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的1/12边(x，y)。若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边(x，y)到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。 程序中的深度优先遍历算法如下： void dfsPath(AdjGraph *graph, int start, int end) // 深度优先搜索从u到v的简单路径 //DFS--Depth First Search { int i = 0; visited[start] = true; //标记已访问过的顶点 if (start == end)
野人过河问题算法分析
野人过河问题算法分析 野人过河问题属于人工智能学科中的一个经典问题，问题描述如下：有三个牧师（也有的翻译为传教士）和三个野人过河，只有一条能装下两个人的船，在河的任何一方或者船上，如果野人的人数大于牧师的人数，那么牧师就会有危险. 你能不能找出一种安全的渡河方法呢？ 一、算法分析 先来看看问题的初始状态和目标状态，假设和分为甲岸和乙岸：初始状态：甲岸，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 // 岸边状态类型