15数码问题的解决算法(算法和具体代码)

人工智能题目：15数码问题实验1：要求：采用广度优先算法解决15数码问题，输出扩展结点，步数和最终结果算法描述：广度优先搜索,即BFS(Breadth First Search),常常深度优先并列提及。这是一种相当常用的图算法，其特点是：每次搜索指定点，并将其所有未访问过的近邻加入搜索队列（而深度优先搜索则是栈），循环搜索过程直到队列为空。广度优先搜索算法的基本思想：从初始状态出发，按照给定的结点产生式规则（算符、结点扩展规则）生产第一层结点，每生成一个结点就检查是不是目标结点，如果是目标结点就搜索结束，如果不是目标结点并且前面没出现过就保存该结点（入队列）；再用产生式规则将所有第一层的结点依次扩展，得到第二层结点，同时检查是否为目标结点，是目标搜索停止，不是并且没出现过保存（入队）；再把第二层的结点按产生规则扩展生产第三层结点，直至找到目标或所有的状态找完但找不到目标（队列空）。特点：先生成深度为1的所有结点，再生产深度为2的所有结点，依次类推。先横向，再纵向。这种方法找到目标，需要的步数一定最少。程序算法流程图：描述：(1).把起始结点放到OPEN表中。(2).如果OPEN表是个空表，则没有解，失败退出；否则继续。(3).把第一个结点从OPEN表中移出，并把它放入CLOSE表的扩展节点表中。 (4).扩展结点N。如果没有后继结点，则转向步骤（2）。 (5).把N的所有后继结点放到OPEN表的末端，并提供从这些后继结点回到N的指针。(6).如果N的任意个后继结点是个目标结点，则找到一个解答，成功退出；否则转向步骤（2）.流程图：起点把S放入open表Open表是否为空表？是否有任何后继节点为目标节点把第一个节点N从open表移出。并把他放入closed表中扩展N，把它的后继节点放入open表的末端，提供返回到N的指针。成功失败是否是否输入：初始态int ANN= 1,2,3,4, 5,10,6,8, 0,9,7,12, 13,14,11,15;目标状态：int BNN= 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）.流程图：是把S放入open表起点是否有任何后继节点为目标节点成功是否扩展N，把它的后继节点放入open表的前头。节点N的深度是否等于深度界限把第一个节点N从open表移出。并把他放入closed表中Open表是否为空表？S是否为目标节点？成功失败否是是否输入：初始态int ANN= 1,2,3,4, 5,10,6,8, 0,9,7,12, 13,14,11,15;目标状态：int BNN= 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)流程图：开始把s放入open表，记为f=h计算value值（不吻合数和深度之和）建立从successor返回min的指针扩展min，产生其后继节点successorSuc=pld，把他添加倒min的后继节点表中把successor放入open中去，添进min的后继表重新确定old的父辈节点，并修正value（old）Open=null？Min是目标节点？Suc属于open？Valuc（successor）minSuc属于close？选取open表中未被遍历的且value最小的节点设置为min，放入closed表中成功失败计算value是否否是否是否是否是 是输入：初始态int ANN= 1,2,3,4, 5,10,6,8, 0,9,7,12, 13,14,11,15;目标状态：int BNN= 1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0;输出截图：6走完成，逆序输出。各源代码见附件。附件：（源程序代码）1 广度优先算法：#include #include #include #include#define N 4typedef struct QNodeint dataNN;int ancent;/标记方向左上下右分别为 1234 5为可以任意方向int x;int y;struct QNode *next;struct QNode *prior;QNode, *QueuePtr;typedef structQueuePtr head;QueuePtr rear;LinkQueue;int ANN= 1,2,3,4, 5,10,6,8, 0,9,7,12, 13,14,11,15;int BNN= 1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0;int n=0;/记录步数int x,y;bool check()/判断是否有路径，根据初始态和目标态的秩序，若不同为奇数或同为偶数，则无路径int temp=Axy;int i,j,sum2 = 0,sum1 = 0;int aN*N,bN*N;for(i=0;iN;i+)for(j=0;jN;j+)ai*N+j=Aij;for(i=0;iN;i+)for(j=0;jN;j+)bi*N+j=Bij;for(i=0;iN*N-1;i+)for(j=i+1;jaj) sum1+;for(i=0;iN*N-1;i+)for(j=i+1;jbj) sum2+;if(sum1%2=0&sum2%2=1)|(sum1%2=1&sum2%2=0)return false;return true;bool begin_opint()int i,j;for(i=0;iN;i+)for(j=0;jN;j+)if(Aij=0)x=i;y=j;return true;return false;bool compare(int aNN)int i,j;for(i=0;iN;i+)for(j=0;jN;j+)if(aij!=Bij)return false;return true;bool moveleft(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(y=0)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-dataxy-1;(*b)-dataxy-1=k;(*b)-x=x;(*b)-y=y-1; return true;bool moveup(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(x=0)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-datax-1y;(*b)-datax-1y=k;(*b)-x=x-1;(*b)-y=y;return true;bool movedown(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(x=N-1)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-datax+1y;(*b)-datax+1y=k;(*b)-x=x+1;(*b)-y=y;return true;bool moveright(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(y=N-1)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-dataxy+1;(*b)-dataxy+1=k;(*b)-x=x;(*b)-y=y+1; return true;bool copy(QueuePtr *a)int i,j;for(i=0;iN;i+)for(j=0;jdataij=Aij;return true;void output(int aNN)int i,j;for(i=0;iN;i+)for(j=0;jnext=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进closedopen.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(steps is %dn,n);break;/将后继结点放入open表中switch(closed-next-ancent)case 1: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;else free(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;else free(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;else free(p);break;case 2: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;else free(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;else free(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;else free(p);break;case 3: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;else free(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;else free(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;else free(p);break;case 4: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;else free(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;else free(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;else free(p);break;default: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;else free(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;else free(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;else free(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;else free(p);break;2 深度优先算法：#include #include #include #include#define N 4#define DEEP 10typedef struct QNodeint dataNN;int ancent;/标记方向左上右下分别为 1234 5为可以任意方向int x;int y;int deep;struct QNode *next;QNode, *QueuePtr;typedef structQueuePtr head;LinkQueue;int ANN= 1,2,3,4, 5,10,6,8, 0,9,7,12, 13,14,11,15;int BNN= 1,2,3,4, 5,6,7,8, 9,10,11,12, 13,14,15,0;int n=0;/记录步数int x,y;bool check()/判断是否有路径，根据初始态和目标态的秩序，若不同为奇数或同为偶数，则无路径int temp=Axy;int i,j,sum2 = 0,sum1 = 0;int aN*N,bN*N;for(i=0;iN;i+)for(j=0;jN;j+)ai*N+j=Aij;for(i=0;iN;i+)for(j=0;jN;j+)bi*N+j=Bij;for(i=0;iN*N-1;i+)for(j=i+1;jaj) sum1+;for(i=0;iN*N-1;i+)for(j=i+1;jbj) sum2+;if(sum1%2=0&sum2%2=1)|(sum1%2=1&sum2%2=0)return false;return true;bool begin_opint()int i,j;for(i=0;iN;i+)for(j=0;jN;j+)if(Aij=0)x=i;y=j;return true;return false;bool compare(int aNN)int i,j;for(i=0;iN;i+)for(j=0;jN;j+)if(aij!=Bij)return false;return true;bool moveleft(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(y=0)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-dataxy-1;(*b)-dataxy-1=k;(*b)-x=x;(*b)-y=y-1; return true;bool moveup(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(x=0)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-datax-1y;(*b)-datax-1y=k;(*b)-x=x-1;(*b)-y=y;return true;bool movedown(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(x=N-1)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-datax+1y;(*b)-datax+1y=k;(*b)-x=x+1;(*b)-y=y;return true;bool moveright(int aNN,QueuePtr *b,int x,int y)int k,i,j;if(y=N-1)return false;for(i=0;iN;i+)for(j=0;jdataij=aij;k=(*b)-dataxy;(*b)-dataxy=(*b)-dataxy+1;(*b)-dataxy+1=k;(*b)-x=x;(*b)-y=y+1; return true;bool copy(QueuePtr *a)int i,j;for(i=0;iN;i+)for(j=0;jdataij=Aij;return true;void output(int aNN)int i,j;for(i=0;iN;i+)for(j=0;jnext=NULL;closed=(QueuePtr)malloc(sizeof(QNode);/头结点closed-next=NULL;p=(QueuePtr)malloc(sizeof(QNode);/S0进open表copy(&p);p-x=x;p-y=y;p-ancent=5;p-deep=0;/s0的深度为0p-next=open.head-next;open.head-next=p;while(open.head-next!=NULL)q=open.head-next;/open进closedopen.head-next=q-next;/移除open表头结点q-next=closed-next;/插入closed表的表头closed-next=q;if(q-deepdata);if(compare(q-data)printf(ok!n);printf(steps is %dn,n);exit(0);/将后继结点放入open表中switch(closed-next-ancent)/左上右下 1234case 1:p=(QueuePtr)malloc(sizeof(QNode);/祖先结点从右来if(moveleft(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=1;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(moveup(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=2;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(movedown(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=4;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);break;case 2:p=(QueuePtr)malloc(sizeof(QNode);/祖先结点从下来if(moveleft(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=1;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(moveup(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=2;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(moveright(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=3;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);break;case 3:p=(QueuePtr)malloc(sizeof(QNode);/祖先结点从左来if(moveup(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=2;p-deep=closed-next-deep+1;p-next=open.head-next;open.head-next=p;else free(p);p=(QueuePtr)malloc(sizeof(QNo