15数码问题地解决算法算法和具体代码文档格式.docx
《15数码问题地解决算法算法和具体代码文档格式.docx》由会员分享，可在线阅读，更多相关《15数码问题地解决算法算法和具体代码文档格式.docx（55页珍藏版）》请在冰点文库上搜索。
（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;
boolpare（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（pare（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:
//祖先结点从左边来
next=open.r
升级会员 