人工智能课程设计

《人工智能课程设计》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、滑块问题求解系统一、设计任务用智能搜索算法中的盲目搜索和启发式搜索这两类基本方法设计八数码问题的求解系统。所谓八数码问题是指这样一种游戏:将分别标有数字1,2,3,…,8的八块正方形数码牌任意地放在一块3×3的数码盘上.放牌时要求不能重叠.于是,在3×3的数码盘上出现了一个空格.现在要求按照每次只能将与空格相邻的数码牌与空格交换的原则,将任意摆放的数码盘逐步摆成某种特殊的排列.如下图表示了一个具体的八数码问题求解.2831476512384765二、设计环境及使用说明设计环境主要采用VC++开发环境。三、系统已实现的功能用广度优先搜索算法和两种A*搜索算法实现八数码问题的求解系统。

2、四、算法思想及分析1、广度优先搜索算法算法思想：这是一种盲目搜索算法。算法主要思想是从初始结点开始依次沿其上下左右四个方向扩展结点，并逐一检查这些后继结点是否为目标结点，若不等于目标结点则把该后继结点插入到数组末尾。然后取数组中未扩展的第一个结点重复以上操作，直到得到目标结点为止或在限定步数以内未得到解。数据结构：算法当中的结点用结构体实现，typedefstruct{intnum[9];//八个数码用一个一维数组来存储。charexpension;//记录是否可以扩展，Y代表可以扩展，N代表不可以。charbandirect;//表示不可以执行的操作，'L'代表不能左移，'R'代

3、表不能右移，'U'代表不能上移，'D'代表不能下移，'C'代表可以任意移动。intfather;//记录父节点的下标。}Node;扩展的结点存储在数组里：Nodenode[MAXSIZE];//将搜索过的状态存储于该数组中。算法当中遇到的问题和解决方法：1）如何去表达八个数码的位置和每个结点状态的表示用一维或二维数组去表示八个数码的位置关系，每个结点包含了一个一维数组（用来表示八个数码的位置关系），可扩展标记（用来标识一个结点是否被扩展过，避免重复扩展），限制移动方向的标记（避免一个结点在一个方向的重复扩展），记录父节点的指针（父节点下标）。2）如何以最简洁的方式表达一个结点在其四

4、个方向的扩展设定一个数组用以存储该结点在每个方位是否可扩展。操作一个结点时先根据空格的位置判断该结点可在哪些方向移动并在数组相应位置1.然后用一个for循环来解决不同方向移动时的相同操作代码的合并和不同操作代码的拆分处理。部分关键代码：intmove(inttmp)//将空格进行移动操作。{inttempNum;inti,j;intdir[4]={0};for(j=0;j<9;j++)//判断空格的位置。if(node[tmp].num[j]==0)break;//判断有哪几个方向可以移动//如果空格不在第一列的位置并且该结点可以往左移动则标记此结点可以往左方向移动。以下类似if(

5、j!=0&&j!=3&&j!=6&&node[tmp].bandirect!='L')dir[0]=1;if(j!=0&&j!=1&&j!=2&&node[tmp].bandirect!='U')dir[1]=1;if(j!=2&&j!=5&&j!=8&&node[tmp].bandirect!='R')dir[2]=1;if(j!=6&&j!=7&&j!=8&&node[tmp].bandirect!='D')dir[3]=1;//遍历某个结点的四个方向进行扩展后继结点for(i=0;i<4;i++){if(dir[i]){//复制原来的结点，防止被改变for(intk=0;k<

6、9;k++)node[temp].num[k]=node[tmp].num[k];//不同方向移动的不同处理if(i==0){//向左移动tempNum=node[temp].num[j-1];node[temp].num[j-1]=0;node[n].bandirect='R';}elseif(i==1){//向上移动tempNum=node[temp].num[j-3];node[temp].num[j-3]=0;node[n].bandirect='D';}elseif(i==2){//向右移动tempNum=node[temp].num[j+1];node[temp].nu

7、m[j+1]=0;node[n].bandirect='L';}else{//向下移动tempNum=node[temp].num[j+3];node[temp].num[j+3]=0;node[n].bandirect='U';}//向各方向移动的相同处理node[temp].num[j]=tempNum;node[tmp].expension='N';//存储移动后的结点，从中间结点temp复制for(intkk=0;kk<9;kk++)node[n].num[k