15数码问题的解决算法算法和具体代码Word下载.docx
《15数码问题的解决算法算法和具体代码Word下载.docx》由会员分享,可在线阅读,更多相关《15数码问题的解决算法算法和具体代码Word下载.docx(47页珍藏版)》请在冰点文库上搜索。
(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]={
{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是连通图,则遍历过程结束,否则继续选择一个尚未被访问的顶点作为新源点,进行新的搜索过程。
如果此结点为一目标结点,则得到一个解。
(3).把第一个结点从OPEN表中移出,并把它放入CLOSE表中。
(4).如果结点N的深度等于最大深度,则转向步骤
(2)。
(5).扩展结点N,产生其全部后裔,并把它们放入OPEN表的前头。
如果没有后裔,则转向步骤
(2)。
由于输出的路径节点很多这里只是显示最终结果和步数
实验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值最小的节点来优先扩展。
计算F(S),并把其值与结点S联系起来。
(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)
6走完成,逆序输出。
各源代码见附件。
附件:
(源程序代码)
1广度优先算法:
#include<
stdlib.h>
string.h>
stdio.h>
#include<
iostream.h>
#defineN4
typedefstructQNode{
intdata[N][N];
intancent;
//标记方向左上下右分别为12345为可以任意方向
intx;
inty;
structQNode*next;
structQNode*prior;
}QNode,*QueuePtr;
typedefstruct{
QueuePtrhead;
QueuePtrrear;
}LinkQueue;
intA[N][N]={
intn=0;
//记录步数
intx,y;
boolcheck(){
//判断是否有路径,根据初始态和目标态的秩序,若不同为奇数或同为偶数,则无路径
inttemp=A[x][y];
inti,j,sum2=0,sum1=0;
inta[N*N],b[N*N];
for(i=0;
i<
N;
i++){
for(j=0;
j<
j++){
a[i*N+j]=A[i][j];
}
}
b[i*N+j]=B[i][j];
N*N-1;
for(j=i+1;
N*N;
if(a[i]!
=temp&
&
a[j]!
a[i]>
a[j])sum1++;
if(b[i]!
b[j]!
b[i]>
b[j])sum2++;
if((sum1%2==0&
sum2%2==1)||(sum1%2==1&
sum2%2==0)){
returnfalse;
returntrue;
}
boolbegin_opint(){
inti,j;
if(A[i][j]==0){
x=i;
y=j;
returntrue;
returnfalse;
boolcompare(inta[N][N]){
if(a[i][j]!
=B[i][j])
returnfalse;
boolmoveleft(inta[N][N],QueuePtr*b,intx,inty){
intk,i,j;
if(y==0)
j++)
(*b)->
data[i][j]=a[i][j];
k=(*b)->
data[x][y];
(*b)->
data[x][y]=(*b)->
data[x][y-1];
data[x][y-1]=k;
x=x;
y=y-1;
boolmoveup(inta[N][N],QueuePtr*b,intx,inty){
if(x==0)
data[x-1][y];
data[x-1][y]=k;
x=x-1;
y=y;
boolmovedown(inta[N][N],QueuePtr*b,intx,inty){
if(x==N-1)returnfalse;
data[x+1][y];
data[x+1][y]=k;
x=x+1;
boolmoveright(inta[N][N],QueuePtr*b,intx,inty){
if(y==N-1)
data[x][y+1];
data[x][y+1]=k;
y=y+1;
boolcopy(QueuePtr*a){
(*a)->
data[i][j]=A[i][j];
voidoutput(inta[N][N]){
printf("
%d"
a[i][j]);
}printf("
\n"
);
}printf("
voidmain(){
QueuePtrclosed,p,q;
LinkQueueopen;
/*if(!
check()){
printf("
noanswer!
!
//noanswer
exit(0);
}*/
if(!
begin_opint()){
no0opint!
//确定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->
p=(QueuePtr)malloc(sizeof(QNode));
//S0进open表
copy(&
p);
p->
ancent=5;
next;
next=p;
open.rear=open.head;
//open表的尾结点暂时设置为头结点
while(open.head->
next!
=NULL){
q=open.head->
//open进closed
open.head->
next=q->
//移除open表头结点
q->
next=closed->
//插入closed表的表头
closed->
next=q;
n++;
output(q->
data);
if(compare(q->
data)){
ok!
stepsis%d\n"
n);
break;
//将后继结点放入open表中
switch(closed->
next->
ancent){
case1:
//祖先结点从右来
if(moveleft(closed->
data,&
p,closed->
x,closed->
y)){
p->
prior=closed->
ancent=1;
next=open.rear->
open.rear->
open.rear=p;
}elsefree(p);
p=(QueuePtr)malloc(sizeof(QNode));
//
if(moveup(closed->
ancent=2;
if(movedown(closed->
ancent=3;
break;
case2:
p=(QueuePtr)malloc(sizeof(QNode));
//祖先结点从下来
if(moveright(closed->
ancent=4;
case3:
//祖先结点从上来
case4:
//祖先结点从左边来