2-九宫重排

1实验二：九宫重排一、实验目的A*算法是人工智能领域最重要的启发式搜索算法之一，本实验通过九宫重排问题，强化学生对A*算法的理解与应用，为人工智能后续环节的课程奠定基础。二、问题描述给定九宫格的初始状态，要求在有限步的操作内，使其转化为目标状态，且所得到的解是代价最小解(即移动的步数最少)。如：三、基本要求输入：九宫格的初始状态和目标状态输出：重排的过程，即途径的状态四、实验结果#includeiostream.h#includetime.h#includestdio.h#includedos.h#includeconio.hstaticinttarget[9]={1,2,3,8,0,4,7,6,5};//classdefinitionclasseight_num{private:intnum[9];intnot_in_position_num;intdeapth;inteva_function;2public: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;3}//构造函数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;4}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]){for(inti=0;i9;i++)if(num[i]==0)break;if(i3)return0;else{num[i]=num[i-3];num[i-3]=0;return1;}}//空格向下移5intmove_down(intnum[9]){for(inti=0;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]){for(inti=0;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]){for(inti=0;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++)6{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){doubletime;clock_tStart,Finish;intmemery_used=0,step=0;intnum[9];intflag=0;//是否输入错误标志，1表示输入错误intbingo=0;//是否查找成功标志，1表示成功inti,j;coutPleaseinputthenumber(0fortheblank):\n;for(i=0;i9;i++){flag=0;cinnum[i];for(j=0;ji;j++)if(num[i]==num[j])7flag=1;if(num[i]0||num[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++;coutNowtheinitialnumbersare:\n;S.show();coutAndtheTargetis:\n;Target.show();if(!icansolve(num,target)){coutNoonecansolveit!\n;cini;return1;}Start=clock();eight_num*OK_leaf=&S,*leaf_start=&S,*new_8num,*p;while(OK_leaf!=NULL&&bingo!=1){OK_leaf=find_OK_leaf(leaf_start);if(*OK_leaf==Target){bingo=1;break;}p=OK_leaf-leaf_pre;OK_leaf-get_numbers_to(num);if(move_up(num)&&!existed(num,OK_leaf)){new_8num=neweight_num;new_8num-set_num(num);new_8num-parent=OK_leaf;new_8num-cul_para();new_8num-leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep-leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf-get_numbers_to(num);if(move_down(num)&&!existed(num,OK_leaf)){new_8num=neweight_num;new_8num-set_num(num);8new_8num-parent=OK_leaf;new_8num-cul_para();new_8num-leaf_pre=p;if(p==NULL)leaf_start=new_8num;elsep-leaf_next=new_8num;p=new_8num;memery_used++;}OK_leaf-get_numbers_to(num);if(move_left(num)&&!existed(num,OK_leaf)){new_8nu