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

人工智能(项目设计)专 业： 计算机科学与技术 班 级： 电计1203学 号： 201281303姓 名： 刘阳 一.问题描述与分析传教士人数M，野人数C，M≥C，开始都在岸左边。①船最多只能载K人，传教士和野人都会划船，当然必须有人划船②两岸边保证野人人数不能大于传教士人数 把所有人都送过河，求解过河方案。如果求取最优解应使用A*算法，但如果输出整个解空间使用DFS比较直接，并且对于大多数情况而言，几种过河方案代价基本相同。在程序中需要保证状态节点向下拓展以提高效率。即如果有哪些信誉好的足球投注网站的状态在之前已经出现过了，就不深入下去了，否则会出现死循环。有哪些信誉好的足球投注网站算法这里采用DFS的非递归描述，如果当前节点无法继续拓展或者已经拓展到目标状态，那么将当前解中位于栈顶第一个待拓展状态之前的状态全部出栈（栈非空的情况下），如果当前达到目标状态还需要将解压入解空间中。程序中回溯不可避免因为总有不可继续拓展的节点，但是向上拓展必须避免因为这会导致有哪些信誉好的足球投注网站陷入错误的循环。二.程序源码及注释#include iostream#include vector#include string#include stdio.h#include conio.h#define MAXSIZE 50using namespace std;typedef struct{int person; //左岸传教士人数int wild; //左岸野人人数bool boat; //true表示船在左岸int method; //到达本状态上一步使用的方法int Last; //记录父状态编号}state; //状态节点int LastMethod=0; //记录上一步使用的方法，防止循环int LastState=-1; //上一步状态编号bool flag=true; //ture表示船在左岸vectorvectorstate answer; //最终解集vectorstate temp; //当前解空间暂存数组state Stack[MAXSIZE]; //用于非递归DFS的状态栈int f=0,r=0; //栈顶与栈底int A,B; //记录传教士与野人初始人数int k; //小船最多载的人数//函数声明int DFS(int M,int C,int m,int c);int judge(int M,int C,int m,int c);int next_judge(int M,int C,int m,int c,int met);int if_repeat(int M,int C,bool f);int disp();int DFS(int M,int C,int m,int c) //非递归DFS{ int X=M,Y=C,x=m,y=c; state index; 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((!flagX==0Y==0)) //全部运输过去 { answer.push_back(temp); if(r==f) break; else if(r!=f) { state t1; 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(