启发式搜索算法解决八数码问题(C语言).doc
- 文档编号:709457
- 上传时间:2023-04-29
- 格式:DOC
- 页数:9
- 大小:108KB
启发式搜索算法解决八数码问题(C语言).doc
《启发式搜索算法解决八数码问题(C语言).doc》由会员分享,可在线阅读,更多相关《启发式搜索算法解决八数码问题(C语言).doc(9页珍藏版)》请在冰点文库上搜索。
1、程序源代码
#include
#include
structnode{
inta[3][3];//用二维数组存放8数码
inthx;//函数h(x)的值,表示与目标状态的差距
structnode*parent;//指向父结点的指针
structnode*next;//指向链表中下一个结点的指针
};
//------------------hx函数-------------------//
inthx(ints[3][3])
{//函数说明:
计算s与目标状态的差距值
inti,j;
inthx=0;
intsg[3][3]={1,2,3,8,0,4,7,6,5};
for(i=0;i<3;i++)
for(j=0;j<3;j++)
if(s[i][j]!
=sg[i][j])
hx++;
returnhx;
}
//-------------hx函数end----------------------//
//-------------extend扩展函数----------------//
structnode*extend(node*ex)
{//函数说明:
扩展ex指向的结点,并将扩展所得结点组成一条
//单链表,head指向该链表首结点,并且作为返回值
inti,j,m,n;//循环变量
intt;//临时替换变量
intflag=0;
intx[3][3];//临时存放二维数组
structnode*p,*q,*head;
head=(node*)malloc(sizeof(node));//head
p=head;
q=head;
head->next=NULL;//初始化
for(i=0;i<3;i++)//找到二维数组中0的位置
{
for(j=0;j<3;j++)
if(ex->a[i][j]==0)
{
flag=1;
break;
}
if(flag==1)
break;
}
for(m=0;m<3;m++)//将ex->a赋给x
for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
//根据0的位置的不同,对x进行相应的变换
//情况1
if(i-1>=0)
{
t=x[i][j];x[i][j]=x[i-1][j];x[i-1][j]=t;
flag=0;
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!
=9)
{
q=(node*)malloc(sizeof(node));
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
q->next=NULL;
p->next=q;
p=p->next;
}
}
//情况2
for(m=0;m<3;m++)//将ex->a重新赋给x,即还原x
for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
if(i+1<=2)
{
t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t;
flag=0;
for(m=0;m<3;m++)
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!
=9)
{
q=(node*)malloc(sizeof(node));
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
q->next=NULL;
p->next=q;
p=p->next;
}
}
//情况3
for(m=0;m<3;m++)//将ex->a重新赋给x,即还原x
for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
if(j-1>=0)
{
t=x[i][j];x[i][j]=x[i][j-1];x[i][j-1]=t;
flag=0;
for(m=0;m<3;m++)
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!
=9)
{
q=(node*)malloc(sizeof(node));
for(m=0;m<3;m++)//将x赋给a
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
q->next=NULL;
p->next=q;
p=p->next;
}
}
//情况4
for(m=0;m<3;m++)//将ex->a重新赋给x,即还原x
for(n=0;n<3;n++)
x[m][n]=ex->a[m][n];
if(j+1<=2)
{
t=x[i][j];x[i][j]=x[i][j+1];x[i][j+1]=t;
flag=0;
for(m=0;m<3;m++)
for(n=0;n<3;n++)
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!
=9)
{
q=(node*)malloc(sizeof(node));
for(m=0;m<3;m++)
for(n=0;n<3;n++)
q->a[m][n]=x[m][n];
q->parent=ex;
q->hx=hx(q->a);
q->next=NULL;
p->next=q;
p=p->next;
}
}
head=head->next;
returnhead;
}
//---------------extend函数end-----------------------//
//----------------insert函数-------------------------//
node*insert(node*open,node*head)
{//函数说明:
将head链表的结点依次插入到open链表相应的位置,
//使open表中的结点按从小到大排序。
函数返回open指针
node*p,*q;//p、q均指向open表中的结点,p指向q所指的前一个结点
inti,j;
intflag=0;
if(open==NULL)//初始状态,open表为空
{//首先将head表第一个结点直接放入open表中
open=head;
q=head;
head=head->next;
q->next=NULL;
//再插入第二个结点
if(head->hx
{//插入到首结点位置
open=head;
head=head->next;
open->next=q;
}
else
{//或者第二个结点的位置
q->next=head;
head=head->next;
q=q->next;
q->next=NULL;
p=open;
}
p=open;
q=open->next;
}//endif
while(head!
=NULL)
{
q=open;
if(head->hx
{
open=head;
head=head->next;
open->next=q;
continue;
}
else{q=q->next;p=open;}//否则,q指像第二个结点,p指向q前一个结点
while(q->next!
=NULL)//将head的一个结点插入到链表中(非表尾的位置)
{
if(q->hx
{
q=q->next;
p=p->next;
}
else
{
p->next=head;
head=head->next;
p->next->next=q;
break;
}
}
if(q->next==NULL)//将head的一个结点插入到表尾
{
if(q->hx>head->hx)
{
p->next=head;
head=head->next;
p->next->next=q;
}
else
{
q->next=head;
head=head->next;
q->next->next=NULL;
}
}//if
}//while
returnopen;
}//insert
//-----------------insert函数end--------------------//
//---------------------main-----------------------//
voidmain()
{
inti,j;
nodes0;
node*open,*close;
node*p,*q;
node*newlist;
printf("请输入初始状态的8数码(按每行从左往右依次输入,用0表示空格):
\n");
for(i=0;i<3;i++)
for(j=0;j<3;j++)
scanf("%d",&s0.a[i][j]);
s0.parent=(node*)malloc(sizeof(node));
s0.parent->hx=9;
s0.hx=hx(s0.a);
open=&s0;
p=&s0;
if(open->hx==0)
{
printf("该状态已为最终状态!
\n");
return;
}
q=&s0;
close=&s0;
open=NULL;
newlist=extend(q);//newlist指向新扩展出来的链表
open=insert(open,newlist);//将扩展出来的结点插入到open表中
while
(1)
{
q->next=open;//q始终指向close表尾结点。
将open表的第一个元素加到close表
open=open->next;
q=q->next;
q->next=NULL;
if(q->hx==0)
{
printf("\n搜索成功!
\n");
break;
}
newlist=extend(q);//对close表最后一个结点进行扩展,扩展得到的链表接到open表尾
open=insert(open,newlist);//将扩展的结点按顺序插入到open表中
}
p=close;
printf("择优搜索过程如下:
\n");
while(p!
=NULL)
{
for(i=0;i<3;i++)
{
for(j=0;j<3;j++)
printf("%d",p->a[i][j]);
printf("\n");
}
printf("\n");
p=p->next;
}
}
2、程序运行结果截图
截图1:
初始态为:
283
14
765
运行结果如
右图所示:
截图2:
初始状态为283时,程序运行结果如下:
164
75
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 启发式 搜索 算法 解决 数码 问题 语言