15数码问题的解决算法.docx

《15数码问题的解决算法.docx》由会员分享，可在线阅读，更多相关《15数码问题的解决算法.docx（40页珍藏版）》请在三一文库上搜索。

1、题目： 15 数码问题实验 1：要求 ：采用广度优先算法解决15 数码问题，输出扩展结点，步数和最终结果算法描述 ：广度优先搜索 , 即 BFS(Breadth First Search), 常常深度优先并列提及。这是一种相当常用的图算法， 其特点是： 每次搜索指定点， 并将其所有未访问过的近邻加入搜索队列(而深度优先搜索则是栈)，循环搜索过程直到队列为空。广度优先搜索算法的基本思想：从初始状态出发，按照给定的结点产生式规则(算符、结点扩展规则)生产第一层结点，每生成一个结点就检查是不是目标结点， 如果是目标结点就搜索结束， 如果不是目标结点并且前面没出现过就保存该结点(入队列)；再用产生式规

2、则将所有第一层的结点依次扩展，得到第二层结点，同时检查是否为目标结点，是目标搜索停止，不是并且没出现过保存(入队) ； 再把第二层的结点按产生规则扩展生产第三层结点， 直至找到目标或所有的状态找完但找不到目标(队列空)。特点： 先生成深度为 1 的所有结点， 再生产深度为 2 的所有结点， 依次类推。先横向，再纵向。这种方法找到目标，需要的步数一定最少。程序算法流程图 ：描述 ：(1) .把起始结点放到OPENft中。(2) .如果OPEN!是个空表，则没有解，失败退出；否则继续。(3) .把第一个结点从 OPENg中移出，并把它放入 CLOSES的扩展节点表 中。(4) .扩展结点No如果没

3、有后继结点，则转向步骤(2)。(5) .把N的所有后继结点放到 OPENS的末端，并提供从这些后继结点回 到 N 的指针。(6) . 如果 N 的任意个后继结点是个目标结点， 则找到一个解答， 成功退出；否则转向步骤(2) .流程图 ：输入： 初始态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；输由截图：由于输出的路径节点很多这里只是显示最终结果和步数13 14 1112 3 45 0 7 89 & 10 1213 14 11 IS12 3 45

4、6 7 09 14 10 1213 9 11 1512 3 4& 6 7 89 Id il 1213 9 14 1512 3 45 6 7 89 10 11 1213 14 15 0nkfsteps is Z13胪|；05 &ny key 七口 匚untieLiu.实验2:要求：采用深度优先算法实现15数码问题。算法描述：设x是当前被访问顶点，在对 x做过访问标记后，选择一条从x出发的未检测过的边(x , y)。若发现顶点 y已访问过，则重新选择另一条从x出发的未检测过的边，否则沿边 (x , y)到达未曾访问过的 y,对y访问并将其 标记为已访问过；然后从y开始搜索，直到搜索完从y出发的所有

5、路径，即访问完所有从y出发可达的顶点之后，才回溯到顶点x,并且再选择一条从x出发的未检测过的边。上述过程直至从x出发的所有边都已检测过为止。此时，若 x不是源点，则回溯到在x之前被访问过的顶点；否则图中所有和源点有路彳相通的顶点(即从源点可达的所有顶点)都已被访问过，若图G是连通图，则遍历过程结束，否则继续选择一个尚未被访问的顶点 作为新源点，进行新的搜索过程。流程图：描述：(1) .把起始结点放到 OPENS中。如果此结点为一目标结点，则得到一个 解。(2) .如果OPENS是个空表，则没有解，失败退出；否则继续。(3) .把第一个结点从 OPENS中移出，并把它放入 CLOSES中(4)

6、.如果结点N的深度等于最大深度，则转向步骤(2)。(5) .扩展结点N,产生其全部后裔，并把它们放入 OPENg的前头。如果没 有后裔，则转向步骤(2)。(6) .如果N的任意个后继结点是个目标结点，则找到一个解答，成功退出; 否则转向步骤(2).流程图：输入： 初始态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；输由截图：由于输出的路径节点很多这里只是显示最终结果和步数13 L4 11 1512 3 4S 6 0 & ? 10 7 1Z 13 1

7、4 11 1512 3 4 5 & 7 8 ? 10 0 1212 14 11 1S12 3 4 5 6 7 8 9 9 11 1213 L4 012 3 4S 6 7 8 ? 13 11 12 13 14 15 0ok* is 1224Fi*唯窿&ku“ 七0 c/ntinuR实验3:要求：采用启发式的A星算法实现15数码问题。算法描述：启发式搜索算法A, 一般简称为A算法，是一种典型的启发式搜索算法。其基本思想是：定义一个评价函数f ，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的形式如下：f (n) = g (n) + h (n)其中 n 是被评价的节点。f (n)、

8、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)值的大小对OPEN1中的元素进

9、行排序，f值小的节 点放在前面，而f值大的节点则被放在OPEN1的后面，这样每次扩展节点时， 都是选择当前f 值最小的节点来优先扩展。流程图：描述：(1) .把起始结点放到OPEN1中。计算F (S),并把其值与结点S联系起来。(2) .如果OPEN1是个空表，则没有解，失败退出；否则继续。(3) .从OPENft中选才?一个F值最小的结点I。如果有几个结点合格，当其 中有一个为目标结点时，则选择此目标结点，否则就选择其中任一个结点为结点 I 。(4) .把结点I从OPENft中移出，并把它放入 CLOSE勺扩展结点表中。(5) . 如果 I 是目标结点，则成功退出，求得一个解。(6) . 扩

10、展结点 I ，生成其全部后继结点。对于I 的每一个后继结点 J：(a) . 计算 F(J).(b) .如果J既不再OPEN!中，也不再CLOSE!中，则用估价函数F把 它添入OPENft中。从J加一指向其父辈结点I的指针，以便一旦 找到目标结点时记住一个解答捷径。(c) .如果J已在OPEK或CLOS法上，则比较刚刚对J计算过的F值 和前面计算过的该结点在表中的 F 值。如果新的 F 值较小，则 (i). 以此新值代替旧值。(ii) . 从 J 指向 I ，而不是指向它的父辈结点。(iii) . 如果结点J在CLOSES中，则把它移回 OPENft中。(7). 转向( 2) ，即 GOTO(2

11、)流程图：输入： 初始态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走完成，逆序输由12 3 45 & 7 SJ 11 1213 14 15 012 3 45 & ? 89 10 11 1213 14 0 1512 3 45 & 7 89 10 0 1213 14 11 1512 3 45 6 口 89 10 7 121311 1512 3 45修6 89 10 7 1213 14 11 1512 3 4S 10 6 89 0

12、? 1213 14 11 1512 3 4& 1Q 6 80 ? 7 1213 14 11 15step is Gc c rcC . 1 A C ccr十 二宜口年各源代码见附件附件： (源程序代码)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

13、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

14、=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 com

15、pare(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

16、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)-

17、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(QueuePt

18、r *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=next=NULL;prior=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-p

19、rior=NULL;p-next=next;next=p;=;/open 表的尾结点暂时设置为头结点whilenext!=NULL)q=next;/open 进 closednext=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=(QueueP

20、tr)malloc(sizeof(QNode);/祖先结点从右来if(moveleft(closed-next-data,&p,closed-next-x,closed-next-y) p-prior=closed-next;p-ancent=1;p-next=next;next=p;=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=next;next=

21、p;=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=next;next=p;=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-pri

22、or=closed-next;p-ancent=1;p-next=next;next=p;=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=next;next=p;=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(moveright(closed-next-data,&p,closed-next-x

23、,closed-next-y) p-prior=closed-next;p-ancent=4;p-next=next;next=p;=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=next;next=p;=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if

24、(movedown(closed-next-data,&p,closed-next-x,closed-next-y) p-prior=closed-next;p-ancent=3;p-next=next;next=p;=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=next;next=p;=p;else free(p);break;case 4:

25、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=next;next=p;=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=

26、next;next=p;=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=next;next=p;=p;else free(p);break;default:p=(QueuePtr)malloc(sizeof(QNode);/初始情况if(moveleft(closed-next-data,&p,closed-next-x,closed-next

27、-y) p-prior=closed-next;p-ancent=1;p-next=next;next=p;=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=next;next=p;=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(movedown(closed-next-data,&p,close

28、d-next-x,closed-next-y) p-prior=closed-next;p-ancent=3;p-next=next;next=p;=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=next;next=p;=p;else free(p);break;2 深度优先算法：#include #include #include #inclu

29、de#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;/ 记录

30、步数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)|(sum

31、1%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

32、 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=

33、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

34、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;/no answer/ 确定 0 点closed=(QueuePtr)

35、malloc(sizeof(QNode);/头结点进 open 表/s0 的深度为whilenext!=NULL)q=next;next=q-next;q-next=closed-next;/open 进 closed/ 移除 open 表头结点/ 插入 closed表的表头closed-next=NULL;p=(QueuePtr)malloc(sizeof(QNode);/S0 copy(&p);p-x=x;p-y=y;p-ancent=5;p-deep=0;p-next=next;next=p;closed-next=q;if(q-deepdata);if(compare(q-data)p

36、rintf(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=next;next=p;else free(p);p=(QueuePtr)malloc(sizeof(

37、QNode);/if(moveup(closed-next-data,&p,closed-next-x,closed-next-y)p-ancent=2;p-deep=closed-next-deep+1;p-next=next;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=next;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=next;next=p;else free(p);p=(QueuePtr)malloc(sizeof(QNode);/if(moveup(closed-next-data,&p,closed-next-x,