c 的一些经典算法,满好的,适合初学者. 也可以当作小程序看,对初学者会很有帮助

 
 
  
文章标题：拼图游戏的算法
原 作 者：不详
原 出 处：不详
发 布 者：loose_went
发布类型：转载
发布日期：2004-08-04
今日浏览：11
总 浏 览：562
  

相信大家都玩过"滑块拼图"游戏! 
 大概说一下 :假如一副图是由几个部分拼凑成的,现在要你把这些散块拼凑成一副完整的图片 
       也可以是几个数字来拼凑 
 比如 3*3的格子 
    1 2 3 
    4 5 6 
    7 8   (相当于原始矩阵) 
有一个格子是空的现在要你组合成 
   1 2 7 
   3 6 4 
   5 8     (目标矩阵) 
问题是编写一种算法 能根据输入的原始图形(矩阵)拼凑成目标图形(目标矩阵) 要求是步数最少(耗时间最少) 
 #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];//目标状态 
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<<"请输入初始状态的空格的位置(行)"<<endl; 
 cin>>temp; 
 path[1].x=temp; 
cout<<"请输入初始状态的空格的位置(列)"<<endl; 
 cin>>temp; 
 path[1].y=temp; 
//目标状态 
for(i=1;i<4;i++) 
   for(j=1;j<4;j++) 
 {cout<<"请输入目标状态第"<<i<<"行"<<"第"<<j<<"列的值"<<endl; 
  cin>>temp; 
  desti[i][j]=temp; 
 } 
 //深度优先搜索 
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];//目标状态 
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<<"请输入初始状态的空格的位置(行)"<<endl; 
 cin>>temp; 
 path[1].x=temp; 
cout<<"请输入初始状态的空格的位置(列)"<<endl; 
 cin>>temp; 
 path[1].y=temp; 
//目标状态 
for(i=1;i<4;i++) 
   for(j=1;j<4;j++) 
 {cout<<"请输入目标状态第"<<i<<"行"<<"第"<<j<<"列的值"<<endl; 
  cin>>temp; 
  desti[i][j]=temp; 
 } 
 //广度优先搜索 
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++; 
  } 
} 

上面是用最简单的深度优先，广度优先直接搜索得来得，毫无AI可言，这并不说明我不能写出其更好得算法，这里最简单得的估价函数f(x)=g(x)+h(x) 
g(x)用初始化的节点到当前的节点的路径长度来表示h(x)启发函数用当前状态和目标状态的位置不同的个数来表