大连理工大学人工智能课程项目设计

人工智能(项目设计)专业：计算机科学与技术班级：电计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