![大连理工大学人工智能课程项目设计_第1页](http://file4.renrendoc.com/view/7570c0859da84c50a9eef60782ef1e2d/7570c0859da84c50a9eef60782ef1e2d1.gif)
![大连理工大学人工智能课程项目设计_第2页](http://file4.renrendoc.com/view/7570c0859da84c50a9eef60782ef1e2d/7570c0859da84c50a9eef60782ef1e2d2.gif)
![大连理工大学人工智能课程项目设计_第3页](http://file4.renrendoc.com/view/7570c0859da84c50a9eef60782ef1e2d/7570c0859da84c50a9eef60782ef1e2d3.gif)
![大连理工大学人工智能课程项目设计_第4页](http://file4.renrendoc.com/view/7570c0859da84c50a9eef60782ef1e2d/7570c0859da84c50a9eef60782ef1e2d4.gif)
![大连理工大学人工智能课程项目设计_第5页](http://file4.renrendoc.com/view/7570c0859da84c50a9eef60782ef1e2d/7570c0859da84c50a9eef60782ef1e2d5.gif)
版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领
文档简介
人工智能(项目设计)专业:计算机科学与技术班级:电计1203学号:201281303姓名:刘阳一.问题描述与分析传教士人数M,野人数C,M≥C,开始都在岸左边。
①船最多只能载K人,传教士和野人都会划船,当然必须有人划船
②两岸边保证野人人数不能大于传教士人数
把所有人都送过河,求解过河方案。如果求取最优解应使用A*算法,但如果输出整个解空间使用DFS比较直接,并且对于大多数情况而言,几种过河方案代价基本相同。在程序中需要保证状态节点向下拓展以提高效率。即如果搜索的状态在之前已经出现过了,就不深入下去了,否则会出现死循环。搜索算法这里采用DFS的非递归描述,如果当前节点无法继续拓展或者已经拓展到目标状态,那么将当前解中位于栈顶第一个待拓展状态之前的状态全部出栈(栈非空的情况下),如果当前达到目标状态还需要将解压入解空间中。程序中回溯不可避免因为总有不可继续拓展的节点,但是向上拓展必须避免因为这会导致搜索陷入错误的循环。二.程序源码及注释#include<iostream>#include<vector>#include<string>#include<stdio.h>#include<conio.h>#defineMAXSIZE50usingnamespacestd;typedefstruct{intperson;//左岸传教士人数intwild;//左岸野人人数boolboat;//true表示船在左岸intmethod;//到达本状态上一步使用的方法intLast;//记录父状态编号}state;//状态节点intLastMethod=0;//记录上一步使用的方法,防止循环intLastState=-1;//上一步状态编号boolflag=true;//ture表示船在左岸vector<vector<state>>answer;//最终解集vector<state>temp;//当前解空间暂存数组stateStack[MAXSIZE];//用于非递归DFS的状态栈intf=0,r=0;//栈顶与栈底intA,B;//记录传教士与野人初始人数intk;//小船最多载的人数//函数声明intDFS(intM,intC,intm,intc);intjudge(intM,intC,intm,intc);intnext_judge(intM,intC,intm,intc,intmet);intif_repeat(intM,intC,boolf);intdisp();intDFS(intM,intC,intm,intc)//非递归DFS{intX=M,Y=C,x=m,y=c;stateindex;judge(X,Y,x,y);//初始情况进栈while(r!=f){index=Stack[--r];X=index.person;Y=index.wild;x=M-X;y=C-Y;temp.push_back({X,Y,index.boat,index.method,index.Last});LastState++;LastMethod=index.method;if((!flag&&X==0&&Y==0))//全部运输过去{answer.push_back(temp);if(r==f)break;elseif(r!=f){statet1;t1=temp.back();//将解集暂存数组temp中栈顶状态后的状态删除while(Stack[r-1].Last!=t1.Last){temp.pop_back();t1=temp.back();}temp.pop_back();index=Stack[--r];//将栈顶待拓展状态出栈temp.push_back({index.person,index.wild,index.boat,index.method,index.Last});LastMethod=index.method;LastState=index.Last;//重置上一步状态编号LastState++;flag=index.boat;X=index.person;Y=index.wild;x=M-X;y=C-Y;}}if(!judge(X,Y,x,y)){if(r!=f)//如果栈中仍有待拓展节点,才需要将栈顶状态后的状态删除{statet2;t2=temp.back();while(Stack[r-1].Last!=t2.Last){temp.pop_back();t2=temp.back();}temp.pop_back();flag=Stack[r-1].boat;LastState=Stack[r-1].Last;}}}if(0==answer.size())return0;elsereturn1;}intjudge(intM,intC,intm,intc)//将下一步可能状态进栈{inti,j,signal=0;intT=1;if(1==flag){flag=!flag;for(i=0;i<=k;i++){for(j=0;(i+j)<=k;j++,T++)if(next_judge(M-i,C-j,m+i,c+j,T)&&(if_repeat(M-i,C-j,flag&!((i==0)&&(j==0)))){Stack[r++]={M-i,C-j,flag,T,LastState};signal=1;}}}else{flag=!flag;for(i=0;i<=k;i++){for(j=0;(i+j)<=k;j++,T++)if(next_judge(M+i,C+j,m-i,c-j,T)&&(if_repeat(M+i,C+j,flag&&(!((i==0)&&(j==0)))){Stack[r++]={M+i,C+j,flag,T,LastState};signal=1;}}}returnsignal;}//判断接下来的可能状态是否非法intnext_judge(intM,intC,intm,intc,intmet){if(M<0||C<0||m<0||c<0)//非法return0;if(M>A||C>B||m>A||c>B)//非法return0;if((M==A)&&(C==B))//防止回溯到初始节点return0;if((M&&C>M)||(m&&c>m))//野人会吃传教士return0;if(LastMethod==met)//回溯return0;return1;}//判断接下来的可能状态是否与栈或当前解中已有状态重复intif_repeat(intM,intC,boolf){//判断接下来的可能状态是否与当前栈中待拓展状态重复,防止回溯for(intx=0;x<r;x++)if((Stack[x].person==M)&&(Stack[x].wild==C)&&(Stack[x].boat==f))return0;//判断接下来的可能状态是否与当前解空间中已经存在的状态重复,防止循环for(unsignedintx=0;x<temp.size();x++)if((temp[x].person==M)&&(temp[x].wild==C)&&(temp[x].boat==f))return0;return1;}intdisp()//输出解集{printf("一共有%d种解法\n",answer.size());unsignedintm,n;inti,j,T;for(m=0;m<answer.size();m++){printf("第%d种解法:\n",m+1);printf("(%d,%d)boat=left\n",A,B);for(n=0;n<answer[m].size();n++){for(T=1,i=0;i<=k;i++){for(j=0;(i+j)<=k;j++,T++)if(T==answer[m][n].method){cout<<"("<<i<<","<<j<<")"<<endl;}}if(answer[m][n].boat)printf("(%d,%d)boat=left\n",answer[m][n].person,answer[m][n].wild);elseprint
温馨提示
- 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
- 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
- 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
- 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
- 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
- 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
- 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
最新文档
- 三农项目投资规划方案
- 智慧城市建设规划设计协议
- 校园绿化与学生环保意识的培养路径
- 现代办公环境中网络游戏的商业模式分析
- 电影科技的发展与未来办公模式
- 油漆施工承包合同
- 雪孩子之友情的力量读后感
- 短视频在网络媒体中的崛起与前景
- 旅游景区游客安全保障及紧急救援协议
- 革命故事小兵张嘎评析与启示
- 2025年不停电电源(UPS)项目合作计划书
- 2025年国家林业和草原局直属事业单位第一批招聘应届毕业生96人历年高频重点模拟试卷提升(共500题附带答案详解)
- 2025年春季开学典礼校长讲话稿-少年无畏凌云志扶摇直上入云苍
- 山东省泰安市新泰市2024-2025学年(五四学制)九年级上学期1月期末道德与法治试题(含答案)
- 1《北京的春节》课后练习(含答案)
- (完整版)陆河客家请神书
- 2025年行业协会年度工作计划
- DB3502T 160-2024 工业产品质量技术帮扶和质量安全监管联动工作规范
- 2025年学校教师政治理论学习计划
- 集团专利管理制度内容
- 提高发票额度的合同6篇
评论
0/150
提交评论