试验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 A[N][N]={ {1,2,3,4}, {5,10,6,8}, {0,9,7,12}, {13,14,11,15} };
目标状况：int B[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）.
流程图：
起点 把S放入open表 S是否为目标节点？ 是 否 是 成功 Open表是否为空表？ 掉败 把第一个节点N从open表移出.并把他放入closed表中 是 节点N的深度是否等于深度界线 否 扩大N,把它的后继节点放入open表的前头. 否 是否有任何后继节点为目标节点 是 成功 输入：初始态int A[N][N]={ {1,2,3,4}, {5,10,6,8}, {0,9,7,12}, {13,14,11,15} };
目标状况：int B[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) 流程图：
开端 把s放入open表,记为f=h 是 Open==null？ 否 拔取open表中未被遍历的且value最小的节点设置为min,放入closed表中 掉败 是 Min是目标节点？ 成功 否 扩大min,产生厥后继节点successor 树立从successor返回min的指针 盘算value值（不吻合数和深度之和） 否 Suc属于open？ 是 是 是 Suc=pld,把他添加倒min的后继节点表中 Suc属于close？ 否 否 Valuc（successor） 目标状况：int B[N][N]={ {1,2,3,4}, {5,6,7,8}, {9,10,11,12}, {13,14,15,0} }; 输出截图：6走完成,逆序输出. 各源代码见附件. 附件：（源程序代码） 1 广度优先算法： #include typedef struct QNode{ int data[N][N]; int ancent; 离为 1234 5为可以随意率性偏向 int x; int y; struct QNode *next; struct QNode *prior; }QNode, *QueuePtr; typedef struct{ QueuePtr head; QueuePtr rear; }LinkQueue; int A[N][N]={ {1,2,3,4}, {5,10,6,8}, {0,9,7,12}, {13,14,11,15} }; int B[N][N]={ {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=A[x][y]; int i,j,sum2 = 0,sum1 = 0; int a[N*N],b[N*N]; for(i=0;i bool begin_opint(){ int i,j; for(i=0;i bool compare(int a[N][N]){ int i,j; for(i=0;i bool moveup(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j; if(x==0) return false; for(i=0;i } bool movedown(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j; if(x==N-1)return false; for(i=0;i bool moveright(int a[N][N],QueuePtr *b,int x,int y){ int k,i,j; if(y==N-1) return false; for(i=0;i bool copy(QueuePtr *a){ int i,j; for(i=0;i void output(int a[N][N]){ int i,j; for(i=0;i void main(){ QueuePtr closed,p,q; LinkQueue open; /*if(!check()){ printf(\"no answer!!\\n\"); //no answer exit(0); }*/ if(!begin_opint()){ printf(\"no 0 opint!!\\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(\"steps is %d\\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 #define DEEP 10 typedef struct QNode{ int data[N][N]; int ancent; //标识表记标帜偏向左上右下分离为 1234 5为可以随意率性偏向 int x; int y; int deep; struct QNode *next; }QNode, *QueuePtr; typedef struct{ QueuePtr head; }LinkQueue; int A[N][N]={ {1,2,3,4}, {5,10,6,8}, {0,9,7,12}, {13,14,11,15} }; int B[N][N]={ {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=A[x][y]; int i,j,sum2 = 0,sum1 = 0; int a[N*N],b[N*N]; for(i=0;i bool begin_opint(){ 因篇幅问题不能全部显示，请点此查看更多更全内容