大概说
下 :假如副图是由几个部分拼凑成
,现在要你把这些散块拼凑成副完整图片也可以是几个数字来拼凑
比如 3*3
格子 1 2 3
4 5 6
7 8 (相当于原始矩阵)
有
个格子是空现在要你组合成1 2 7
3 6 4
5 8 (目标矩阵)
问题是编写
种算法 能根据输入原始图形(矩阵)拼凑成目标图形(目标矩阵) 要求是步数最少(耗时间最少)#
"iostream.h"struct node{
nodesun[4][4]; x,y;}path[1000];
zx[4]={-1,0,1,0}; zy[4]={0,-1,0,1}; top; desti[4][4];//目标状态 detect(struct node *p){
i,j;for(i=1;i<4;i
)for(j=1;j<4;j
)
(p->nodesun[i][j]!=desti[i][j])
0; 1;}
void pr
lj
{
tempt; 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];
(j
3)cout<<" "<<endl;
}
tempt
;}
}
void
{ //
化 i,j,m,n,f; 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];
(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;
(detect(&path[top])){pr
lj;find=1;
;}
;}//
}//for
}//while
}
#
"iostream.h"struct node{
nodesun[4][4]; pre; x,y;}path[400];
zx[4]={-1,0,1,0}; zy[4]={0,-1,0,1}; front,rear; desti[4][4];//目标状态 detect(struct node *p){
i,j;for(i=1;i<4;i
)for(j=1;j<4;j
)(p->nodesun[i][j]!=desti[i][j]) 0; 1;}
void pr
lj{
tempt; 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];
(j3)cout<<" "<<endl;
}
tempt=path[tempt].pre;
}
}
void
{ //
化 i,j,m,n,f; 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];
(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;
(detect(&path[rear])){pr
lj;find=1;
;}
}
}
front
;}
}
上面是用最简单
深度优先
广度优先直接搜索得来得毫无AI可言这并不介绍说明我不能写出其更好得算法这里最简单得估价
f(x)=g(x)+h(x)g(x)用
化节点到当前节点路径长度来表示h(x)启发用当前状态和目标状态位置区别个数来表示待续
最新评论