八数码问题_启发搜索-白红宇

八数码问题_启发搜索

阅读量：5759 次

发布时间：2019-06-18

本文共 5712 字，大约阅读时间需要 19 分钟。

#include
     
      #include
      
       typedef struct  {    long parent;    long index;        int direction;//记录上一节点到当前节点空格移动方向    int Grid[9];//存储局面    int H;//启发函数值}State;State S,T;//起始态，目标态(目标态由评估函数决定好了)State OPEN[2048];//队列-----待考察的状态State CLOSE[2048];//--------考察过的状态int OPhead=0,OPtail=0,openlen=2048;int CLhead=0,CLtail=0,closelen=2048;long INDEX=0;//记录下标void readdata();int search();int Evaluate(State s);State Swap(State v,int Epindex,int Nindex);//交换两个位置上的值int Judge(State father,int n,int BlankIndex,int NumIndex);void AI_Inspire();void addtoopen(State v);//将节点v加到队列尾State takeoutofopen();//取队列头数据void addtoclose(State v);int main(){        readdata();//读取起始状态   int flag=search();     int kk;   if(flag==1)//找到了,输出CLOSE表中的考察过的状态   {      for(kk=CLhead;kk
       
        =CLhead;i--)       {           if(End.parent ==CLOSE[i].index)           {                Process[k++]=CLOSE[i];                End=CLOSE[i];           }                }      for(j=k-1;j>=0;j--)//输出从起点到终点的局面变化过程      {             printf("第%d个状态: ",k-1-j);           for(int jj=0;jj<9;jj++)               printf(" %d",Process[j].Grid[jj]);           printf("\n");       }*/   }   else             printf("未找到\n");   return 0;}int search(){    State father;        while(OPhead != OPtail)//OPEN[]表中还有待考察的数据    {       int BlankIndex,NumIndex;       father = takeoutofopen();//从队列头取数据       addtoclose(father);//将father节点加入CLOSE表(已考察)       for(int k=0;k<9;k++)          if(father.Grid[k]==0)          {  BlankIndex=k; break;  } //记录父节点father空格位所在的位置                    //四个方向搜索//           //空格向左移       if(father.direction !=3)       {           NumIndex=BlankIndex/3*3+BlankIndex%3-1;                  if(BlankIndex%3-1>=0)           {                       int flag=Judge(father,1,BlankIndex,NumIndex);               if(flag==1) return 1;           }       }       //空格向上移       if(father.direction !=4)       {           NumIndex=(BlankIndex/3-1)*3+BlankIndex%3;//计算待移动的数据所在的位置           if(BlankIndex/3-1>=0)           {                    int flag=Judge(father,2,BlankIndex,NumIndex);               if(flag==1) return 1;                  }       }       //空格向右移       if(father.direction !=1)       {           NumIndex=BlankIndex/3*3+BlankIndex%3+1;                  if(BlankIndex%3+1<3)           {               int flag=Judge(father,3,BlankIndex,NumIndex);               if(flag==1) return 1;            }       }       //空格向下移       if(father.direction !=2)       {           NumIndex=(BlankIndex/3+1)*3+BlankIndex%3;           if(BlankIndex/3+1<3)           {                             int flag=Judge(father,4,BlankIndex,NumIndex);               if(flag==1) return 1;             }       }        AI_Inspire();//调整OPEN标           }    return 0;}void AI_Inspire(){       //按启发函数值对OPEN表中的元素进行排序----降序       State temp[2048];       int t=0;       int ii,jj;       //取出       if(OPtail
        
         = temp[kk].H) //正确位码的个数大的放在队列的最前面，优先展开                  kk=jj;                          State tp=temp[ii];           temp[ii]=temp[kk];           temp[kk]=tp;       }       //printf("%d---",temp[0].H);//调试       //放回       t=0;       if(OPtail
         
          son    son.H=Evaluate(son);//4.子节点的启发函数值    if(son.H==T.H)     {               son.index =INDEX++;         addtoclose(son);         return 1; //表明找到了终点        }    else     {   son.index =INDEX++;  //2.子节点自己的下标---father.index*4+n以指数形式增长，会超出long的范围(不能用)        addtoopen(son);//将当前状态节点加入到OPEN表                   }    return 0;}void addtoopen(State v){    OPEN[OPtail++]=v; //向尾部添加节点     OPtail = OPtail%openlen;}State takeoutofopen()//从队列头取节点数据{    State v;    v=OPEN[OPhead++];//向头部取节点    OPhead=OPhead%openlen;    return v;}void addtoclose(State v){    CLOSE[CLtail++]=v;        CLtail = CLtail%closelen;}//v为传入的局面，BlankIndex为空格位置,NumIndex为被交换的数据位置State Swap(State son,int BlankIndex,int NumIndex){    int temp=son.Grid[BlankIndex];//取空格位置的数字    son.Grid[BlankIndex]=son.Grid[NumIndex];    son.Grid[NumIndex]=temp;    return son;//返回新局面}int Evaluate(State s)//启发式函数{   int count=0;//正确位码的个数   for(int i=0;i<9;i++)   {          if(s.Grid[i]==T.Grid[i] && s.Grid[i]!=0)           count++;   }   return count;//返回逆序值}void readdata(){    int Arr[10]={
   8,7,6,5,4,3,2,1,0};    int Brr[10]={
   0,1,2,3,4,5,6,7,8};    //28步    //终止局面    T.index=-1;//1    T.parent=-1;//2    for(int i=0;i<9;i++)//4        T.Grid[i]=Arr[i];        T.H=Evaluate(T);//5    //起始局面    S.index=INDEX++;    S.parent=-1;    for(i=0;i<9;i++)        S.Grid[i]=Brr[i];    S.H=Evaluate(S);//起始局面评估    addtoopen(S); }