15数码问题的解决算法算法和具体代码.docx
《15数码问题的解决算法算法和具体代码.docx》由会员分享，可在线阅读，更多相关《15数码问题的解决算法算法和具体代码.docx（55页珍藏版）》请在冰点文库上搜索。
15数码问题的解决算法算法和具体代码
〈〈人工智能〉〉
题目：
15数码问题
实验1：
要求：
采用广度优先算法解决15数码问题，输出扩展结点，步数和最终结果
算法描述：
广度优先搜索,即BFS（BreadthFirstSearch）,常常深度优先并列提及。
这是一种相当常用的图算法，其特点是：
每次搜索指定点，并将其所有未访问过的近邻加入搜索队列（而深度优先搜索则是栈），循环搜索过程直到队列为空。
广度优先搜索算法的基本思想：
从初始状态出发，按照给定的结点产生式规则（算符、结点扩展规则）生产第一层结点，每生成一个结点就检查是不是目标结点，如果是目标结点就搜索结束，如果不是目标结点并且前面没出现过就保存该结点（入队列）；再用产生式规则将所有第一层的结点依次扩展，得到第二层结点，同时检查是否为目标结点，是目标搜索停止，不是并且没出现过保存（入队）；再把第二层的结点按产生规则扩展生产第三层结点，直至找到目标或所有的状态找完但找不到目标（队列空）。
特点：
先生成深度为1的所有结点，再生产深度为2的所有结点，依次类推。
先横向，再纵向。
这种方法找到目标，需要的步数一定最少。
程序算法流程图：
描述：
（1）.把起始结点放到OPEN表中。
（2）.如果OPEN表是个空表，则没有解，失败退出；否则继续。
（3）.把第一个结点从OPEN表中移出，并把它放入CLOSE表的扩展节点表中。
（4）.扩展结点N。
如果没有后继结点，则转向步骤
（2）。
（5）.把N的所有后继结点放到OPEN表的末端，并提供从这些后继结点回到N的指针。
（6）.如果N的任意个后继结点是个目标结点，则找到一个解答，成功退出；否则转向步骤
（2）.
流程图：
输入：
初始态intA[N][N]={
{1,2,3,4},
{5,10,6,8},
{0,9,7,12},
{13,14,11,15}
};
目标状态：
intB[N][N]={
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,0}
};
输出截图：
由于输出的路径节点很多这里只是显示最终结果和步数。
实验2：
要求：
采用深度优先算法实现15数码问题。
算法描述：
设x是当前被访问顶点，在对x做过访问标记后，选择一条从x出发的未检测过的边（x，y）。
若发现顶点y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边（x，y）到达未曾访问过的y，对y访问并将其标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x，并且再选择一条从x出发的未检测过的边。
上述过程直至从x出发的所有边都已检测过为止。
此时，若x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路径相通的顶点（即从源点可达的所有顶点）都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点作为新源点，进行新的搜索过程。
流程图：
描述：
（1）.把起始结点放到OPEN表中。
如果此结点为一目标结点，则得到一个解。
（2）.如果OPEN表是个空表，则没有解，失败退出；否则继续。
（3）.把第一个结点从OPEN表中移出，并把它放入CLOSE表中。
（4）.如果结点N的深度等于最大深度，则转向步骤
（2）。
（5）.扩展结点N,产生其全部后裔，并把它们放入OPEN表的前头。
如果没有后裔，则转向步骤
（2）。
（6）.如果N的任意个后继结点是个目标结点，则找到一个解答，成功退出；否则转向步骤
（2）.
流程图：
输入：
初始态intA[N][N]={
{1,2,3,4},
{5,10,6,8},
{0,9,7,12},
{13,14,11,15}
};
目标状态：
intB[N][N]={
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,0}
};
输出截图：
由于输出的路径节点很多这里只是显示最终结果和步数
实验3：
要求：
采用启发式的A星算法实现15数码问题。
算法描述：
启发式搜索算法A，一般简称为A算法，是一种典型的启发式搜索算法。
其基本思想是：
定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。
评价函数的形式如下：
f（n）＝g（n）＋h（n）
其中n是被评价的节点。
f（n）、g（n）和h（n）各自表述什么含义呢？
我们先来定义下面几个函数的含义，它们与f（n）、g（n）和h（n）的差别是都带有一个"*"号。
g*（n）：
表示从初始节点s到节点n的最短路径的耗散值；
h*（n）：
表示从节点n到目标节点g的最短路径的耗散值；
f*（n）=g*（n）+h*（n）：
表示从初始节点s经过节点n到目标节点g的最短路径的耗散值。
而f（n）、g（n）和h（n）则分别表示是对f*（n）、g*（n）和h*（n）三个函数值的的估计值。
是一种预测。
A算法就是利用这种预测，来达到有效搜索的目的的。
它每次按照f（n）值的大小对OPEN表中的元素进行排序，f值小的节点放在前面，而f值大的节点则被放在OPEN表的后面，这样每次扩展节点时，都是选择当前f值最小的节点来优先扩展。
流程图：
描述：
（1）.把起始结点放到OPEN表中。
计算F（S），并把其值与结点S联系起来。
（2）.如果OPEN表是个空表，则没有解，失败退出；否则继续。
（3）.从OPEN表中选择一个F值最小的结点I。
如果有几个结点合格，当其中有一个为目标结点时，则选择此目标结点，否则就选择其中任一个结点为结点I。
（4）.把结点I从OPEN表中移出，并把它放入CLOSE的扩展结点表中。
（5）.如果I是目标结点，则成功退出，求得一个解。
（6）.扩展结点I，生成其全部后继结点。
对于I的每一个后继结点J：
（a）.计算F（J）.
（b）.如果J既不再OPEN表中，也不再CLOSE表中，则用估价函数F把它添入OPEN表中。
从J加一指向其父辈结点I的指针，以便一旦找到目标结点时记住一个解答捷径。
（c）.如果J已在OPEN表或CLOSE表上，则比较刚刚对J计算过的F值和前面计算过的该结点在表中的F值。
如果新的F值较小，则
（i）.以此新值代替旧值。
（ii）.从J指向I，而不是指向它的父辈结点。
（iii）.如果结点J在CLOSE表中，则把它移回OPEN表中。
（7）.转向
（2），即GOTO
（2）
流程图：
输入：
初始态intA[N][N]={
{1,2,3,4},
{5,10,6,8},
{0,9,7,12},
{13,14,11,15}
};
目标状态：
intB[N][N]={
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,0}
};
输出截图：
6走完成，逆序输出。
各源代码见附件。
附件：
（源程序代码）
1广度优先算法：
#include
#include
#include
#include
#defineN4
typedefstructQNode{
intdata[N][N];
intancent;//标记方向左上下右分别为12345为可以任意方向
intx;
inty;
structQNode*next;
structQNode*prior;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrhead;
QueuePtrrear;
}LinkQueue;
intA[N][N]={
{1,2,3,4},
{5,10,6,8},
{0,9,7,12},
{13,14,11,15}
};
intB[N][N]={
{1,2,3,4},
{5,6,7,8},
{9,10,11,12},
{13,14,15,0}
};
intn=0;//记录步数
intx,y;
boolcheck（）{
//判断是否有路径，根据初始态和目标态的秩序，若不同为奇数或同为偶数，则无路径
inttemp=A[x][y];
inti,j,sum2=0,sum1=0;
inta[N*N],b[N*N];
for（i=0;ifor（j=0;ja[i*N+j]=A[i][j];
}
}
for（i=0;ifor（j=0;jb[i*N+j]=B[i][j];
}
}
for（i=0;ifor（j=i+1;jif（a[i]!
=temp&&a[j]!
=temp&&a[i]>a[j]）sum1++;
}
}
for（i=0;ifor（j=i+1;jif（b[i]!
=temp&&b[j]!
=temp&&b[i]>b[j]）sum2++;
}
}
if（（sum1%2==0&&sum2%2==1）||（sum1%2==1&&sum2%2==0））{
returnfalse;
}
returntrue;
}
boolbegin_opint（）{
inti,j;
for（i=0;ifor（j=0;jif（A[i][j]==0）{
x=i;y=j;
returntrue;}
}
}
returnfalse;
}
boolcompare（inta[N][N]）{
inti,j;
for（i=0;ifor（j=0;jif（a[i][j]!
=B[i][j]）
returnfalse;
}
}
returntrue;
}
boolmoveleft（inta[N][N],QueuePtr*b,intx,inty）{
intk,i,j;
if（y==0）
returnfalse;
for（i=0;ifor（j=0;j（*b）->data[i][j]=a[i][j];
}
k=（*b）->data[x][y];
（*b）->data[x][y]=（*b）->data[x][y-1];
（*b）->data[x][y-1]=k;
（*b）->x=x;
（*b）->y=y-1;
returntrue;
}
boolmoveup（inta[N][N],QueuePtr*b,intx,inty）{
intk,i,j;
if（x==0）
returnfalse;
for（i=0;ifor（j=0;j（*b）->data[i][j]=a[i][j];
}
k=（*b）->data[x][y];
（*b）->data[x][y]=（*b）->data[x-1][y];
（*b）->data[x-1][y]=k;
（*b）->x=x-1;
（*b）->y=y;
returntrue;
}
boolmovedown（inta[N][N],QueuePtr*b,intx,inty）{
intk,i,j;
if（x==N-1）returnfalse;
for（i=0;ifor（j=0;j（*b）->data[i][j]=a[i][j];
}
k=（*b）->data[x][y];
（*b）->data[x][y]=（*b）->data[x+1][y];
（*b）->data[x+1][y]=k;
（*b）->x=x+1;
（*b）->y=y;
returntrue;
}
boolmoveright（inta[N][N],QueuePtr*b,intx,inty）{
intk,i,j;
if（y==N-1）
returnfalse;
for（i=0;ifor（j=0;j（*b）->data[i][j]=a[i][j];
}
k=（*b）->data[x][y];
（*b）->data[x][y]=（*b）->data[x][y+1];
（*b）->data[x][y+1]=k;
（*b）->x=x;
（*b）->y=y+1;
returntrue;
}
boolcopy（QueuePtr*a）{
inti,j;
for（i=0;ifor（j=0;j（*a）->data[i][j]=A[i][j];
}
returntrue;
}
voidoutput（inta[N][N]）{
inti,j;
for（i=0;ifor（j=0;jprintf（"%d",a[i][j]）;
}printf（"\n"）;
}printf（"\n"）;
}
voidmain（）{
QueuePtrclosed,p,q;
LinkQueueopen;
/*if（!
check（））{
printf（"noanswer!
!
\n"）;//noanswer
exit（0）;
}*/
if（!
begin_opint（））{
printf（"no0opint!
!
\n"）;//确定0点
exit（0）;
}
open.head=open.rear=（QueuePtr）malloc（sizeof（QNode））;//头结点
open.rear->next=open.head->next=NULL;
open.head->prior=open.head->prior=NULL;
closed=（QueuePtr）malloc（sizeof（QNode））;//头结点
closed->next=NULL;
closed->prior=NULL;
p=（QueuePtr）malloc（sizeof（QNode））;//S0进open表
copy（&p）;
p->x=x;
p->y=y;
p->ancent=5;
p->prior=NULL;
p->next=open.head->next;
open.head->next=p;
open.rear=open.head;//open表的尾结点暂时设置为头结点
while（open.head->next!
=NULL）{
q=open.head->next;//open进closed
open.head->next=q->next;//移除open表头结点
q->next=closed->next;//插入closed表的表头
closed->next=q;
n++;
output（q->data）;
if（compare（q->data））{
printf（"ok!
\n"）;
printf（"stepsis%d\n",n）;
break;
}
//将后继结点放入open表中
switch（closed->next->ancent）{
case1:
p=（QueuePtr）malloc（sizeof（QNode））;//祖先结点从右来
if（moveleft（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=1;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（moveup（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=2;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（movedown（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=3;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
break;
case2:
p=（QueuePtr）malloc（sizeof（QNode））;//祖先结点从下来
if（moveleft（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=1;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（moveup（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=2;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（moveright（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=4;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
break;
case3:
p=（QueuePtr）malloc（sizeof（QNode））;//祖先结点从上来
if（moveleft（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=1;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（movedown（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=3;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（moveright（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=4;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
break;
case4:
p=（QueuePtr）malloc（sizeof（QNode））;//祖先结点从左边来
if（moveup（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=2;
p->next=open.rear->next;
open.rear->next=p;
open.rear=p;
}elsefree（p）;
p=（QueuePtr）malloc（sizeof（QNode））;//
if（movedown（closed->next->data,&p,closed->next->x,closed->next->y））{
p->prior=closed->next;
p->ancent=3;
p->next=open.rear->next;
升级会员 