启发式搜索-八数码问题VIP专享VIP免费

启发式搜索1.介绍八数码问题也称为九宫问题。在3×3的棋盘，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格（以数字0来表示），与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。2.使用启发式搜索算法求解8数码问题。1)A，A星算法采用估价函数，其中：是搜索树中结点的深度；为结点的数据库中错放的棋子个数；为结点的数据库中每个棋子与其目标位置之间的距离总和。2)宽度搜索采用f(i)为i的深度，深度搜索采用f(i)为i的深度的倒数。3.算法流程①把起始节点S放到OPEN表中，并计算节点S的；②如果OPEN是空表，则失败退出，无解；③从OPEN表中选择一个值最小的节点。如果有几个节点值相同，当其中有一个为目标节点时，则选择此目标节点；否则就选择其中任一个节点作为节点；④把节点从OPEN表中移出，并把它放入CLOSED的已扩展节点表中；⑤如果是个目标节点，则成功退出，求得一个解；⑥扩展节点，生成其全部后继节点。对于的每一个后继节点：计算；如果既不在OPEN表中，又不在CLOCED表中，则用估价函数把它添入OPEN表中。从加一指向其父节点的指针，以便一旦找到目标节点时记住一个解答路径；如果已在OPEN表或CLOSED表中，则比较刚刚对计算过的和前面计算过的该节点在表中的值。如果新的较小，则(I)以此新值取代旧值。(II)从指向，而不是指向他的父节点。(III)如果节点在CLOSED表中，则把它移回OPEN表中。⑦转向②，即GOTO②。4.估价函数计算一个节点的估价函数，可以分成两个部分：1、已经付出的代价（起始节点到当前节点）；2、将要付出的代价（当前节点到目标节点）。节点n的估价函数定义为从初始节点、经过n、到达目标节点的路径的最小代价的估计值，即=+。是从初始节点到达当前节点n的实际代价；是从节点n到目标节点的最佳路径的估计代价，体现出搜索过程中采用的启发式信息（背景知识），称之为启发函数。所占的比重越大，越趋向于宽度优先或等代价搜索；反之，的比重越大，表示启发性能就越强。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.#include"stdio.h"2.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->...