启发式搜索-八数码问题

启发式搜索1.介绍八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2.使用启发式搜索算法求解8数码问题。1)A，A星算法采用估价函数wnfndnpn，其中：dn是搜索树中结点n的深度；wn为结点n的数据库中错放的棋子个数；pn为结点n的数据库中每个棋子与其目标位置之间的距离总和。2)宽度搜索采用f(i)为i的深度，深度搜索采用f(i)为i的深度的倒数。3.算法流程①把起始节点S放到OPEN表中，并计算节点S的)(Sf；②如果OPEN是空表，则失败退出，无解；③从OPEN表中选择一个f值最小的节点i。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点i；④把节点i从OPEN表中移出，并把它放入CLOSED的已扩展节点表中；⑤如果i是个目标节点，则成功退出，求得一个解；⑥扩展节点i，生成其全部后继节点。对于i的每一个后继节点j：计算)(jf；如果j既不在OPEN表中，又不在CLOCED表中，则用估价函数f把它添入OPEN表中。从j加一指向其父节点i的指针，以便一旦找到目标节点时记住一个解答路径；如果j已在OPEN表或CLOSED表中，则比较刚刚对j计算过的f和前面计算过的该节点在表中的f值。如果新的f较小，则(I)以此新值取代旧值。(II)从j指向i，而不是指向他的父节点。(III)如果节点j在CLOSED表中，则把它移回OPEN表中。⑦转向②，即GOTO②。4.估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价（起始节点到当前节点）；2、将要付出的代价（当前节点到目标节点）。节点n的估价函数)(nf定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即)(*nf=)(*ng+)(*nh。)(*ng是从初始节点到达当前节点n的实际代价；)(*nh是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。)(*ng所占的比重越大，越趋向于宽度优先或等代价搜索；反之，)(*nh的比重越大，表示启发性能就越强。5.实验代码为方便起见，目标棋局为不变(1)以下代码估价函数为深度+错放棋子个数(2)若估价函数为深度+每个棋子与其目标位置之间的距离总和，则加入估价函数intcalvalue1(inta[])//不在位棋子数{intc=0;intb=0;for(inti=0;i=8;i++)for(intj=0;j=8;j++)if(a[i]=goal[j])if(goal[j]!=0)c=c+abs(i%3-j%3)+abs((i-i%3)/3+(j-j%3)/3);returnc;}(3)宽度搜索采用OPEN-jiedian.f=depth;(4)深度搜索采用OPEN-jiedian.f=-depth;源代码：1.#includestdio.h2.3.intgoal[9]={1,2,3,8,0,4,7,6,5},sgoal[9];//goal为棋盘的目标布局,并用中间状态sgoal与之比较4.5.structBoard6.{7.intshuzu[9];8.intd,f,e;//d:深度;f:启发函数;e:记录前一次的扩展节点9.};10.11.structNodeLink12.{13.Boardjiedian;14.NodeLink*parent;15.NodeLink*previous;16.NodeLink*next;17.NodeLink*path;18.};19.//更新纪录八数码的状态20.voidsetboard(inta[],intb[],intflag)//flag=0,写棋子;flag=1,写棋盘21.{22.for(inti=0;i=8;i++)23.if(flag)24.a[b[i]]=i;25.else26.b[a[i]]=i;27.}28.//计算启发值的函数29.intcalvalue(inta[])//不在位棋子数30.{31.intc=0;32.for(inti=0;i=8;i++)33.if(a[i]!=goal[i])34.if(goal[i]!=0)35.c++;36.returnc;37.}38.//生成一个新节点的函数39.NodeLink*newnode(NodeLink*TEM,intdepth,intflag)40.{41.NodeLink*temp=newNodeLink;42.for(inti=0;i=8;i++)43.temp-jiedian.shuzu[i]=TEM-jiedian.shuzu[i];44.switch(flag)45.{46.case1:47.{48.temp-jiedian.shuzu[0]--;49.temp-jiedian.shuzu[sgoal[temp-jiedian.shuzu[0]]]++;//向左移50.break;51.}52.case2:53.{54.temp-jiedian.shuzu[0]++;55.temp-jiedian.shuzu[sgoal[temp-jiedian.shuzu[0]]]--;//向右移56.break;57.}58.case3:59.{60.temp-jiedian.shuzu[0]-=3;61.temp-jiedian.shuzu[sgoal[temp-jiedian.shuzu[0]]]+=3;//向上移62.break;63.}64.case4:65.{66.temp-jiedian.shuzu[0]+=3;67.temp-jiedian.shuzu[sgoal[temp-jiedian.shuzu[0]]]-=3;//向下移68.break;69.}70.}71.temp-jiedian.d=depth+1;72.setboard(sgoal,temp-jiedian.shuzu,1);73.temp-jiedian.f=temp-jiedian.d+calvalue(sgoal);74.temp-jiedian.e=flag;75.temp-parent=TEM;76.returntemp;77.}78.//把新节点加入OPEN队列79.NodeLink*addnode(NodeLink*head,NodeLink*node)//把node插入到head链中80.{81.NodeLink*TEM;82.TEM=head;83.head=node;84.head-next=TEM;85.head-previous=NULL;86.if(TEM)87.TEM-previous=head;//TEM已为空,无需操作88.returnhead;89.}90.91.//求启发值最小的结点92.NodeLink*minf(NodeLink*head)93.{94.NodeLink*min,*forward;95.min=head;96.forward=head;97.while(forward)98.{99.if(min-jiedian.fforward-jiedian.f)100.min=forward;101.forward=forward-next;102.}103.returnmin;104.}105.106.intmain()107.{108.intdepth=0;109.intsource[9];110.inti,j;111.112.NodeLink*OPEN=newNodeLink;113.NodeLink*TEMP,*TEM;114.115.printf(请输入初始状态：\n);116.for(i=0;i9;i++)117.scanf_s(%d,&source[i]);118.119.setboard(source,OPEN-jiedian.shuzu,0);120.OPEN-jiedian.d=depth;121.OPEN-jiedian.e=0;122.OPEN-jiedian.f=depth+calvalue(source);123.OPEN-next=NULL;124.OPEN-previous=NULL;125.OPEN-parent=NULL;126.127.while(OPEN)128.{129.TEMP=minf(OPEN);//求具有最小启发值的节点130.setboard(sgoal,TEMP-jiedian.shuzu,1);//写棋盘131.if(!calvalue(sgoal))132.break;133.if(TEMP!=OPEN)//如果不是第一个节点134.{135.TEMP-previous-next=TEMP-next;136.TEMP-next-previous=TEMP-previous;137.}138.else//是第一个节点139.{140.if(OPEN-next)//如果还有节点141.{142.OPEN=OPEN-next;143.OPEN-previous=NULL;144.}145.elseOPEN=NULL;//否则置为空146.}147.148.if(TEMP-jiedian.shuzu[0]-1=0&&TEMP-jiedian.e!=2)//防止棋子回到原状态149.OPEN=addnode(OPEN,newnode(TEMP,depth,1));150.if(TEMP-jiedian.shuzu[0]+1=8&&TEMP-jiedian.e!=1)151.OPEN=addnode(OPEN,newnode(TEMP,depth,2));152.if(TEMP-jiedian.shuzu[0]-3=0&&TEMP-jiedian.e!=4)153.OPEN=addnode(OPEN,newnode(TEMP,depth,3));154.if(TEMP-jiedian.shuzu[0]+3=8&&TEMP-jiedian.e!=3)155.OPEN=addnode(OPEN,newnode(TEMP,depth,4));156.depth++;157.}158.159.if(OPEN)//如有解,则打印出解的步骤160.{161.TEMP-path=NULL;162.while(TEMP-parent)//每次回溯父节点，生成路径163.{164.TEMP-parent-path=TEMP;165.TEMP=TEMP-parent;166.}167.j=0;168.while(TEMP-path)169.{170.setboard(sgoal,TEMP-jiedian.shuzu,1);171.printf(第%d步：\n,j);172.for(i=0;i=2;i++)173.printf(%d,sgoal[i]);174.printf(\n);175.for(i=3;i=5;i++)176.printf(%d,sgoal[i]);177.printf(\n);178.for(i=6;i=8;i++)179.printf(%d,sgoal[i]);180.printf(\n);181.TEMP=TEMP-path;182.j++;183.}184.setboard(sgoal,TEMP-jiedian.shuzu,1);185.printf(第%d步：\n,