第1页 / 共9页
第2页 / 共9页
第3页 / 共9页
第4页 / 共9页
第5页 / 共9页
第6页 / 共9页
第7页 / 共9页
第8页 / 共9页
启发式搜索算法解决八数码问题(C语言源代码.doc
1、程序源代码
#include
#include
struct node{
int a[3][3];//用二维数组存放 8 数码
int hx;//函数 h（x）的值，表示与目标状态的差距
struct node *parent;//指向父结点的指针
struct node *next;//指向链表中下一个结点的指针
};
//------------------hx 函数-------------------//
int hx(int s[3][3])
{//函数说明：计算 s 与目标状态的差距值
int i,j;
int hx=0;
int sg[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++;
return hx;
}
//-------------hx 函数 end----------------------//
//-------------extend 扩展函数----------------//
struct node *extend(node *ex)
{ //函数说明：扩展 ex 指向的结点，并将扩展所得结点组成一条
//单链表，head 指向该链表首结点，并且作为返回值
//临时替换变量
int i,j,m,n; //循环变量
int t;
int flag=0;
int x[3][3];//临时存放二维数组
struct node *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;
return head;
}
//---------------extend 函数 end-----------------------//
//----------------insert 函数-------------------------//
node* insert(node *open,node * head)
{ //函数说明：将 head 链表的结点依次插入到 open 链表相应的位置，
//使 open 表中的结点按从小到大排序。函数返回 open 指针
node *p,*q;//p、q 均指向 open 表中的结点，p 指向 q 所指的前一个结点
int i,j;
int flag=0;
if(open==NULL)//初始状态，open 表为空
{ //首先将 head 表第一个结点直接放入 open 表中
open=head;
q=head;
head=head->next;
q->next=NULL;
//再插入第二个结点
if(head->hxhx)
{//插入到首结点位置
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;
} //end if
while(head!=NULL)
{
q=open;
if(head->hxhx) //插入到表头
{
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->hxhx)
{
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;
q->next=head;
head=head->next;
q->next->next=NULL;
}
else
{
}
}//if
}//while
return open;
}//insert
//-----------------insert 函数 end--------------------//
//---------------------main-----------------------//
void main()
{
int i,j;
node s0;
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：
初始态为：
2
1
7
运行结果如
右图所示：
3
4
5
8
6
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
