相信大家都玩過"滑塊拼圖"游戲!
  大概說一下 :假如一副圖是由幾個部分拼湊成的,現(xiàn)在要你把這些散塊拼湊成一副完整的圖片
              也可以是幾個數(shù)字來拼湊
  比如 3*3的格子
        1 2 3
        4 5 6
        7 8     (相當于原始矩陣)
有一個格子是空的現(xiàn)在要你組合成
     1 2 7
     3 6 4
     5 8          (目標矩陣)
問題是編寫一種算法 能根據(jù)輸入的原始圖形(矩陣)拼湊成目標圖形(目標矩陣) 要求是步數(shù)最少(耗時間最少)
  #include"iostream.h"
struct node{
int nodesun[4][4];

int x,y;
}path[1000];
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
int top;
int desti[4][4];//目標狀態(tài)
int detect(struct node *p)
{int i,j;
  for(i=1;i<4;i++)
     for(j=1;j<4;j++)
   if(p->nodesun[i][j]!=desti[i][j])
    return 0;
  return 1;
}

void printlj()
{int tempt;
int i,j;
tempt=1;
while(tempt<=top)
{    for(i=1;i<4;i++)
     for(j=1;j<4;j++)
  {cout<<path[tempt].nodesun[i][j];
   if(j==3)
    cout<<" "<<endl;
  }
  tempt++;
}
}

   
   

void main()
{ //初始化
  int i,j,m,n,f;
  int temp,find=0;
  top=1;
for(i=1;i<4;i++)
     for(j=1;j<4;j++)
  {cout<<"請輸入第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;
   cin>>temp;
   path[1].nodesun[i][j]=temp;
  }
  cout<<"請輸入初始狀態(tài)的空格的位置(行)"<<endl;
  cin>>temp;
  path[1].x=temp;
cout<<"請輸入初始狀態(tài)的空格的位置(列)"<<endl;
  cin>>temp;
  path[1].y=temp;
//目標狀態(tài)
for(i=1;i<4;i++)
     for(j=1;j<4;j++)
  {cout<<"請輸入目標狀態(tài)第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;
   cin>>temp;
   desti[i][j]=temp;
  }
  //深度優(yōu)先搜索
while(!find)
{ m=path[top].x;
  n=path[top].y ;
  for(f=0;f<4;f++)
  {i=m+zx[f];
   j=n+zy[f];
   if(i>=1&&i<=3&&j>=1&&j<=3)
   {top++;
    path[top]=path[top-1];
path[top].nodesun[m][n]=path[top-1].nodesun[i][j];
path[top].nodesun[i][j]=0;

path[top].x=i;
path[top].y=j;

   if(detect(&path[top]))
   {printlj();
   find=1;
   break;
   }

   break;
   }//if
  
  }//for
   
   }//while
}



#include"iostream.h"
struct node{
int nodesun[4][4];
int pre;
int x,y;
}path[400];
int zx[4]={-1,0,1,0};
int zy[4]={0,-1,0,1};
int front,rear;
int desti[4][4];//目標狀態(tài)
int detect(struct node *p)
{int i,j;
  for(i=1;i<4;i++)
     for(j=1;j<4;j++)
   if(p->nodesun[i][j]!=desti[i][j])
    return 0;
  return 1;
}

void printlj()
{int tempt;
int i,j;
tempt=rear;
while(tempt!=0)
{    for(i=1;i<4;i++)
     for(j=1;j<4;j++)
  {cout<<path[tempt].nodesun[i][j];
   if(j==3)
    cout<<" "<<endl;
  }
  tempt=path[tempt].pre;
}
}

   
   

void main()
{ //初始化
  int i,j,m,n,f;
  int temp,find=0;
  front=rear=1;
  path[1].pre=0;
for(i=1;i<4;i++)
     for(j=1;j<4;j++)
  {cout<<"請輸入第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;
   cin>>temp;
   path[1].nodesun[i][j]=temp;
  }
  cout<<"請輸入初始狀態(tài)的空格的位置(行)"<<endl;
  cin>>temp;
  path[1].x=temp;
cout<<"請輸入初始狀態(tài)的空格的位置(列)"<<endl;
  cin>>temp;
  path[1].y=temp;
//目標狀態(tài)
for(i=1;i<4;i++)
     for(j=1;j<4;j++)
  {cout<<"請輸入目標狀態(tài)第"<<i<<"行"<<"第"<<j<<"列的值"<<endl;
   cin>>temp;
   desti[i][j]=temp;
  }
  //廣度優(yōu)先搜索
while(front<=rear&&!find)
{ m=path[front].x;
  n=path[front].y ;
  for(f=0;f<4;f++)
  {i=m+zx[f];
   j=n+zy[f];
   if(i>=1&&i<=3&&j>=1&&j<=3)
   {rear++;
    path[rear]=path[front];
path[rear].nodesun[m][n]=path[front].nodesun[i][j];
path[rear].nodesun[i][j]=0;
path[rear].pre=front;
path[rear].x=i;
path[rear].y=j;
   if(detect(&path[rear]))
   {printlj();
   find=1;
   break;
   }
   }
  }
   front++;
   }
}

上面是用最簡單的深度優(yōu)先，廣度優(yōu)先直接搜索得來得，毫無AI可言，這并不說明我不能寫出其更好得算法，這里最簡單得的估價函數(shù)f(x)=g(x)+h(x)
g(x)用初始化的節(jié)點到當前的節(jié)點的路徑長度來表示h(x)啟發(fā)函數(shù)用當前狀態(tài)和目標狀態(tài)的位置不同的個數(shù)來表示，待續(xù)