“数据结构与算法综合实验”课程设计报告题目：农夫过河问题
学院计算机科学技术
年级2014级
专业计算机科学与技术
学号20142060
姓名高晗
日期2016年3月30日星期三
成绩
评语
黑龙江大学
计算机科学技术学院、软件学院
《数据结构与算法综合实验》报告
1.系统概述
（1）一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。
（2）为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。
（3）掌握顺序表和队列的逻辑结构和存储结构。
2.系统需求分析
(1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。
(2)题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到，不接受非法输入。
(3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。
(4)实验运行环境为VC++6.0.
3.系统概要设计
(1)数据结构设计
要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。则问题的初
始状态是整数（二进制数表示为0000）；问题的终结状态是整数15（二进制表示为1111）。
用一个整数队列MoveTo把搜索过程中所有可能达到的状态都保存起来。队列中的每一个元素表示一个可以到达的中间状态。另外用一个整数数组route记录被访问过的状态，以及已经被发现的能够到达这些状态的前驱。数组只需使用16个元素，每个元素的初始化值均为-1，每当队列中加入一个新状态时，数组中以该状态做下标的元素改为到达这一状态的前一状态的下标值。所以数组的第i个元素不仅记录状态i是否被过，同时还保存该状态的前驱状态下标。算法结束后可以利用route数组元素的值生成一个正确的状态路径。系统状态转换结构如图1所示:
图1系统状态转换结构图
（2）软件结构设计
农夫过河管理系统根据需求分析中的功能分析，可以提炼出主要有搜索功能，判断事物安全功能，输出过河方案功能。而搜索功能又可以利用不同算法，如广度优先算法，深度优先算法等等。判断事物安全功能需要将事物位置进行分析，通过位置分布的代码来判断当前状态是否安全，使用“与”位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。若是，该状态即为不安全状态，否则为安全状态。若一个状态已经被访问过，或只有农夫一人从南岸过到北岸，则该状态被判为无效状态。输出功能就是将过河方案在屏幕上进行显示。系统软
件结构如图1所示
图1农夫过河管理系统软件模块结构图
4.系统详细设计与实现
(1)搜索算法设计
搜索过程可利用广度优先搜索算法从初始状态二进制0000（全部在河的南岸）出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111（全部到达河的北岸）为最终目标，并且在序列中的每一个状态都可以从前一个状态得到。为避免重复，要求在序列中不出现重复的状态。
(2)确定状态的安全有效性的功能模块设计
通过位置分布的代码来判断当前状态是否安全，使用“与”位操作来考察狼和羊、羊和白菜是否在同一侧，且它们与农夫不一侧。若是，该状态即为不安全状态，否则为安全状态。若一个状态已经被访问过，或只有农夫一人从南岸过到北岸，则该状态被判为无效状态。若状态安全且有效，则返回1，否则返回0。该模块算法流程图如图2所示。
图2 确定状态的安全有效性的功能模块设计算法流程图（3）输出模块设计
输出农夫过河问题的可行性方案时，可从目标状态（1111）开始，将其记入队列（或栈）中，然后再找出其前驱，记入队列（或栈）中，然后在找其前驱，…，直到找到的是开始状态（0000）为止。要求输出时根据位置分布代码（即4位二进制数）各个位置上的0、1代码所表示的含义输出容易理解的文字。
5.系统测试
对于该程序而言并没有实际输入，需要观察的就是输出结果。对于该程序的测试及其测试用例如表3所示。
表3输出测试用例
测试内容测试用例预期结果实际结果
输出过河方案具体步骤无第0步：南岸农夫狼白菜羊
北岸
第1步：南岸狼白菜
北岸农夫羊
第2步：南岸农夫狼白菜
北岸羊
第3步：南岸狼
北岸农夫羊白菜
第4步：南岸农夫狼羊
北岸白菜
第5步：南岸羊
北岸农夫狼白菜
第6步：南岸农夫羊
北岸狼白菜
第7步：南岸
北岸农夫狼白菜羊
与预期结果
相同
6.小结
（1）通过这2周的程序设计使我了解到了自己在数据结构方面的不足，也坚定了我学好编程的信心。
（2）采用广度优先的算法，利用数组只能记寻前一个前驱，导致另一个路径的丢失，不是很令人满意，所以采用第二种算法，深度优先算法，利用栈来记录路径前驱。
参考文献
[1] 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版）[M]. 北京：人民邮电出版社，2011:54-110.
1.广度优先算法
#include
#include
#define MAXNUM 20
using namespace std;
typedef struct //顺序队列类型定义
{
int f, r; //f表示头，r 表示尾
int q[MAXNUM];//顺序队
}SqQueue ,*SqQueuePtr;
SqQueuePtr createEmptySQueue()//创建空队列
{
SqQueuePtr squeue = new SqQueue;
if(squeue == NULL)
{
cout<<"申请内存失败"< exit(0); } squeue->f=squeue->r=0; return squeue; } bool isEmptyQueue(SqQueuePtr squeue)//判断是否空队列{ return (squeue->f==squeue->r); } void enQueue(SqQueuePtr squeue,int x)//向队列中插入元素x { if((squeue->r+1)%MAXNUM==squeue->f) { cout<<"队列已满"< } else squeue->q[squeue->r]=x; squeue->r=(squeue->r+1)%MAXNUM; } } void deQueue(SqQueuePtr squeue)//出对 { if(isEmptyQueue(squeue)) cout<<"对列为空"< else squeue->f=(squeue->f+1)%MAXNUM; } int getHead(SqQueuePtr squeue)//对非空队列,求队列头部元素 { if(squeue->f != squeue->r) return squeue->q[squeue->f]; } bool farmerLocation(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置 { return 0 != (location & 0x08); } bool wolfLocation(int location) //判断狼位置 { return 0 != (location & 0x04); } bool cabbageLocation(int location) //判断白菜位置 { return 0 != (location & 0x02); } bool goatLocation(int location) //判断羊的位置 { return 0 !=(location & 0x01); } /* 其中一共有两种状态是不安全的：狼和羊单独在一起；羊和白菜单独在一起*/ bool isSafe(int location) // 若状态安全则返回true { if ((goatLocation(location) == cabbageLocation(location)) //羊和白菜单独在一起 && (goatLocation(location) !=farmerLocation(location)) ) return 0; if ((goatLocation(location) == wolfLocation(location)) && (goatLocation(location) !=farmerLocation(location)))//狼和羊单独在一起 return 0; return 1; //其他状态是安全的 } void farmerProblem() { int movers, i, location, newlocation; int route[16]; //记录已考虑的状态路径 int print[MAXNUM]; SqQueuePtr moveTo; moveTo = createEmptySQueue();//新的队列判断路径 enQueue(moveTo, 0x00); //初始状态为0 for (i = 0; i < 16; i++) route[i] = -1; //-1表示没有记录过路径 route[0]=0; while (!isEmptyQueue(moveTo)&&(route[15]== -1)) //队列不为空，路径未满时循环 { location = getHead(moveTo); //从队头出队，location表示位置，0为北岸，1为南岸 deQueue(moveTo);//已出队的删除 for (movers = 1; movers <= 8; movers<<= 1) //向左移位，movers分别0001，0010，0100，1000, //也就是依次判断过河的可行性 { if ((0 != (location & 0x08)) == (0 != (location & movers))) //判断农夫和要移动的物品是否在同岸 { newlocation = location^(0x08|movers);//过岸 if (isSafe(newlocation) && (route[newlocation] == -1)) //判断是否安全，以及路径是否可用 { route[newlocation] = location; enQueue(moveTo, newlocation); //记录路径并入队，位置改变 } } } } /* 打印路径*/ if(route[15] != -1) { cout<<"过河步骤是: "< cout<<"\t\t南岸\t\t\t北岸"< i=7; for(location = 15; location >= 0; location = route[location]) { print[i]=location; i--; if (location == 0) break; } for(int j=i+1;j<=7;j++) { cout<<"第"< switch(print[j]) { case 0: cout<<"\t\t农夫狼白菜羊\t\t\t"< case 1: cout<<"\t\t农夫狼白菜\t\t羊"< case 2: cout<<"\t\t农夫狼羊\t\t白菜"< case 4: cout<<"\t\t农夫白菜羊\t\t\t狼"< case 6: cout<<"\t\t农夫羊\t\t狼白菜"< case 9: cout<<"\t\t狼白菜\t\t\t农夫羊"< case 11: cout<<"\t\t狼\t\t\t农夫羊白菜"< case 13: cout<<"\t\t白菜\t\t\t农夫狼羊"< case 14: cout<<"\t\t羊\t\t\t农夫狼白菜"< case 15: cout<<"\t\t\t\t\t农夫狼羊白菜"< } } } } int main(){ farmerProblem(); return 0; } 2.深度优先算法 #include #include #define MAXNUM 20 using namespace std; int solutionCout=0; typedef struct { int *base;//栈底指针 int *top;//栈顶指针 int stacksize;//栈可用的最大容量 }SqStack; void createEmptyStack(SqStack &S)//构造一个空栈S { S.base=new int[MAXNUM]; if(!S.base) { cout<<"申请内存失败"< exit(0); } S.top=S.base;//初始为空栈 S.stacksize = MAXNUM; } void Push(SqStack &S,int x)//插入一个元素x { if(S.top-S.base==S.stacksize)//栈满 { cout<<"栈满"; } *S.top++=x; } void Pop(SqStack &S)//出栈 { if(S.top==S.base)//栈空 { cout<<"栈空"; } --S.top; } int getTop(SqStack S)//取栈顶元素 { return *(S.top-1); } void print(SqStack S)//打印路径 { int *p=S.base; solutionCout++; int print[MAXNUM]; int i=0; while(!(p==S.top)) { print[i]=*p; i++;p++; } cout<<"方案"< cout<<"\t\t南岸\t\t\t北岸"< for(int j=0;j { cout<<"第"< switch(print[j]) { case 0: cout<<"\t\t农夫狼白菜羊\t\t\t"< case 1: cout<<"\t\t农夫狼白菜\t\t羊"< case 2: cout<<"\t\t农夫狼羊\t\t白菜"< case 4: cout<<"\t\t农夫白菜羊\t\t狼"< case 6: cout<<"\t\t农夫羊\t\t狼白菜"< case 9: cout<<"\t\t狼白菜\t\t\t农夫羊"< case 11: cout<<"\t\t狼\t\t\t农夫羊白菜"< case 13: cout<<"\t\t白菜\t\t\t农夫狼羊"< case 14: cout<<"\t\t羊\t\t\t农夫狼白菜"< case 15: cout<<"\t\t\t\t\t农夫狼羊白菜"< } } } bool farmerLocation(int location) //判断农夫位置对0做与运算，还是原来的数字，用来判断位置 { return 0 != (location & 0x08); } bool wolfLocation(int location) //判断狼位置 { return 0 != (location & 0x04); } bool cabbageLocation(int location) //判断白菜位置 { return 0 != (location & 0x02); } bool goatLocation(int location) //判断羊的位置 { return 0 !=(location & 0x01); } /* 其中一共有两种状态是不安全的：狼和羊单独在一起；羊和白菜单独在一起*/ bool isSafe(int location) // 若状态安全则返回true { if ((goatLocation(location) == cabbageLocation(location)) //羊和白菜单独在一起 && (goatLocation(location) !=farmerLocation(location)) ) return 0; if ((goatLocation(location) == wolfLocation(location)) && (goatLocation(location) !=farmerLocation(location)))//狼和羊单独在一起 return 0; return 1; //其他状态是安全的 } int isAppeared(SqStack S,int location) //判断路径是否出现过,出现返回0；没有出现返回1 { int *p=S.base; while (!(p==S.top)) { if(*p==location) return 0; p++; } } void farmerProblem(SqStack S,int location) { if(location == 15) { print(S); return; } int newlocation,movers; for (movers = 1; movers <= 8; movers<<= 1) //向左移位，movers分别0001，0010，0100，1000, //也就是依次判断过河的可行性 { if ((0 != (location & 0x08)) == (0 != (location & movers))) //判断农夫和要移动的物品是否在同岸 { newlocation = location^(0x08|movers);//过岸 if (isSafe(newlocation) && isAppeared(S,newlocation)) //判断是否安全，以及路径是否可用 { Push(S,newlocation);//新路径入栈 farmerProblem(S,newlocation);//以新路径为当前状态递归寻找下一可行路径 Pop(S);//已找到的可行路径出战 } } } } int main(){ SqStack S;int location=0; createEmptyStack(S);//创建辅助空栈 Push(S,location);//首先将0000压入栈 farmerProblem(S,location); } 郑州轻工业学院 课程设计任务书 题目农夫过河 专业、班级计算机科学与技术 学号姓名 主要内容： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。基本要求: 编写求解该问题的算法程序，并用此程序上机运行、调试，屏幕显示结果，能结合程序进行分析。 主要参考资料: 数据结构严蔚敏 完成期限：2012/6/21 指导教师签名： 课程负责人签名： 年月日 郑州轻工业学院 本科 数据结构课程设计总结报告 设计题目：农夫过河 学生姓名： 系别：计算机与通信工程学院 专业：计算机科学与技术 班级：计算机科学与技术 学号： 指导教师： 2012年6 月21 日 一，设计题目 问题描述： 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不能吃白菜。要求给出农夫将所有的东西运过河的方案。 二，运行环境（软、硬件环境） VC6.0 Windows7系统 三，算法设计的思想 对于这个问题，我们需要先自动生成图的邻接矩阵来存储，主要方法是先生成各种安全状态结点，存放在顶点向量中；再根据判断两个结点间状态是否可以转换来形成顶点之间的所有边，并把它们保存在邻接矩阵中。在建立了图的邻接矩阵存储结构后，利用递归深度优先搜索求出从顶点（0，0，0，0）到顶点（1，1，1，1）的一条简单路径，这样做只能搜到一种合理方法，因为深度优先搜索遍历一个图的时候每一个结点只能被访问一次。 四，算法的流程图 要写算法的流程图，必须要先很了解自己的函数结构，我先在纸上手动的把整个过程在纸上画一遍，了解它的大体流程，然后把各个函数给分开，下面是我自己根据我的代码中画的各个函数画的流程图，希望老师满意。 主函数的流程图： 实验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 实现汉诺塔演示的程序。 程序运行界面如图所示。 数学模型实验—实验报告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 商人过河 一、问题重述和分析 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货。现有4名商人各带一个随从一起渡河一只船只能容纳两个人，但如何乘船渡河的大权掌握在商人的手里，商人怎样安排才能在有限步内安全渡河？ 二、模型假设 1、在商人人数多于随从时乘船渡河的大权掌握在商人的手里； 2、商人和随从都会划船； 三．符号说明 x表示商人人数； y表示随从人数； z表示划船到河的此岸与彼岸。 四、模型的建立与求解 本题为多步决策模型，每一次过河都是状态量的转移过程。 此岸四个商人用x=0、1、2、3、4表示，此岸四个随从用y=0、1、2、3、4表示，z=0时表示划船到河的此岸时，z=1时表示划船到河的彼岸时，用有序数对（x，y，z）表示每次转移的状态量。解决此问题就是状态量（4,4,0）转移至（0,0,1），以下就是状态量转移的全部情况（其中“！”表示不能再转移下去或与前面步骤重复）： （4,4，0）→（3,3,1） ↓↓ （4,2,1）→（4,3,0）→（4,1,1）→（4,2,0）→（4,0,1）→（4,1,0）→！ ↓ （2,2,1） ↓ ！ 由以上关系可知，一只船只能容纳两个人的情况下，四名商人各带一个随从无法过河。 此外，如果船的容量增加到3人，那么商人就能以几种方式安全过河，以下 是其中一种方案： （4,4,0）→（4,2,1）→（4,3,0）→（4,1,1,）→（4,2,0）→（2,2,1） ↓ （0,1,1）←（0,3,0）←（0,2,1）←（0,4,0）←（0,3,1）←（3,3,0）↓ （0,2,0）→（0,0,1） 五、模型推广 通过以上模型的建立，若商人和随从人数增加或小船容量加大，考虑n名商人各带一随从的情况。 计算机科学与技术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 四、算法描述 农夫过河问题状态图及程序 一、问题需求分析 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。问题是他面前只有一条小船，船小到只能容下他和一件物品，另外只有农夫能撑船。另外，因为狼能吃羊，而羊爱吃白菜，所以农夫不能留下羊和白菜或者狼和羊单独在河的一边，自己离开。请问农夫该采取什么方案才能将所有的东西运过河呢？ 二、算法选择 求解这个问题的最简单的方法是一步一步进行试探，每一步都搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 用计算机实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first) 搜索，另一种是深度优先(depth_first) 。 广度优先： u 广度优先的含义就是在搜索过程中总是首先搜索下面一步的所有可能状态，然后再进一步考虑更后面的各种情况。u 要实现广度优先搜索，一般都采用队列作为辅助结构。把下一步所有可能达到的状态都列举出来，放在这个队列中， 然后顺序取出来分别进行处理，处理过程中把再下一步的状态放在队列里……。 u 由于队列的操作遵循先进先出的原则，在这个处理过程中，只有在前一步的所有情况都处理完后，才能开始后面一步各情况的处理。 三、算法的精化 要模拟农夫过河问题，首先需要选择一个对问题中每个角色的位置进行描述的方法。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。例如用0表示农夫或者某东西在河的南岸，1表示在河的北岸。因此整数5(其二进制表示为0101) 表示农夫和白菜在河的南岸，而狼和羊在北岸。 四、算法的实现 完成了上面的准备工作，现在的问题变成： 从初始状态二进制0000(全部在河的南岸) 出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸) 为最终目标，并且在序列中的每一个状态都可以从前一状态通过农夫（可以带一样东西）划船过河的动作到达。 商人过河问题 /*************************************************** *M个商人与每人各带的一个仆人过河问题 *船每次至多运N个人，至少要有一人划船 *在任一岸，当商人数<仆人数时,仆人就杀人越货 *过河由商人安排运送人员及数目 *找出安全渡河的全部方法并打印(原问题中M=3，N=2) *2010-10-10 20时许（纪念伟大的双十） * LYP ***************************************************/ /****************************************************************** *本题为多步决策 *若考虑只针对人数为 M = 3 对，每次过河人数最多 N = 2 *可以证明路径中必须经坐标中(3,1)过至(1,1)点(过诃时)， *后返回至(2,2)点，再过诃至(0,2)点(只剩2个仆人) *可以先考虑(3,3)到(3,1)点 *再经(0,2)至(0,0),完成过诃(由图形的对称性关系,可以直接将(3,1)至(3,1)路径翻转,更改对应标号即可) *当然也可以用动态规划求解 *本代码不限定M,N值,可通过修改宏M,N的值,求其他商人(仆人)数与最大过河人数的全部路径 *******************************************************************/ /********************************************************************* * *商人数x < 仆人数y时遭杀人越货，过河失败 *对应可行域为: *x = 0, y = 0…M; elements[]中编号0…M *0 < x < M, y = x; elements[]中编号M+1…2M-1 *x = M, y = 0…M； elements[]中编号2M…3M *图像上表示如下:(共 3*M+1 个点),过河即从3M点到0点 *过河为左下方1/4圆区域 *返回为右上方1/4圆区域 人工智能上机实验报告 学号：姓名：所在系：信息学院班级： 实验名称：实验日期2016年12月3日 实验指导教师实验机房A401 ------------------------------------------------------------------------------------------------------ 1.实验目的： (1)在掌握状态空间搜索策略的基础上，理解知识表示的方法。 (2)能够应用知识表示方法，解决实际问题 2. 实验内容： (1)M-C问题描述 有n个牧师和n个野人准备渡河，但只有一条能容纳c个人的小船，为了防止野人侵犯牧师，要求无论在何处，牧师的人数不得少于野人的人数(除非牧师人数为0)，且假定野人与牧师都会划船，试设计一个算法，确定他们能否渡过河去，若能，则给出小船来回次数最少的最佳方案。 3．算法设计（编程思路或流程图或源代码） #include 课程设计第五题 1．题目探讨农夫过河的问题 2.设计思路 （1）农夫由A到B的情况 （1）带走一个动物后，另外的两个物是不是可以相吃 （2）会不会把刚带回来的又带到对岸去 （3）最后一次带的情况比较的特殊，判断最后一次走后是不是所有的都不在了对岸 （2）农夫从B到A的情况 （1）对岸是不是只有一个物体 （2）对岸是不是有两个物体，若是有两个物体的话他们的处理方式不一样，1。两个物体会相克的，则把羊带走，2如果不是的话那么农夫就空着手回去。 3．应该注意的问题 （1）。在最后的一次带走羊的时候，应该加如一个新的判段 （2）。以及在带回羊的时候，我们要对其进行一个标记，不然的话我们就很容易进行死循环里面 （3）以及每一次从A带东西去B的时候，我们都要对他的位置进行标记下 4．咸受 在对一个问题分析的时候，我们应该先把每一种情况给分析出来，要把问题分析得分面一些，最好是不要落下任何的一种情况，这样我们就可以对每一种情况编写相应的代码了。5．源代码 static int sum(int[] a) { int sum = 0; for (int i = 0; i < a.Length; i++) { sum = sum + a[i]; } return sum; } static void Main(string[] args) { string[] wu = new string[4] { "农夫", "狼", "羊", "白菜" }; int[] a = new int[4] { 3, 1, -1, 1 }; int[] b = new int[4] { 0, 0, 0, 0 }; Console.WriteLine(" 关于农夫过河的问题"); int weizhi = 0; do { if (a[0] == 3) { 数据结构实验报告 ——实验四农夫过河的求解本实验的目的是进一步理解顺序表和队列的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。 一、【问题描述】 一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸。他要把这些东西全部运到北岸。他面前只有一条小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜，否则狼会吃羊，羊会吃白菜，所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，而狼不吃白菜。请求出农夫将所有的东西运过河的方案。 二、【数据结构设计】 求解这个问题的简单的方法是一步一步进行试探，每一步搜索所有可能的选择，对前一步合适的选择再考虑下一步的各种方案。 要模拟农夫过河问题，首先需要对问题中每个角色的位置进行描述。一个很方便的办法是用四位二进制数顺序分别表示农夫、狼、白菜和羊的位置。用0表示农夫或者某东西在河的南岸，1表示在河的北岸。例如整数5(其二进制表示为0101)表示农夫和白菜在河的南岸，而狼和羊在北岸。 现在问题变成：从初始状态二进制0000(全部在河的南岸)出发，寻找一种全部由安全状态构成的状态序列，它以二进制1111(全部到达河的北岸)为最终目标，并且在序列中的每一个状态都可以从前一状态到达。为避免瞎费功夫，要求在序列中不出现重复的状态。 实现上述求解的搜索过程可以采用两种不同的策略：一种是广度优先(breadth_first)搜索， 另一种是深度优先(depth_first)搜索。本书只介绍在广度优先搜索方法中采用的数据结构设计。 广度优先就是在搜索过程中总是首先搜索下面一步的所有可能状态，再进一步考虑更后面的各种情况。要实现广度优先搜索，可以使用队列。把下一步 《数学模型实验》实验报告 姓名：王佳蕾学院：数学与信息科 学学院 地点：主楼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）。 （二）程序设计 “数据结构与算法综合实验”课程设计报告题目：农夫过河问题 学院计算机科学技术 年级2014级 专业计算机科学与技术 学号20142060 姓名高晗 日期2016年3月30日星期三 成绩 评语 黑龙江大学 计算机科学技术学院、软件学院 《数据结构与算法综合实验》报告 1.系统概述 （1）一个农夫带着一只狼、一只羊和一棵白菜，身处河的南岸，他要把这些东西全部运到北岸。他面前只有一只小船，船只能容下他和一件物品，另外只有农夫才能撑船。如果农夫在场，则狼不能吃羊，羊不能吃白菜；否则狼会吃羊，羊会吃白菜。所以农夫不能留下羊和白菜自己离开，也不能留下狼和羊自己离开，但是狼不吃白菜。要求给出农夫将所有东西运过河的方案。 （2）为农夫过河问题抽象数据模型，体会数据模型在求解问题中的重要作用。 （3）掌握顺序表和队列的逻辑结构和存储结构。 2.系统需求分析 (1)针对实现整个过程需要多步，不同步骤中各个事物所处位置不同的情况，可定义一个结构体来实现对四个对象狼、羊、白菜和农夫的表示。对于起始岸和目的岸，可以用0或者1来表示，以实现在程序设计中的简便性。 (2)题目要求给出四种事物的过河步骤，没有对先后顺序进行约束，这就需要给各个事物依次进行编号，然后依次试探，若试探成功，进行下一步试探。这就需要使用循环或者递归算法，避免随机盲目运算且保证每种情况均试探到，不接受非法输入。 (3)题目要求求出农夫带一只羊，一条狼和一颗白菜过河的办法，所以依次成功返回运算结果后，需要继续运算，直至求出结果，即给出农夫的过河方案。输出界面要求具有每一步中农夫所带对象及每步之后各岸的物体，需要定义不同的数组来分别存储上述内容，并使界面所示方案清晰简洁。 (4)实验运行环境为VC++6.0. 3.系统概要设计 (1)数据结构设计 要模拟农夫过河的问题，用四位二进制数顺序分别表示农夫，狼，羊，白菜的位置。用0表示农夫或某种东西在河的南岸，1表示在河的北岸。则问题的初 数学建模课程作业 论文题目： 对商人过河问题的研究 指导教师：黄光辉 小组成员：黄志宇（20156260）车辆工程04班 牛凯春（20151927）电气工程05班 文逸楚（20150382）工商管理02 班 一、问题重述 3名商人带3名随从乘一条小船过河，小船每次只能承载至多两人。随从们密约，在河的任一岸，一旦随从的人数比商人多，就杀人越货。乘船渡河的方案由商人决定，商人们如何才能安全渡河呢？ 二、问题分析 本题针对商人们能否安全过河问题，需要选择一种合理的过河方案。对该问题可视为一个多步决策模型，通过对每一次过河的方案的筛选优化，最终得到商人们全部安全过到河对岸的最优决策方案。对于每一次的过河过程都看成一个随机决策状态量，商人们能够安全到达彼岸或此岸我们可以看成目标决策允许的状态量，通过对允许的状态量的层层筛选，从而得到过河的目标。 三、模型假设 1.过河途中不会出现不可抗力的自然因素。 2.当随从人数大于商人数时，随从们不会改变杀人的计划。 3．船的质量很好，在多次满载的情况下也能正常运作。 4.随从会听从商人的调度，所有人都到达河对岸。 四、符号说明 第k次渡河前此岸的商人数 第k次渡河前此岸的随从数 过程的状态向量 允许状态集合 第k次渡船上的商人数 第k次渡船上的随从数 决策向量 允许决策集合 x y 3322110s 1s n +1d 1d 11五、模型建立 本题为多步决策模型，每一次过河都是状态量的转移过程。 用二维向量表示过程的状态，其中分别表示对应时刻此岸的商人，仆人数以及船的行进方向，其中则允许状态集合: = 又将二维向量定义为决策，则允许的决策合集为: 因为k 为奇数时船从此岸驶向彼岸，k 为偶数时船从彼岸驶向此岸，所以状态随决策的变化规律是 该式称为状态转移律。 求决策，使,并按照转移律，由经过有限步n 到达状态 六、模型求解 本模型使用MATLAB 软件编程，通过穷举法获得决策方案如下(完整matlab 程序详见附录): 初始状态： 可用图片表示为：X0= 3 3状态为: S = 3 13 23 03 11 12 20 20 30 10 20 0决策为: D = 02 Lab05．队列的操作及应用 【实验目的和要求】 1．掌握队列的顺序表示和链表表示下的基本操作； 2．深入理解深度优先搜索和广度优先搜索的思想并能正确描述其算法； 3．会应用广度优先搜索算法解决较复杂的问题。 【实验内容】 1．编写一个C源程序，其中包含顺序表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。 2．编写一个C源程序，其中包含链表表示的空队列的创建、判断队列是否为空、进队、出队、取队列头部元素等操作。 3. 简述深度优先搜索和广度优先搜索的思想，并给出具体的算法步骤。 4．应用广度优先搜索算法求解农夫过河问题。 【实验仪器与软件】 1．CPU主频在1GHz以上，内存在512Mb以上的PC； 2．VC6.0，Word 2003及以上版本。 实验讲评： 实验成绩： 评阅教师： 2012 年月日 Lab05．队列的操作及应用 一、顺序表示的队列基本操作 1．顺序表示的队列操作基本源程序 #include 商人过河问题 一、三名商人各带一名随从的情况 1．问题（略） 2．模型假设 ①当一边岸满足随从数大于商人数，但商人数为0时仍为一种安全状 态； ②小船至多可容纳2人，且渡河时由随从（或者商人）来划船。 3．分析与建模 商人过河需要一步一步实现，比如第一步：两个仆人过河，第二步：一个仆人驾船回来，第三步：又是两个仆人过河，第四步：…… 其中每一步都使当前状态发生变化，而且是从一种安全状态变为另一种安全状态。如果我们把每一种安全状态看成一个点，又如果存在某种过河方式使状态a变到状态b，则在点a和点b之间连一条边，这样我们把商人过河问题和图联系起来，有可能用图论方法来解决商人过河问题。 建模步骤：⑴首先要确定过河过程中的所有安全状态，我们用二元数组(,) x y 表示一个安全状态（不管此岸还是彼岸），其中x表示留在此岸的主人数，y表示留在此岸的随从数。两岸各有十种安全状态： (0,0),(0,1),(0,2),(0,3),(2,2),(1,1),(3,0),(3,1),(3,2),(3,3) ⑵在两岸的安全状态之间，如存在一种渡河方法能使一种状态变为另一种 安全状态，则在这两种状态之间连一条边。这样，得到如下一个二部图（图1），其中下方顶点表示此岸状态，上方顶点表示彼岸状态。我们的目的是要找出一条从此岸(3,3)到彼岸(0,0)的最短路。 ⑶观察发现此岸的状态(0,0)，(3,0)和彼岸的状态(0,3)，(3,3)都是孤立点，在求最短路的过程中不涉及这些点，把它们删去。两岸的点用1,2, (16) 新标号。 （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,0） ○②④⑥⑧⑩○○12○14○16 ①③⑤○⑦⑨○11○13○15○ （3,3）（3,2）（3,1）（3,0）（1,1）（2,2）（0,3）（0,2）（0,3）（0,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) *******大学 实验报告| | 实验名称PROLOG语言练习与编程上机实验 课程名称人工智能及应用 | | 专业班级：*******学生姓名：****** 学号：*******成绩： 指导教师：*******实验日期： 一、实验目的及要求 1、熟悉并掌握prolog的编程环境、prolog语言的回溯、递归技术和表处理技 术； 2、运用prolog及其相关技术，编写并调试求解农夫过河和模式搜索问题的程 序。要求实验报告中包括：程序及其注释和说明、程序运行结果。 二、所用仪器、设备 PC台式机和prolog编译软件 三、实验原理 1、prolog本身自带推理机，其回溯、递归技术和表处理技术可简化复杂问 题求解。 2、prolog的跟踪、设断点对于调试程序是非常有用的。 四、求解的问题与程序 农夫过河问题 opposite(s,n). opposite(n,s). safe_goat(X,_,X,_). safe_cabbage(X,_,_,X). safe_goat(F,X,Y,_):-opposite(X,Y). safe_cabbage(F,_,X,Y):-opposite(X,Y). is_peaceful(F,W,G,C):-safe_goat(F,W,G,C),safe_cabbage(F,W,G,C). transform(location(X,W,G,C),location(Y,W,G,C)):-opposite(X,Y). transform(location(X,X,G,C),location(Y,Y,G,C)):-opposite(X,Y). transform(location(X,W,X,C),location(Y,W,Y,C)):-opposite(X,Y). transform(location(X,W,G,X),location(Y,W,G,Y)):-opposite(X,Y). member(X,[X|_]). member(X,[_|T]):-member(X,T). legal_states(location(F0,W0,G0,C0),location(F,W,G,C),States,X):- transform(location(F0,W0,G0,C0),location(F1,W1,G1,C1)), 组长：王鹏道110714 组员：任利伟110713、孙祎110706 小组成员负责情况： 王鹏道：选择论文题目、设计论文版面字体、分配成员任务、总结任利伟：一、问题提出、关键、分析。二、模型假设、三、模型建立孙祎：四、模型求解、五、模型的检验、拓展及延伸 2014年11月24日 摘要 为了求解3个商人和3个随从的过河问题，用数学分析方法，建立数学模型，并且加以求解，展示动态规划思想的应用步骤。最后利用计算机蝙程进行求解，获得过河问题的完整求解过程；有效地求解类似多步决策问题的作用。 关键词：多步决策计算机求解状态转移律图解法 一、 问题的提出 随从们密约, 在河的任一岸, 一旦随从的人数比商人多, 就杀人越货，但是乘船渡河的方案由商人决定.商人们怎样才能安全过河? 二、 问题的关键 解决的关键集中在商人和随从的数量上，以及小船的容量上，该问题就是考虑过河步骤的安排和数量上。各个步骤对应的状态及决策的表示法也是关键。 三、 问题的分析 在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河。由于船上人数限制，这需要多步决策过程，必须考虑每一步船上的人员。动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 四、 模型假设 记第k 次过河前A 岸的商人数为X K ， 随从数为Y K k=1，2，? X K ,Y K =0，1，2，3，将二维向量S K =(X K ，Y K )定义为状态．把满足安全渡河条件下的状态集合称为允许状态集合。记作S 。则 S={(X K ,Y K )|(X K =0,Y K =0,1,2,3),(X K =3,Y K =0,1,2,3),(X K =Y K =1)(X K =Y K =2)} 记第k 次过河船上的商人数为U K 随从数为V K 将二维向量D K =(U K ,V K )定义为决策．由小船的容量可知允许决策集合（记作D)为 D={(U K ,V K )|U K +V K =l,2}={(O,1);(O,2);(1,O);(1,1);(2,O)} 五、 模型建立： 动态规划法正是求解多步决策的有效方法。它要求把解的问题一层一层地分解成一级一级、规模逐步缩小的子问题。直到可以直接求出其解的子问题为止。分解成所有子问题按层次关系构成一棵子问题树．树根是原问题。原问题的解依赖于子问题树中所有子问题的解。 农夫过河 教学目标 1、知识与能力：通过农夫过河的数学逻辑问的题，探讨研究找到解决问题的办法和养成自己动脑动手的解决问题的能力。 2、过程与方法：通过以角色扮演的形式让学生自己动脑动手寻找答案和探讨解决问题的方法。 3、态度价值观：知道数学有很多有趣的东西，培养爱科学的情感。教师准备 1. 数学课件。 2、做“狼、羊、白菜、农夫”头饰。 3、准备四张纸分别写上“狼、羊、白菜、农夫”。 教学过程 一、谈话导入 介绍我国著名的数学家华罗庚爷爷。 数学家华罗庚生平介绍，主要科学业绩，对数学的贡献等等。介绍华罗庚爷爷的话。“数学本身，也是无穷的美妙，认为数学枯燥，是不正确的，就像站在花园外面，说花园枯燥无味一样，只要你踏进大门，随时会发现数学有许多有趣的东西。”数学并不是几个数字算来算去，它的学问大着呢。下面这道题能引起你的兴趣吗？ 二、创设情境 1、出示数学问题：有一个农夫带一匹狼、一只羊和一棵白菜过河（从河的东岸到西岸）。如果没有农夫看管，则狼要吃羊，羊要吃白菜。 但是船很小，只够农夫带一样东西过河。 2、图片演示。（一条河；一边是对岸；另一边是河岸，有农夫、狼、羊、白菜） 三、探究学习 1、以小组表演形式（演示出河的位置）和讨论形式解题 第一步是什么？必须是什么？（农夫和羊先过河） 第二步是什么？（农夫自己回来） 第三步是什么？ 2、全班学生汇报交流 问题的突破口在——狼与白菜能够共存！农夫、狼、羊、白菜和船组成了这个系统。系统中各要素是一个整体，都依赖农夫过河；最大的问题是“船很小，只够农夫带一样东西过河”和“没有农夫看管，则狼要吃羊，羊要吃白菜”的冲突。我们联系已知条件，做了一系列的分析实验，但是比较其他方案不能实现所有要素都安全过河。最后得出以上方案。 具体描述如下： 第一步：把羊带过河，坐船返回； 第二步：把狼带过河，带羊返回； 第三步：将羊放在这一岸后，带白菜过河； 第四步：坐船返回，把羊带过河。 或者： 第一步：把羊带过河，坐船返回；农夫过河数据结构
人工智能实验一指导
商人过河实验报告
商人过河问题
人工智能实验报告
农夫过河问题状态图及程序
商人过河问题
MC牧师过河问题
C# 关于农夫过河的问题
农夫过河实验报告――数据结构
数学模型实验商人过河
农夫过河实验报告
数学建模 商人过河
LAB05+队列的操作及应用
商人过河问题
研究性学习实验报告
农夫过河问题
PROLOG实验报告
数学建模商人过河__论文
趣味数学教案—农夫过河
相关主题
文本预览