资源描述：
《启发式搜索解决八数码问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、#include#include#includetypedefstructNode{//节点结构体intdata[9];doublef,g;structNode*parent;}Node,*Lnode;typedefstructStack{//OPENCLOSED表结构体Node*npoint;structStack*next;}Stack,*Lstack;Node*Minf(Lstack*Open){//选取OPEN表上f值最小的节点，返回该节点地址Lstacktemp=(*Open)->next,
2、min=(*Open)->next,minp=(*Open);Node*minx;while(temp->next!=NULL){if((temp->next->npoint->f)<(min->npoint->f)){min=temp->next;minp=temp;}temp=temp->next;}minx=min->npoint;temp=minp->next;minp->next=minp->next->next;free(temp);returnminx;}intCanslove(Node*suc,Node*goal){//判断是否可解int
3、a=0,b=0,i,j;for(i=1;i<9;i++)for(j=0;jdata[i]>suc->data[j])&&suc->data[j]!=0)a++;if((goal->data[i]>goal->data[j])&&goal->data[j]!=0)b++;}if(a%2==b%2)return1;elsereturn0;}intEqual(Node*suc,Node*goal){//判断节点是否相等，相等，不相等for(inti=0;i<9;i++)if(suc->data[i]!=goal->data[i
4、])return0;return1;}Node*Belong(Node*suc,Lstack*list){//判断节点是否属于OPEN表或CLOSED表，是则返回节点地址，否则返回空地址Lstacktemp=(*list)->next;if(temp==NULL)returnNULL;while(temp!=NULL){if(Equal(suc,temp->npoint))returntemp->npoint;temp=temp->next;}returnNULL;}voidPutinto(Node*suc,Lstack*list){//把节点放入OPE
5、N或CLOSED表中Stack*temp;temp=(Stack*)malloc(sizeof(Stack));temp->npoint=suc;temp->next=(*list)->next;(*list)->next=temp;}///////////////计算f值部分-开始//////////////////////////////doubleFvalue(Nodesuc,Nodegoal,floatspeed){//计算f值doubleDistance(Node,Node,int);doubleh=0;for(inti=1;i<=8;i++)
6、h=h+Distance(suc,goal,i);returnh*speed+suc.g;//f=h+g;(speed值增加时搜索过程以找到目标为优先因此可能不会返回最优解)}doubleDistance(Nodesuc,Nodegoal,inti){//计算方格的错位距离intk,h1,h2;for(k=0;k<9;k++){if(suc.data[k]==i)h1=k;if(goal.data[k]==i)h2=k;}returndouble(fabs(h1/3-h2/3)+fabs(h1%3-h2%3));}///////////////计算f值部
7、分-结束/////////////////////////////////////////////////////扩展后继节点部分的函数-开始/////////////////intBelongProgram(Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed){//判断子节点是否属于OPEN或CLOSED表并作出相应的处理Node*temp=NULL;intflag=0;if((Belong(*suc,Open)!=NULL)
8、
9、(Belong(*suc,Closed)!=NULL)){if(
10、Belong(*suc,Open)!=NULL)temp=Belong(*suc
