启发式搜索算法解决八数码问题(C语言)
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
for(j=0;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
{
for(j=0;j
if(ex->a[i][j]==0)
{
flag=1;
break;
}
if(flag==1)
break;
}
for(m=0;ma赋给x
for(n=0;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
for(n=0;n
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m
for(n=0;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;ma重新赋给x，即还原x
for(n=0;n
x[m][n]=ex->a[m][n];
if(i+1
{
t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t;
flag=0;
for(m=0;m
for(n=0;n
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m
for(n=0;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;ma重新赋给x，即还原x
for(n=0;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
for(n=0;n
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m
for(n=0;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;ma重新赋给x，即还原x
for(n=0;n
x[m][n]=ex->a[m][n];
if(j+1
{
t=x[i][j];x[i][j]=x[i][j+1];x[i][j+1]=t;
flag=0;
for(m=0;m
for(n=0;n
if(x[m][n]==ex->parent->a[m][n])
flag++;
if(flag!=9)
{
q=(node *)malloc(sizeof(node));
for(m=0;m
for(n=0;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;
}
else
{
q->next=head;
head=head->next;
q->next->next=NULL;
}
}//if
}//while
return open;
}//insert
//-----------------insert函数 end--------------------//
//---------------------main-----------------------//
void main()
{
int i,j;
node s0;
node *open,*close;
node *p,*q;
node *newlist;
printf(
for(j=0;j
scanf(
s0.parent=(node *)malloc(sizeof(node));
s0.parent->hx=9;
s0.hx=hx(s0.a);
open=&s0;
p=&s0;
if(open->hx==0)
{
printf(
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(
break;
}
newlist=extend(q);//对close表最后一个结点进行扩展，扩展得到的链表接到open表尾
open=insert(open,newlist);//将扩展的结点按顺序插入到open表中
}
p=close;
printf(
while(p!=NULL)
{
for(i=0;i
{
for(j=0;j
printf(
printf(
}
printf(
p=p->next;
}
}
2、程序运行结果截图
截图1：
初始态为：
2 8 3
1 4
7 6 5
运行结果如
右图所示：
截图2：
初始状态为 2 8 3 时，程序运行结果如下： 1 6 4
7 5