昆明理工大学信息工程与自动化学院学生上机实验报告
（ 2012 —2013 学年第 1 学期 ）
课程名称：人工智能导论 实验地点：20##年 11月 13 日
一、 实验问题
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
初始状态: 目标状态:
请任选一种盲目搜索算法（深度优先搜索或宽度优先搜索）或 任选一种启发式搜索方法（A 算法或 A* 算法）编程求解八数码问题（初始状态任选），并对实验结果进行分析,得出结论。
二、实验目的
1. 熟悉人工智能系统中的问题求解过程；
2. 熟悉状态空间的盲目搜索和启发式搜索算法的应用；
3. 熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验原理
常用的状态空间搜索有深度优先和广度优先。广度优先是从初始状态一层一层向下找，直到找到目标为止。深度优先是按照一定的顺序前查找完一个分支，再查找另一个分支，以至找到目标为止。 广度和深度优先搜索有一个很大的缺陷就是他们都是在一个给定的状态空间中穷举。这在状态空间不大的情况下是很合适的算法，可是当状态空间十分大，且不预测的情况下就不可取了。他的效率实在太低，甚至不可完成。由于八数码问题状态空间共有9!个状态，对于八数码问题如果选定了初始状态和目标状态，有9!/2个状态要搜索，考虑到时间和空间的限制，在这里采用A*算法作为搜索策略。在这里就要用到启发式搜索
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径，提到了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
启发中的估价是用估价函数表示的，如：f(n) = g(n) + h(n)
其中f(n) 是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。 在此八数码问题中，显然g(n)就是从初始状态变换到当前状态所移动的步数，估计函数f(n)我们就可采用当前状态各个数字牌不在目标状态未知的个数，即错位数。
四、程序框图
算法流程如下：
五、实验结果及分析
{1,2,3,8,0,5,7,4,6}
A(4)
B(3) C(5) D(5)
E(2) F(4) G(4)
H(0)
六、结论
A*算法中，限制h(x)<=h*(x)的原因是是为了保证取得最优解。通过分析证明，如果问题存在最优解，则这样的限制就可保证能找到最优解。虽然这个限制可能产生无用搜索。实际上，当某一节点x的h(x)>h*(x)，则该节点就可能失去优先扩展的机会，因而导致得不到最优解。八数码问题是一个很难求解的问题，因为他需要用到复杂的C++程序编程知识，而自己在这个环节的运用上总体来说相对薄弱，所以开始时感觉很迷茫，无从下手，但是后来经过对所学知识的回顾和复习，对此问题终于找到了出口。这次实验让我深刻意识到学习C++程序编程的重要性，如果学好了这门课程，那么在以后的学习中将会轻松很多，同时让我找到了自身存在的不足，朝着这个方向努力的改善和提高自己。
七、源程序及注释
#include "Stdio.h"
#include "Conio.h"
#include "stdlib.h"
#include "math.h"
void Copy_node(struct node *p1,struct node *p2);
void Calculate_f(int deepth,struct node *p);
void Add_to_open(struct node *p);
void Add_to_closed(struct node *p);
void Remove_p(struct node *name,struct node *p);
int Test_A_B(struct node *p1,struct node *p2);
struct node * Solution_Astar(struct node *p);
void Expand_n(struct node *p);
struct node * Search_A(struct node *name,struct node *temp);
void Print_result(struct node *p);
typedef struct node
{
int s[3][3];
int i_0;
int j_0;
int f;
int d;
int h;
struct node *father;
struct node *next;
};
struct node s_0={{1,3,4,8,0,2,7,6,5},1,1,0,0,0,NULL,NULL};
struct node s_g={{1,2,3,8,0,4,7,6,5},1,1,0,0,0,NULL,NULL};
struct node *open=NULL;
struct node *closed=NULL;
int sum_node=0;
int main(void)
{
struct node s,*target;
Copy_node(&s_0,&s);
Calculate_f(0,&s);
target=Solution_Astar(&s);
if(target) Print_result(target);
else printf("问题求解失败！");
getch();
return 0;
}
struct node * Solution_Astar(struct node *p)
{
struct node *n,*temp;
Add_to_open(p);
while(open!=NULL)
{
n=open;
temp=open->next;
Add_to_closed(n);
open=temp;
if(Test_A_B(n,&s_g))
return n;
Expand_n(n);
}
return NULL;
}
void Expand_n(struct node *p)
{
struct node *temp,*same;
if(p->j_0>=1)
{
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0-1==p->j_0)
;
else
{
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0-1];
temp->s[temp->i_0][temp->j_0-1]=0;
temp->j_0--;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
{
if(temp->f<same->f)
{
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
}
else;
}
else if(same=Search_A(open,temp))
{
if(temp->f<same->f)
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
}
else
{
Add_to_open(temp);
sum_node++;
}
}
}
if(p->j_0<=1)
{
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0&&temp->j_0+1==p->j_0)
;
else
{
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0][temp->j_0+1];
temp->s[temp->i_0][temp->j_0+1]=0;
temp->j_0++;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
{
if(temp->f<same->f)
{
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
}
else;
}
else if(same=Search_A(open,temp))
{
if(temp->f<same->f)
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
}
else
{
Add_to_open(temp);
sum_node++;
}
}
}
if(p->i_0>=1)
{
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0-1&&temp->j_0==p->j_0)
;
else
{
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0-1][temp->j_0];
temp->s[temp->i_0-1][temp->j_0]=0;
temp->i_0--;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
{
if(temp->f<same->f)
{
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
}
else;
}
else if(same=Search_A(open,temp))
{
if(temp->f<same->f)
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
}
else
{
Add_to_open(temp);
sum_node++;
}
}
}
if(p->i_0<=1)
{
temp=p->father;
if(temp!=NULL&&temp->i_0==p->i_0+1&&temp->j_0==p->j_0)
;
else
{
temp=(struct node *)malloc(sizeof(struct node));
Copy_node(p,temp);
temp->s[temp->i_0][temp->j_0]=temp->s[temp->i_0+1][temp->j_0];
temp->s[temp->i_0+1][temp->j_0]=0;
temp->i_0++;
temp->d++;
Calculate_f(temp->d,temp);
temp->father=p;
if(same=Search_A(closed,temp))
{
if(temp->f<same->f)
{
Remove_p(closed,same);
Add_to_open(temp);
sum_node++;
}
else;
}
else if(same=Search_A(open,temp))
{
if(temp->f<same->f)
{
Remove_p(open,same);
Add_to_open(temp);
sum_node++;
}
else ;
}
else
{
Add_to_open(temp);
sum_node++;
}
}
}
}
void Add_to_open(struct node *p)
{
struct node *p1,*p2;
p1=open;
p2=NULL;
if(open==NULL)
{
p->next=NULL;
open=p;
}
else
{
while(p1!=NULL&&p->f>p1->f)
{
p2=p1;
p1=p1->next;
}
if(p2==NULL)
{
p->next=open;
open=p;
}
else if(p1==NULL)
{
p->next=NULL;
p2->next=p;
}
else
{
p2->next=p;
p->next=p1;
}
}
}
void Add_to_closed(struct node *p)
{
if(closed==NULL)
{
p->next=NULL;
closed=p;
}
else
{
p->next=closed;
closed=p;
}
}
struct node * Search_A(struct node *name,struct node *temp)
{
struct node *p1;
p1=name;
while(p1!=NULL)
{
if(Test_A_B(p1,temp))
return p1;
else
p1=p1->next;
}
return NULL;
}
int Test_A_B(struct node *p1,struct node *p2)
{
int i,j,flag;
flag=1;
for(i=0;i<=2;i++)
for(j=0;j<=2;j++)
{
if((p2->s[i][j])!=(p1->s[i][j])) { flag=0; return flag; }
else ;
}
return flag;
}
void Remove_p(struct node *name,struct node *p)
{
struct node *p1,*p2;
p1=NULL;
p2=NULL;
if(name==NULL)
return;
else if(Test_A_B(name,p)&&name->f==p->f)
{
open=name->next;
name->next=NULL;
return;
}
else
{
p2=name;
p1=p2->next;
while(p1)
{
if(Test_A_B(p1,p)&&p1->f==p->f)
{
p2->next=p1->next;
return;
}
else
{
p2=p1;
p1=p1->next;
}
}
return;
}
}
void Calculate_f(int deepth,struct node *p)
{
int i,j,temp;
temp=0;
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
switch(p->s[i][j])
{
case 0: temp+=abs(i-1)+abs(j-1); break;
case 1: temp+=abs(i-0)+abs(j-0); break;
case 2: temp+=abs(i-0)+abs(j-1); break;
case 3: temp+=abs(i-0)+abs(j-2); break;
case 4: temp+=abs(i-1)+abs(j-2); break;
case 5: temp+=abs(i-2)+abs(j-2); break;
case 6: temp+=abs(i-2)+abs(j-1); break;
case 7: temp+=abs(i-2)+abs(j-0); break;
case 8: temp+=abs(i-1)+abs(j-0); break;
}
}
}
p->h=temp;
p->f=deepth+p->h;
}
void Copy_node(struct node *p1,struct node *p2)
{
int i,j;
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{ p2->s[i][j]=p1->s[i][j]; }
}
p2->i_0=p1->i_0;
p2->j_0=p1->j_0;
p2->f=p1->f;
p2->d=p1->d;
p2->h=p1->h;
p2->next=p1->next;
p2->father=p1->father;
}
void Print_result(struct node *p)
{
struct node *path[100];
struct node *temp,*temp_father;
int i,j,k;
for(i=0;i<=99;i++)
path[i]=0;
temp=p;
printf("总共扩展 %d 个节点\n",sum_node);
printf("总共扩展 %d 层\n",temp->d);
printf("*************************************************\n");
printf("解路径如下：\n");
for(i=p->d;i>=0;i--)
{
path[i]=temp;
temp=temp->father;
}
for(k=0;k<=p->d;k++)
{
temp=path[k];
printf("第%d步 ",temp->d);
if(k-1>=0)
{
temp_father=path[k-1];
if(temp->i_0<temp_father->i_0) printf("->上移\n");
if(temp->i_0>temp_father->i_0) printf("->下移\n");
if(temp->j_0<temp_father->j_0) printf("->左移\n");
if(temp->j_0>temp_father->j_0) printf("->右移\n");
}
else
printf("\n");
printf("当前：f=%d，d=%d，h=%d\n",temp->f,temp->d,temp->h);
printf("当前节点状态为：\n");
for(i=0;i<=2;i++)
{
for(j=0;j<=2;j++)
{
printf("%d ",temp->s[i][j]);
}
printf("\n");
}
printf("\n");
}
}