banshuma.cpp

八数码问题 带启发式的搜索 非常好的人工智能学习实例

#include"stdio.h" 
#include"conio.h"
#include"stdlib.h"
  
    
  struct   node{   
    int   nodesun[3][3];   
    int   high;   
    int   pre;   
    int   flag;   
    int   value;   
    int   x,y;   
    int   prestep;   
  }queue[2040];   
    
    
  int   zx[4]={-1,0,1,0};   
  int   zy[4]={0,-1,0,1};   
  int   top;   
  int   desti[3][3];   
    
  int   detect(struct   node   *p)   
  {int   i,j;   
      for(i=0;i<3;i++)   
            for(j=0;j<3;j++)   
              if(p->nodesun[i][j]!=desti[i][j])   
              return   0;   
      return   1;   
  }   
    
  int   update(struct   node   *p)   
  {int   i,j,k,m;   
    for(k=1;k<top;k++)   
      {m=0;   
        for(i=0;i<3;i++)   
          for(j=0;j<3;j++)   
              if(p->nodesun[i][j]==queue[k].nodesun[i][j])     m++;   
        if(m==9)   return   1;   
      }   
      return   0;   
  }   
    
    
  void   printlj()   
  {int   tempt;   
    int   i,j,step;   
    step=0;   
    tempt=top;   
    printf("\n-----------------   \n     step   by   step   :\n-----------------\n");   
    printf("-----------------\n");   
  while(tempt!=0)   
    {     for(i=0;i<3;i++)   
            for(j=0;j<3;j++)   
      {printf("%d",queue[tempt].nodesun[i][j]);   
                printf("   ");   
                if(j==2)   
                printf("\n");   
              }   
  step++;   
  printf("-----------------\n");   
  getch();   
          tempt=queue[tempt].pre;   
    }   
    printf("%d   steps",--step);   
  }   
    
  int   VALUE(struct   node   *p)   
  {int   count=0;   
    int   i,j;   
    for(i=0;i<3;i++)   
            for(j=0;j<3;j++)   
                if(p->nodesun[i][j]!=desti[i][j])   
      count++;   
    count=count+p->high;   
    return   count;   
  }   
    
  int   check(struct   node   *p,int   prenode)   
  {int   i,j,k,m,n;   
  if(queue[prenode].prestep==0)   
        return   1;   
  n=queue[prenode].prestep+2;   
  if(n>=4)   
        n=n-4;   
  if(p->prestep==n)   
        return   0;   
  return   1;   
  }   
    
  void   main()   
  {   
      int   i,j,m,n,f,prestep;   
      int   min;   
      int   temp,find,minnumber,first;   
      system("cls");  
      find=0;   
      top=1;   
    
    for(i=0;i<3;i++)   
              {printf("input   %drd   rows\n",i+1);   
                scanf("%d   %d   %d",&queue[1].nodesun[i][0],&queue[1].nodesun[i][1],&queue[1].nodesun[i][2]);   
        }   
    
    for(i=0;i<3;i++)   
  for(j=0;j<3;j++)   
    if(queue[1].nodesun[i][j]==0)   {   queue[1].x=i;   
    queue[1].y=j;   
                                                                                    break;   
                                                                                }   
    
  first=1;   
  for(i=0;i<3;i++)   
            for(j=0;j<3;j++)   
      {   
  desti[i][j]=first;   
  first++;   
      }   
  desti[2][2]=0;   
    
    queue[1].high=1;   
    queue[1].value=VALUE(&queue[1]);   
    queue[1].pre=0;   
    queue[1].flag=0;   
    queue[1].prestep=0;   
    
    
  while(!find&&top>0)   
    {   min=1000;   
        for(i=1;i<=top;i++)   
            if(queue[i].value<min&&queue[i].flag==0)   
              {   
  min=queue[i].value;   
  minnumber=i;   
              }   
        queue[minnumber].flag=1;   
    
      for(f=0;f<4;f++)   
        {   
          m=queue[minnumber].x;   
          n=queue[minnumber].y;   
          i=m+zx[f];   
          j=n+zy[f];   
    
          if(i>=0&&i<=2&&j>=0&&j<=2)   
              {   
                top++;   
                queue[top]=queue[minnumber];   
                queue[top].nodesun[m][n]=queue[minnumber].nodesun[i][j];   
                queue[top].nodesun[i][j]=0;   
    
                queue[top].x=i;   
                queue[top].y=j;   
                queue[top].pre=minnumber;   
                queue[top].high=queue[minnumber].high+1;   
                queue[top].value=VALUE(&queue[top]);   
                queue[top].flag=0;   
                queue[top].prestep=f;   
                if(check(&queue[top],minnumber)==0||update(&queue[top]))   
                                  {   
                      top--;   
      continue;   
                                                                                                                }   
    
                if(detect(&queue[top]))   
    {   
      printlj();   
                      find=1;   
                      break;   
                    }   
    
              }   
    
        }   
    
    }   
    
    printf("\ntotal   generate   %d   nodes",top);   
    getch();   
    
  }