啟發(fā)式搜索解決八數(shù)碼問題

#include<stdlib.h>#include<stdio.h>#include<math.h>typedefstructNode{//節(jié)點結(jié)構(gòu)體intdata[9];doublef,g;structNode*parent;}Node,*Lnode;typedefstructStack{//OPENCLOSED表結(jié)構(gòu)體Node*npoint;structStack*next;}Stack,*Lstack;Node*Minf(Lstack*Open){//選取OPEN表上f值最小的節(jié)點，返回該節(jié)點地址Lstacktemp=(*Open)->next,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){//判斷是否可解inta=0,b=0,i,j;for(i=1;i<9;i++)for(j=0;j<i;j++){if((suc->data[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){//判斷節(jié)點是否相等，相等，不相等for(inti=0;i<9;i++)if(suc->data[i]!=goal->data[i])return0;return1;}Node*Belong(Node*suc,Lstack*list){//判斷節(jié)點是否屬于OPEN表或CLOSED表，是則返回節(jié)點地址，否則返回空地址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){//把節(jié)點放入OPEN或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++)h=h+Distance(suc,goal,i);returnh*speed+suc.g;//f=h+g;(speed值增加時搜索過程以找到目標(biāo)為優(yōu)先因此可能不會返回最優(yōu)解)}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值部分-結(jié)束/////////////////////////////////////////////////////擴展后繼節(jié)點部分的函數(shù)-開始/////////////////intBelongProgram(Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed){//判斷子節(jié)點是否屬于OPEN^CLOSED表并作出相應(yīng)的處理Node*temp=NULL;intflag=0;if((Belong(*suc,Open)!=NULL)||(Belong(*suc,Closed)!=NULL)){if(Belong(*suc,Open)!=NULL)temp=Belong(*suc,Open);elsetemp=Belong(*suc,Closed);if(((*suc)->g)<(temp->g)){temp->parent=(*suc)->parent;temp->g=(*suc)->g;temp->f=(*suc)->f;flag=1;}}else{Putinto(*suc,Open);(*suc)->f=Fvalue(**suc,goal,speed);}returnflag;}intCanspread(Nodesuc,intn){//判斷空格可否向該方向移動，，，表示空格向上向下向左向右移inti,flag=0;for(i=0;i<9;i++)if(suc.data[i]==0)break;switch(n){case1:if(i/3!=0)flag=1;break;case2:if(i/3!=2)flag=1;break;case3:if(i%3!=0)flag=1;break;case4:if(i%3!=2)flag=1;break;default:break;}returnflag;}voidSpreadchild(Node*child,intn){//擴展child節(jié)點的字節(jié)點n表示方向，，，表示空格向上向下向左向右移inti,loc,temp;for(i=0;i<9;i++)child->data[i]=child->parent->data[i];for(i=0;i<9;i++)if(child->data[i]==0)break;if(n==0)loc=i%3+(i/3-1)*3;elseif(n==1)loc=i%3+(i/3+1)*3;elseif(n==2)loc=i%3-1+(i/3)*3;elseloc=i%3+1+(i/3)*3;temp=child->data[loc];child->data[i]=temp;child->data[loc]=0;}voidSpread(Lnode*suc,Lstack*Open,Lstack*Closed,Nodegoal,floatspeed){//擴展后繼節(jié)點總函數(shù)inti;Node*child;for(i=0;i<4;i++){if(Canspread(**suc,i+1))//判斷某個方向上的子節(jié)點可否擴展{child=(Node*)malloc(sizeof(Node));//擴展子節(jié)點child->g=(*suc)->g+1;//算子節(jié)點的g值child->parent=(*suc);//子節(jié)點父指針指向父節(jié)點Spreadchild(child,i);//向該方向移動空格生成子節(jié)點if(BelongProgram(&child,Open,Closed,goal,speed))//判斷子節(jié)點是否屬于OPEN或CLOSED表并作出相應(yīng)的處理free(child);///////////////////////擴展后繼節(jié)點部分的函數(shù)-結(jié)束//////////////////////////////////Closed,floatspeed)//判斷OPEN表是否為//從OPEN表中取出f//將節(jié)點放入//如果當(dāng)前節(jié)點是目//當(dāng)前節(jié)點不是目標(biāo)Node*Process(Lnode*org,Lnode*goal,Closed,floatspeed)//判斷OPEN表是否為//從OPEN表中取出f//將節(jié)點放入//如果當(dāng)前節(jié)點是目//當(dāng)前節(jié)點不是目標(biāo)while(1){if((*Open)->next==NULL)returnNULL;空，為空則失敗退出Node*minf=Minf(Open);值最小的節(jié)點Putinto(minf,Closed);CLOSED表中if(Equal(minf,*goal))returnminf;標(biāo)節(jié)點，則成功退出Spread(&minf,Open,Closed,**goal,speed);節(jié)點時擴展當(dāng)前節(jié)點的后繼節(jié)點}}intShownum(Node*result){//遞歸顯示從初始狀態(tài)到達目標(biāo)狀態(tài)的移動方法if(result==NULL)return0;else{intn=Shownum(result->parent);for(inti=0;i<3;i++){printf(〃\n〃)；for(intj=0;j<3;j++){if(result->data[i*3+j]!=0)printf("%d〃,result-〉data[i*3+j]);elseprintf("");}}printf(〃\n〃)；returnn+1;}}voidCheckinput(Node*suc){//檢查輸入inti=0,j=0,flag=0;charc;while(i<9){while(((c=getchar())!=10)){if(c==''){if(flag>=0)flag=0;}elseif(c>='0'&&c<='8'){if(flag==0){suc->data[i]=(c-'0');flag=1;for(j=0;j<i;j++)if(suc->data[j]==suc->data[i])flag=-2;i++;}elseif(flag>=0)flag=-1;}elseif(flag>=0)flag=-1;}if(flag<0||i<9){if(flag<0){if(flag==-1)printf("含有非法字符或數(shù)字!\n請重新輸入:\n〃)；elseif(flag==-2)printf("輸入的數(shù)字有重復(fù)!\n請重新輸入:\n〃)；}elseif(i<9)printf("輸入的有效數(shù)字不夠!\n請重新輸入:\n〃)；i=0;flag=0;}}}voidmain(){//主函數(shù)//初始操作，建立open和closed表LstackOpen=(Stack*)malloc(sizeof(Stack));Open->next=NULL;LstackClosed=(Stack*)malloc(sizeof(Stack));Closed->next=NULL;Node*org=(Node*)malloc(sizeof(Node));org->parent=NULL;//初始狀態(tài)節(jié)點org->f=1;org->g=1;Node*goal=(Node*)malloc(sizeof(Node));//目標(biāo)狀態(tài)節(jié)點Node*result;floatspeed=1;//speed搜索速度charc;printf(〃=================================\n〃)；printf(-說明:狀態(tài)矩陣由0-8九個數(shù)字表示,\n請依次按照九宮格上的行列順序輸入,每個數(shù)字間用空格隔開。\n〃)；printf(〃=================================\n〃)；printf(-請輸入初始狀態(tài)(0-89個數(shù)字以空格隔開回車表示輸入結(jié)束):\n");Checkinput(org);printf(-請輸入目標(biāo)狀態(tài)(0-89個數(shù)字以空格隔開回車表示輸入結(jié)束):\n");Checkinput(goal);if(Canslove(org,goal)){//A*算法開始，先將初始狀態(tài)放入OPEN表printf("請輸入搜索速度(速度越高越無法保證結(jié)果是最優(yōu)解)：〃)；scanf(〃％f〃,&speed);while((c=getchar())!=10);printf(-搜索中，請耐