8数码问题程序源代码Word文件下载.docx
《8数码问题程序源代码Word文件下载.docx》由会员分享，可在线阅读，更多相关《8数码问题程序源代码Word文件下载.docx（16页珍藏版）》请在冰点文库上搜索。
//启发信息，采用数码“不在位”距离和
structnode*father;
//指向解路径上该节点的父节点
structnode*next;
//指向所在open或closed表中的下一个元素
};
structnodes_0={{3,8,2,1,0,5,7,6,4},1,1,0,0,0,NULL,NULL};
//定义初始状态
structnodes_g={{1,2,3,8,0,4,7,6,5},1,1,0,0,0,NULL,NULL};
//定义目标状态
structnode*open=NULL;
//建立open表指针
structnode*closed=NULL;
//建立closed表指针
intsum_node=0;
//用于记录扩展节点总数
intmain（void）
structnodes,*target;
Copy_node（&
s_0,&
s）;
Calculate_f（0,&
//拷贝8数码初始状态，初始化代价值
target=Solution_Astar（&
//求解主程序
if（target）Print_result（target）;
//输出解路径
elseprintf（"
问题求解失败！
"
）;
getch（）;
return0;
}
/******************************************/
/*A*算法*/
structnode*Solution_Astar（structnode*p）
structnode*n,*temp;
Add_to_open（p）;
//将s_0放入open表
while（open!
=NULL）//只要open表中还有元素，就继续对代价最小的节点进行扩展
{
n=open;
//n指向open表中当前要扩展的元素
temp=open->
next;
Add_to_closed（n）;
open=temp;
if（Test_A_B（n,&
s_g））//当前n指向节点为目标时，跳出程序结束；
否则，继续下面的步骤
returnn;
Expand_n（n）;
//扩展节点n
}
returnNULL;
/*******************************************************/
/*生成当前节点n通过走步可以得到的所有状态*/
voidExpand_n（structnode*p）
structnode*temp,*same;
if（p->
j_0>
=1）//空格所在列号不小于1,可左移
{
temp=p->
father;
if（temp!
=NULL&
&
temp->
i_0==p->
i_0&
j_0-1==p->
j_0）//新节点与其祖父节点相同
;
else//新节点与其祖父节点不同，或其父节点为起始节点
{
temp=（structnode*）malloc（sizeof（structnode））;
//给新节点分配空间
Copy_node（p,temp）;
//拷贝p指向的节点状态
temp->
s[temp->
i_0][temp->
j_0]=temp->
j_0-1];
//空格左移
j_0-1]=0;
j_0--;
d++;
Calculate_f（temp->
d,temp）;
//修改新节点的代价值
father=p;
//新节点指向其父节点
if（same=Search_A（closed,temp））//在closed表中找到与新节点状态相同的节点
{
if（temp->
f<
same->
f）//temp指向的节点,其代价比closed表中相同状态节点代价小，加入open表
{
Remove_p（closed,same）;
//从closed表中删除与temp指向节点状态相同的节点
Add_to_open（temp）;
sum_node++;
}
else;
}
elseif（same=Search_A（open,temp））//在open表中找到与新节点状态相同的节点
f）//temp指向的节点,其代价比open表中相同状态节点代价小，加入open表
Remove_p（open,same）;
//从open表中删除与temp指向节点状态相同的节点
else;
else//新节点为完全不同的新节点，加入open表
Add_to_open（temp）;
sum_node++;
}
}
}//end左移
j_0<
=1）//空格所在列号不大于1,可右移
j_0+1==p->
temp=（structnode*）malloc（sizeof（structnode））;
Copy_node（p,temp）;
temp->
j_0+1];
//空格右移
j_0+1]=0;
j_0++;
Calculate_f（temp->
//新节点指向其父节点
}//end右移
i_0>
=1）//空格所在列号不小于1,上移
i_0-1&
j_0==p->
i_0-1][temp->
j_0];
//空格上移
j_0]=0;
i_0--;
}//end上移
i_0<
=1）//空格所在列号不大于1,下移
i_0+1&
i_0+1][temp->
//空格下移
i_0++;
}//end下移
/*添加p指向的节点到open表中*/
voidAdd_to_open（structnode*p）
structnode*p1,*p2;
p1=open;
//初始时p1指向open表首部
p2=NULL;
if（open==NULL）//open表为空时，待插入节点即为open表第一个元素，open指向该元素
p->
next=NULL;
open=p;
else//open表不为空时，添加待插入节点，并保证open表代价递增的排序
while（p1!
p->
f>
p1->
f）
{
p2=p1;
//p2始终指向p1指向的前一个元素
p1=p1->
if（p2==NULL）//待插入节点为当前open表最小
next=open;
elseif（p1==NULL）//待插入节点为当前open表最大
p2->
next=p;
else//待插入节点介于p2、p1之间
next=p1;
/*添加p指向的节点到closed表中*/
voidAdd_to_closed（structnode*p）
if（closed==NULL）//closed表为空时，p指向节点为closed表第一个元素，closed指向该元素
closed=p;
else//closed表不为空时，直接放到closed表首部
next=closed;
/**************************************************************/
/*在open表或closed表中搜索与temp指向节点状态相同的节点，*/
/*返回搜索到的节点地址*/
structnode*Search_A（structnode*name,structnode*temp）
structnode*p1;
p1=name;
//p1指向open表或closed表
=NULL）
if（Test_A_B（p1,temp））//找到相同的节点，返回该节点地址
returnp1;
else
/**********************************************************/
/*判断两个节点A、B状态是否相同，相同则返回1，否则返回0*/
intTest_A_B（structnode*p1,structnode*p2）
inti,j,flag;
flag=1;
for（i=0;
i<
=2;
i++）
for（j=0;
j<
j++）
if（（p2->
s[i][j]）!
=（p1->
s[i][j]））{flag=0;
returnflag;
else;
/*从open表或closed表删除指定节点*/
voidRemove_p（structnode*name,structnode*p）
p1=NULL;
if（name==NULL）//如果name指向的链表为空，则不需要进行删除
return;
elseif（Test_A_B（name,p）&
name->
f==p->
f）//指定节点为name指向的链表的第一个元素
open=name->
name->
p2=name;
p1=p2->
while（p1）
if（Test_A_B（p1,p）&
f）//找到指定节点
next=p1->
/*计算某个节点状态的代价值*/
voidCalculate_f（intdeepth,structnode*p）
inti,j,temp;
temp=0;
i++）//计算所有“不在位”数码的距离和
switch（p->
s[i][j]）
case0:
temp+=abs（i-1）+abs（j-1）;
break;
case1:
temp+=abs（i-0）+abs（j-0）;
case2:
temp+=abs（i-0）+abs（j-1）;
case3:
temp+=abs（i-0）+abs（j-2）;
case4:
temp+=abs（i-1）+abs（j-2）;
case5:
temp+=abs（i-2）+abs（j-2）;
case6:
temp+=abs（i-2）+abs（j-1）;
case7:
temp+=abs（i-2）+abs（j-0）;
case8:
temp+=abs（i-1）+abs（j-0）;
h=temp;
f=deepth+p->
h;
/********************************************/
/*将p1指向的节点状态拷贝到p2指向的节点中*/
voidCopy_node（structnode*p1,structnode*p2）
inti,j;
{p2->
s[i][j]=p1->
s[i][j];
i_0=p1->
i_0;
j_0=p1->
j_0;
f=p1->
f;
d=p1->
d;
h=p1->
father=p1->
/*输出解路径*/
/***********************
升级会员 