西安交大 人工智能 重排九宫格实验报告

人工智能实验报告--重排九宫学生姓名石磊专业/班级计算机26学号2120505140一．问题描述在3*3的方格棋盘上放置分别标有数字1,2,3,4,5,6,7,8的8张牌，初始状态为s0，目标状态为sg，可使用的算符有空格左移，空格上移，空格右移和空格下移，即它们只允许把位于空格左，上，右，下边的牌移入空格。要求寻找从初始状态到目的状态的路径。二．算法描述（1）把初始节点S0放入OPEN表。（2）如果OPEN表为空，则问题无解，退出。（3）把OPEN表的第一个节点取出放入CLOSE表（记为节点n）。（4）考察节点n是否为目标节点。若是，则求得了问题的解，退出。（5）若节点n不可扩展，则转第2步。（6）扩展节点n，将其子节点放入OPEN表的尾部，并为每一个子节点都配置指向父节点的指针，然后转第2步。（2）三.实验结果四.实验结果分析应用广度优先搜索可得到如上图所示的从初始状态到目标状态的路径。广度优先搜索盲目性较大，当目标节点距初始节点较远时将会产生许多无用节点，搜索效率低。但只要问题有解，用广度优先搜索总可以得到解，而且得到的是路径最短的解。五．源代码#includeiostream#includectime#includecstdio#includedos.h#includeconio.h#includefstreamusingnamespacestd;inttarget[9]={0};//classdefinitionclasseight_num{private:intnum[9];intnot_in_position_num;intdeapth;inteva_function;public:eight_num*parent;eight_num*leaf_next;eight_num*leaf_pre;eight_num(intinit_num[9]);eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){num[0]=num1;num[1]=num2;num[2]=num3;num[3]=num4;num[4]=num5;num[5]=num6;num[6]=num7;num[7]=num8;num[8]=num9;}eight_num(void){for(inti=0;i9;i++)num[i]=i;}voidcul_para(void);voidget_numbers_to(intother_num[9]);intget_nipn(void){returnnot_in_position_num;}intget_deapth(void){returndeapth;}intget_evafun(void){returneva_function;}voidset_num(intother_num[9]);voidshow(void);eight_num&operator=(eight_num&);eight_num&operator=(intother_num[9]);intoperator==(eight_num&);intoperator==(intother_num[9]);};//计算启发函数g(n)的值voideight_num::cul_para(void){inti;inttemp_nipn=0;for(i=0;i9;i++)if(num[i]!=target[i])temp_nipn++;not_in_position_num=temp_nipn;if(this-parent==NULL)deapth=0;elsedeapth=this-parent-deapth+1;eva_function=not_in_position_num+deapth;}//构造函数1eight_num::eight_num(intinit_num[9]){for(inti=0;i9;i++)num[i]=init_num[i];}//显示当前节点的状态voideight_num::show(){coutnum[0];cout;coutnum[1];cout;coutnum[2];cout\n;coutnum[3];cout;coutnum[4];cout;coutnum[5];cout\n;coutnum[6];cout;coutnum[7];cout;coutnum[8];cout\n;}//复制当前节点状态到一个另数组中voideight_num::get_numbers_to(intother_num[9]){for(inti=0;i9;i++)other_num[i]=num[i];}//设置当前节点状态(欲设置的状态记录的other数组中)voideight_num::set_num(intother_num[9]){for(inti=0;i9;i++)num[i]=other_num[i];}eight_num&eight_num::operator=(eight_num&another_8num){for(inti=0;i9;i++)num[i]=another_8num.num[i];not_in_position_num=another_8num.not_in_position_num;deapth=another_8num.deapth+1;eva_function=not_in_position_num+deapth;return*this;}eight_num&eight_num::operator=(intother_num[9]){for(inti=0;i9;i++)num[i]=other_num[i];return*this;}inteight_num::operator==(eight_num&another_8num){intmatch=1;for(inti=0;i9;i++)if(num[i]!=another_8num.num[i]){match=0;break;}if(match==0)return0;elsereturn1;}inteight_num::operator==(intother_num[9]){intmatch=1;for(inti=0;i9;i++)if(num[i]!=other_num[i]){match=0;break;}if(match==0)return0;elsereturn1;}//classdefinitionover//空格向上移intmove_up(intnum[9]){inti=0;for(;i9;i++)if(num[i]==0)break;if(i3)return0;else{num[i]=num[i-3];num[i-3]=0;return1;}}//空格向下移intmove_down(intnum[9]){inti=0;for(;i9;i++)if(num[i]==0)break;if(i5)return0;else{num[i]=num[i+3];num[i+3]=0;return1;}}//空格向左移intmove_left(intnum[9]){inti=0;for(;i9;i++)if(num[i]==0)break;if(i==0||i==3||i==6)return0;else{num[i]=num[i-1];num[i-1]=0;return1;}}//空格向右移intmove_right(intnum[9]){inti=0;for(;i9;i++)if(num[i]==0)break;if(i==2||i==5||i==8)return0;else{num[i]=num[i+1];num[i+1]=0;return1;}}//判断可否解出inticansolve(intnum[9],inttarget[9]){inti,j;intcount_num,count_target;for(i=0;i9;i++)for(j=0;ji;j++){if(num[j]num[i]&&num[j]!=0)count_num++;if(target[j]target[i]&&target[j]!=0)count_target++;}if((count_num+count_target)%2==0)return1;elsereturn0;}//判断有无重复intexisted(intnum[9],eight_num*where){eight_num*p;for(p=where;p!=NULL;p=p-parent)if(*p==num)return1;return0;}//寻找估价函数最小的叶子节点eight_num*find_OK_leaf(eight_num*start){eight_num*p,*OK;p=OK=start;intmin=start-get_evafun();for(p=start;p!=NULL;p=p-leaf_next)if(minp-get_evafun()){OK=p;min=p-get_evafun();}returnOK;}//主函数开始intmain(void){//ifstreamcin(shilei3.txt);doubletime;clock_tStart,Finish;intmemery_used=0,step=0;intnum[9];intflag=0;//是否输入错误标志，1表示输入错误intbingo=0;//是否查找成功标志，1表示成功inti,j;cout请输入初始状态\n;for(i=0;i9;i++){flag=0;cinnum[i];for(j=0;ji;j++)if(num[i]==num[j])flag=1;if(num[i]0||num[i]8||flag==1){i--;coutIlleglenumber!\tReinput!\n;}}cout请输出目标状态\n;for(i=0;i9;i++){flag=0;cintarget[i];for(j=0;ji;j++)if(target[i]==target[j])flag=1;if(target[i]0||target[i]8||flag==1){i--;coutIlleglenumber!\tReinput!\n;}}eight_numS(num),Target(target);S.parent=S.leaf_next=S.leaf_pre=NULL;S.cul_para();memery_used++;cout初始状态是:\n;S.show();cout目标状态是:\n;Target.show();cout==========================\n;cout==========================\n;cout==========================\n;cout=====开始进行运算！=======\n;cout==========================\n;cout==========================\n;cout==========================\n;if(!icansolve(num,target)){cout\n;cout没有解决办法！\n;return1;}cout\n;Target.show();Start=clock();eight_num*OK_leaf=&S,*leaf_start=&S,*new_8num,*p;while(OK_leaf!=NULL&&bi