昆明理工大学 人工智能 实验报告

《人工智能导论》自动化133钟伦赋昆明理工大学信息工程与自动化学院学生实验报告（2015——2016学年第一学期）课程名称：人工智能导论开课实验室：信自楼432室2015年10月26日年级、专业、班学号姓名成绩实验项目名称状态空间搜索实验—八数码问题求解指导教师胡蓉教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有□教师签名：年月日目录一、实验问题 3二、实验目的 3三、实验原理 3四、程序框图 4五、实验结果及分析 51、随机检验 52、该问题广度优先搜索算法的搜索树； 63、该问题的Open表和Closed表： 7六、结论 7七、源程序及注释 8一、实验问题八数码问题的求解，及程序设计。具体要求如下在3*3的方格中的棋盘中任意摆放1到8个自然数和一个空格，其初始状态如下：123704685a初始状态123804765b目标状态请选择一种盲目搜索的算法或选择一种启发式搜索的算法编程求解八数码问题，初始状态任选，并对使用进行合理分析做出合理结果。二、实验目的1、熟悉人工智能系统中的问题求解过程；2、熟悉状态空间的满目搜索和启发式搜索算法的运用；3、熟悉对八码数问题的建模、求解及编程语言的运用；三、实验原理经过分析，8数码问题中可采用的搜速策略共有：1.广度优先搜索2.深度优先搜索2.有界深度优先搜索4.最好优先搜索5.局部择优搜索一共五种。其中，广度优先搜索法是可采纳的，有界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。在实验时，我采用了广度优先算法广度优先算法搜索原理：广度优先搜索就是始终先在同一级节点中考查，只有当同一级节点考察完之后，才考查下一级的节点。（1）把起始节点放到OPEN表中；（2）如果OPEN是个空表，则没有解，失败退出；否则继续；（3）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；（4）扩展节点n。如果没有后继节点，则转向（2）；（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转（2）四、程序框图是否是否有后继节点为目标节点？扩展节点n，把其后裔放入open表的前头否把open表中的第一个节点n移入close表是是否open表为空表？成功把s放入open表起始是否是否有后继节点为目标节点？扩展节点n，把其后裔放入open表的前头否把open表中的第一个节点n移入close表是是否open表为空表？成功把s放入open表起始失败失败五、实验结果及分析1、随机检验初始状态为：123704685的运行结果为：运行结果如图所示；目标状态为：1238047652、该问题广度优先搜索算法的搜索树；S23046852304685103724685123740685123103724685123740685123074685123784605DCBADCBALKJIHGFELKJIHGFE130724685013724685120743685123130724685013724685120743685123745680023174685123674085123784650123784065TSRQPONMTSRQPONM134720685713024685102743685123134720685713024685102743685123745608203174685123674805123780654123084765SgSg123804765123804765解路径：S A E M Sg3、该问题的Open表和Closed表：OPENCLOSEDSoABCDSoBCDEFSoACDEFGHSoABDEFGHIJSoABCEFGHIJKLSoABCDFGHIJKLMSoABCDEGHIJKLMNSoABCDEFHIJKLMNOSoABCDEFGIJKLMNOPSoABCDEFGHJKLMNOPQSoABCDEFGHIKLMNOPQRSoABCDEFGHIJLMNOPQRSSoABCDEFGHIJKMNOPQRSTSoABCDEFGHIJKLNOPQRSTSgSoABCDEFGHIJKLM六、结论通过实验问题的求解过程就是搜索的过程，让我明白了采用适合的搜索算法是关键的，因为一个合适的算法对求解过程的效率有很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动来描述规则，是一种相对较简单的方法。虽然我使用的广度优先算法实现八数码问题，但是我不得不说广度优先算法其实是一种比较费劲的方式；然而深度优先将是一个相对好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程有了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验让我受益匪浅。七、源程序及注释//八数码问题——广度优先#include<iostream.h>structSnode{ intparent;//指向该结点父节点的编号intmap[9];public:voidTransformIn(constint*d);voidTransformOut(int*d);};voidSnode::TransformIn(constint*d){for(inti=0;i<9;++i) map[i]=d[i];}#defineMAX_OPEN_LEN50000#defineMAX_CLOSE_LEN50000SnodeOPEN[MAX_OPEN_LEN];intop=0;SnodeCLOSE[MAX_CLOSE_LEN];intcp=0;intresult[50000][9];//result数组用于保存路径，纵向9个数为对应的map数组inthave(Snode&node1,Snode&node2)//判断是否为新节点{ intflag=1; for(inti=0;i<9;i++) { if(node1.map[i]!=node2.map[i])flag=0; } returnflag;}inlinevoidswapn(int&a,int&b){ inttmp=a;a=b;b=tmp;}//判断节点是否为目标节点intjudge(Snode&node){ intflag=1; intg[9]={1,2,3,8,0,4,7,6,5}; for(inti=0;i<9;i++) { if(node.map[i]!=g[i]) flag=0; } returnflag;}intAstar(constint*d){ intbegin=0;//begin含义是每次从OPEN表中去除要扩展的那个节点 intnode_number=1;//扩展节点数，初始时已有OPEN[0]节点,故为1，即node_number=cp+op staticintdp[4]={-3,-1,1,3};//-3表示向上移动，3表示向下移动，-1表示向左移动，1表示向右移动op=1;cp=0;OPEN[begin].TransformIn(d); OPEN[begin].parent=-1;//根节点的parent值设置为-1while(op>0)//OPEN表不为空 { inti=0,zero,pos,j=0,k=0;if(judge(OPEN[begin])==1)//找到的这个节点已经是目标节点 { CLOSE[cp]=OPEN[begin]; while(begin!=-1)//while循环用于把路径存入数组result中，顺序是从目标节点到根节点 {for(inti=0;i<9;i++) { result[j][i]=OPEN[begin].map[i]; } j=j+1; begin=OPEN[begin].parent; } for(i=j-1;i>=0;i--)//两层for循环用于把result数组中保存的路径输出，从最后一个向前输出 { for(k=0;k<9;k++) { cout<<result[i][k]<<""; if(k%3==2)cout<<endl; } cout<<endl; } cout<<"生成的节点总数为："<<node_number<<endl; cout<<"扩展的节点总数为："<<cp<<endl;return1; }for(zero=0;zero<9;++zero) { if(OPEN[begin].map[zero]==0)break;//跳出当前for循环，向下执行 }for(i=0;i<4;++i) {if(zero==0&&(i==0||i==1))continue;//判断zero位置怎样可以移动，与上边的判断相同if(zero==1&&i==0)continue;if(zero==2&&(i==0||i==2))continue;if(zero==3&&i==1)continue;if(zero==5&&i==2)continue;if(zero==6&&(i==1||i==3))continue;if(zero==7&&i==3)continue;if(zero==8&&(i==2||i==3))continue;pos=zero+dp[i]; swapn(OPEN[begin].map[zero],OPEN[begin].map[pos]);//交换位置Snodechild;child.TransformIn(OPEN[begin].map); for(j=0;j<cp;++j)//判断是否为新节点 { if(have(CLOSE[j],child)==1) break; }if(j==cp)//得到新节点 { OPEN[op]=child;//先使用op,再op加1 OPEN[op].parent=begin; op=op+1; node_number=node_number+1; if(node_number==10000)//有些情况可能不存在解，这里当op等于10000时退出，并返回0 { cout<<"node_number="<<node_number<<endl;//扩展的节点数 cout<<"op="<<op<<endl;//open表中的节点数 return0; } }