人工智能重排九宫

人工智能课内实验报告重排九宫问题班级:姓名：学号:重排九宫问题搜索就是利用已知条件（知识）寻求解决问题的办法的过程。状态空间搜索即为一种重要的搜索策略，其可分为盲目搜索和启发式搜索。实验目的利用状态空间搜索解决实际问题，将理论应用于实践。加深对概念的理解、知识的掌握，并提高编程能力和动手能力。实验原理重排九宫问题在3*3的方格棋盘上放置分别标有数字1，2,3,4,5,6,7,8的八张牌，确定初始状态和目标状态。可使用的算符有空格左移、空格上移、空格右移、空格下移，即它们只允许把位于空格左、上、右、下边的牌移入空格。要求寻找从初始状态到目标状态的路径。状态空间搜索状态空间的一般搜索过程：（1） 把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；（2） 检查OPEN表是否为空，若为空则问题无解，退出；（3） 把OPEN表的第一个节点取出放入CLOSE表，并记该节点为n；（4） 考察节点n是否为目标节点。若是，则求得了解，退出；（5） 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；（6） 针对M中子节点的不同情况，分别进行如下处理：a） 对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表;（不在OPEN表）b） 对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中）c） 对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针； （在CLOSE表中）（7） 按某种搜索策略对OPEN表中的节点进行排序；（8） 转第2步。广度优先搜索的基本思想：从初始节点S0开始，逐层地对节点进行扩展，并考察它是否为目标节点。在第n层的节点没有全部扩展并考察之前，不对第n+1层的节点进行扩展。OPEN表中节点总是按照进入的先后顺序排列，先进入的节点排在前面，后进入的排在后面。算法描述：（1）把初始节点S0放入OPEN表。如果OPEN表为空，则问题无解，退出。把OPEN表的第一个节点(记为节点n)取出放入CLOSE表。考察节点n是否为目标节点。若是，则求得了问题的解，退出。若节点n不可扩展，则转第2步。扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。A*搜索：如果一般搜索过程满足如下限制，则它就称为A*算法：⑴把OPEN表中的节点按估价函数：f(x)=g(x)+h(x)f(x)的值从小至大进行排序(一般搜索过程的第7步)。g(x)是从初始节点S0到节点x的路径的代价，g(x)是对g*(x)的估计，g(x)>0。h(x)是h*(x)的下界，即对所有的x均有：h(x)Wh*(x)。其中，g*(x)是从初始节点S0到节点x的最小代价；h*(x)是从节点x到目标节点的最小代价。算法描述：把初始节点S0放入OPEN表，并建立目前只包含S0的图，记为G；检查OPEN表是否为空，若为空则问题无解，退出；把OPEN表的第一个节点取出放入CLOSE表，并记该节点为n；（4） 考察节点n是否为目标节点。若是，则求得了问题的解，退出；（5） 扩展节点n，生成一组子节点。把其中不是节点n先辈的那些子节点记做集合M，并把这些子节点作为节点n的子节点加入G中；（6） 针对M中子节点的不同情况，分别进行如下处理：a） 对于那些未曾在G中出现过的M成员设置一个指向父节点（即节点n）的指针，并把它们放入OPEN表；（不在OPEN表）b） 对于那些先前已经在G中出现过的M成员，确定是否需要修改它指向父节点的指针；（在OPEN表中，对g（x）进行更新）c） 对于那些先前已在G中出现并且已经扩展了的M成员，确定是否需要修改其后继节点指向父节点的指针；（在CLOSE表中，对节点n子节点的子节点更新g（x））⑺对OPEN表中的节点按估价函数进行排序；（8）转第2步。实验内容（1） 编写程序，利用状态空间搜索解决重排九宫问题；（2） 分别采取广度优先搜索和A*算法实现，分析它们的优缺点，对比盲目搜索和启发式搜素。实验程序求解算法:publicclassMethod(publicstaticbooleanParity(inta[])(booleanparity=true;for(inti=0;i<a.length;i++){intk=i;for(intj=i+1;j<a.length;j++){if(a[k]>a[j]){k=j;}}if(k!=i){inttemp;temp=a[i];a[i]=a[k];a[k]=temp;parity=!parity;}}returnparity;}publicstaticbooleanisSolutionExist(intsrc[],intdest[],ints[][],intd[][] ){introw1=0,row2=0,clumn1=0,clumn2=0;booleanflag1,flag2;for(inti=0;i<3;i++){for(intj=0;j<3;j++){if(s[i][j]=0){row1=i;clumn1=j;}if(d[i][j]==0){row2=i;clumn2=j;}}}if((row1-row2+clumn1-clumn2)%2==0){flag1=true;}else{flag1=false;}if(Parity(src)==Parity(dest)){flag2=true;else(flag2=false;}if(flag1==flag2)(returntrue;}else(returnfalse;}}广度优先搜索节点数据结构：privatestaticclassNode(intdata[][];//状态introw;//0所在行intclumn;//0所在列Nodeparent;//父亲节点Node(intdata[][],Nodeparent,introw,intclumn)(this.data=data;this.parent=parent;this.row=row;this.clumn=clumn;}A*算法节点数据结构：privatestaticclassNode(intvalue; //估价函数的值intdiff=0;//当前节点到目标节点的最小代价intdepth=-1; //初始节点到当前节点的代价intdata[][];introw;intclumn;Nodeparent;)(Node(intdata[][],Nodeparent,introw,intclumn,intdepth,intdiff)(this.data=data;this.parent=parent;this.row=row;this.clumn=clumn;this.depth=depth;this.diff=diff;this.value=depth+diff;}}5.实验结果输入初始状态:输入日标状态:Cancel广度优先搜索结果：（红色标记为搜索路径）A*搜索结果：（红色标记为搜索路径）:结果分析：广度优先搜索：优点是只要问题有解，这种算法总可以得到解，而且得到的是最优解。缺点是盲目性较大，当日标节点距离初始节点较远时将会产生许多无用节点，搜索效率低。A*算法