九宫问题Word下载.docx
《九宫问题Word下载.docx》由会员分享，可在线阅读，更多相关《九宫问题Word下载.docx（21页珍藏版）》请在冰点文库上搜索。
structNode*pointData;
//指向节点的指针
structSpringLink*next;
//指向当前节点的其他扩展节点
}SPLink,*PSPLink;
//声明OPEN表和CLOSED表
PNodeopen;
PNodeclosed;
//计算棋盘状态的逆序数
intInverseNumber（statusa）
inti,j,sum=0;
intdata_chang[size*size]={0};
//将二维数组转换成一维数组，以方便求逆序数
for（i=0;
i<
size;
i++）
{
for（j=0;
j<
j++）
{
data_chang[i*size+j]=a[i][j];
}
}
//计算序列中除零外的逆序数
=size*size;
i++）
if（data_chang[i]!
=0）
//要比较多少次,从最后一个元素开始比较
for（j=i;
j>
=0;
j--）
{
//当后一个数比前一个数小时
if（data_chang[i]<
data_chang[j]）
{
sum++;
}
}
returnsum;
}
//判断是否存在解决方案
boolhasSolution（statusstartStatus,statustargetStatus）
intstartInverseNumber=InverseNumber（startStatus）;
inttatgetInverseNumber=InverseNumber（targetStatus）;
//判断初始状态和目标状态除零外的序列逆序数奇偶性，相同则可求值，不同则不可求
if（（startInverseNumber%2）!
=（tatgetInverseNumber%2））
returnfalse;
else
returntrue;
//初始化一个空链表
voidinitLink（PNode&
Head）
Head=（PNode）malloc（sizeof（NNode））;
Head->
next=NULL;
//判断链表是否为空
boolisEmpty（PNodeHead）
if（Head->
next==NULL）
//从链表中拿出一个数据
voidpopNode（PNode&
Head,PNode&
FNode）
if（isEmpty（Head））
FNode=NULL;
return;
FNode=Head->
next;
next=Head->
next->
FNode->
//向节点的最终后继节点链表中添加新的子节点
voidaddSpringNode（PNode&
Head,PNodenewData）
PSPLinknewNode=（PSPLink）malloc（sizeof（SPLink））;
newNode->
pointData=newData;
child;
child=newNode;
//释放状态图中存放节点后继节点地址的空间
voidfreeSpringLink（PSPLink&
PSPLinktmm;
while（Head!
=NULL）
tmm=Head;
Head=Head->
free（tmm）;
//释放open表与closed表中的资源
voidfreeLink（PNode&
PNodetmn;
tmn=Head;
Head=Head->
free（tmn）;
//首先释放存放节点后继节点地址的空间
freeSpringLink（Head->
child）;
tmn=Head;
free（tmn）;
//向普通链表中添加一个节点
voidaddNode（PNode&
newNode）
next=newNode;
//向非递减排列的链表中添加一个节点
voidaddAscNode（PNode&
PNodeP;
PNodeQ;
P=Head->
Q=Head;
while（P!
=NULL&
&
P->
f_value<
f_value）
Q=P;
P=P->
//上面判断好位置之后，下面就是简单的插入节点了
next=Q->
Q->
//计算节点到目标状态的预计耗散值
intcomputeh_value（PNodetheNode,statustargetStatus）
intnum=0;
for（inti=0;
i<
3;
i++）
for（intj=0;
j<
j++）
if（theNode->
data[i][j]!
=targetStatus[i][j]）
{
num++;
}
returnnum;
//计算节点的f，g，h值
voidcomputeAllValue（PNode&
theNode,PNodeparentNode,statustargetStatus）
if（parentNode==NULL）
theNode->
g_value=0;
g_value=parentNode->
g_value+1;
theNode->
h_value=computeh_value（theNode,targetStatus）;
f_value=theNode->
g_value+theNode->
h_value;
//初始化函数，进行算法初始条件的设置
voidinitial（statusstartStatus,statustargetStatus）
//初始化open以及closed表
initLink（open）;
initLink（closed）;
//初始化起始节点，令初始节点的父节点为空节点
PNodeNULLNode=NULL;
PNodeStartNode=（PNode）malloc（sizeof（NNode））;
StartNode->
data[i][j]=startStatus[i][j];
StartNode->
parent=NULL;
child=NULL;
computeAllValue（StartNode,NULLNode,targetStatus）;
//起始节点进入OPEN表
addAscNode（open,StartNode）;
//将B节点的状态赋值给A节点
voidstatusAEB（PNode&
ANode,PNodeBNode）
ANode->
data[i][j]=BNode->
data[i][j];
//两个节点是否有相同的状态
boolhasSameStatus（PNodeANode,PNodeBNode）
size;
if（ANode->
=BNode->
data[i][j]）
returnfalse;
returntrue;
//节点与其祖先节点是否有相同的状态
boolhasAnceSameStatus（PNodeOrigiNode,PNodeAnceNode）
while（AnceNode!
if（hasSameStatus（OrigiNode,AnceNode））
returntrue;
AnceNode=AnceNode->
parent;
returnfalse;
//取得方格中空的格子的位置
voidgetPosition（PNodetheNode,int&
row,int&
col）
data[i][j]==0）
row=i;
col=j;
return;
//交换两个数字的值
voidchangeAB（int&
a,int&
b）
intc;
c=b;
b=a;
a=c;
//检查相应的状态是否在某一个链表中
boolinLink（PNodespciNode,PNodetheLink,PNode&
theNodeLink,PNode&
preNode）
preNode=theLink;
theLink=theLink->
while（theLink!
if（hasSameStatus（spciNode,theLink））
theNodeLink=theLink;
preNode=theLink;
theLink=theLink->
//产生节点的后继节点链表
voidSpringLink（PNodetheNode,PNode&
spring,statustargetStatus）
introw;
intcol;
getPosition（theNode,row,col）;
//空的格子右边的格子向左移动
if（col!
=2）
PNoderlNewNode=（PNode）malloc（sizeof（NNode））;
statusAEB（rlNewNode,theNode）;
changeAB（rlNewNode->
data[row][col],rlNewNode->
data[row][col+1]）;
if（hasAnceSameStatus（rlNewNode,theNode->
parent））
free（rlNewNode）;
//与父辈相同，丢弃本节点
else
rlNewNode->
parent=theNode;
computeAllValue（rlNewNode,theNode,targetStatus）;
//将本节点加入后继节点链表
addNode（spring,rlNewNode）;
//空的格子左边的格子向右移动
=0）
PNodelrNewNode=（PNode）malloc（sizeof（NNode））;
statusAEB（lrNewNode,theNode）;
changeAB（lrNewNode->
data[row][col],lrNewNode->
data[row][col-1]）;
if（hasAnceSameStatus（lrNewNode,theNode->
free（lrNewNode）;
lrNewNode->
computeAllValue（lrNewNode,theNode,targetStatus）;
addNode（spring,lrNewNode）;
//空的格子上边的格子向下移动
if（row!
PNodeudNewNode=（PNode）malloc（sizeof（NNode））;
statusAEB（udNewNode,theNode）;
changeAB（udNewNode->
data[row][col],udNewNode->
data[row-1][col]）;
if（hasAnceSameStatus（udNewNode,theNode->
free（udNewNode）;
udNewNode->
computeAllValue（udNewNode,theNode,targetStatus）;
addNode（spring,udNewNode）;
//空的格子下边的格子向上移动
PNodeduNewNode=（PNode）malloc（sizeof（NNode））;
statusAEB（duNewNode,theNode）;
changeAB（duNewNode->
data[row][col],duNewNode->
data[row+1][col]）;
if（hasAnceSameStatus（duNewNode,theNode->
free（duNewNode）;
duNewNode->
computeAllValue（duNewNode,theNode,targetStatus）;
addNode（spring,duNewNode）;
//输出给定节点的状态
voidoutputStatus（PNodestat）
cout<
<
stat->
data[i][j]<
"
;
cout<
endl;
//输出最佳的路径
voidoutputBestRoad（PNodegoal）
intdeepnum=goal->
g_value;
if（goal->
parent!
outputBestRoad（goal->
parent）;
cout<
第"
<
deepnum--<
步的状态：
"
outputStatus（goal）;
voidAStar（statusstartStatus,statustargetStatus）
PNodetmpNode;
//指向从open表中拿出并放到closed表中的节点的指针
PNodespring;
//tmpNode的后继节点链
PNodetmpLNode;
//tmpNode的某一个后继节点
PNodetmpChartNode;
PNodethePreNode;
//指向将要从closed表中移到open表中的节点的前一个节点的指针
boolgetGoal=false;
//标识是否达到目标状态
longnumcount=1;
//记录从open表中拿出节点的序号
initial（startStatus,targetStatus）;
//对函数进行初始化
initLink（spring）;
//对后继链表的初始化
tmpChartNode=NULL;
从OPEN表中拿出的节点的状态及相应的值"
while（!
isEmpty（open））
//从OPEN表中拿出f值最小的元素,并将拿出的元素放入CLOSED表中
popNode（open,tmpNode）;
addNode（closed,tmpNode）;
numcount++<
个状态是：
outputStatus（tmpNode）;
其f值为：
tmpNode->
其g值为：
g_value<
其h值为：
h_value<
//如果拿出的元素是目标状态则跳出循环
if（computeh_value（tmpNode,targetStatus）==0）
getGoal=true;
break;
//产生当前检测节点的后继（与祖先不同）节点列表，产生的后继节点的parent属性指向当前检测的节点
SpringLink（tmpNode,spring,targetStatus）;
//遍历检测节点的后继节点链表
while（!
isEmpty（spring））
popNode（spring,tmpLNode）;
//状态在OPEN表中已经存在，thePreNode参数在这里并不起作用
if（inLink（tmpLNode,open,tmpChartNode,thePreNode））
addSpringNode（tmpNode,tmpChartNode）;
if（tmpLNode->
tmpChartNode->
g_value）
tmpChartNode->
parent=tmpLNode->
g_value=tmpLNode->
f_value=tmpLNode->
f_value;
fre
升级会员 