人工智能基础
大作业
----八数码难题
学院:数学与计算机科学学院
2016.12.20
一、实验名称
八数码难题的启发式搜索
二、实验目的
八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。
要求：1.熟悉人工智能系统中的问题求解过程；
2.熟悉状态空间的启发式搜索算法的应用；
3.熟悉对八数码问题的建模、求解及编程语言的应用。
三、实验设备及软件环境
1.实验编程工具：VC++ 6.0
2.实验环境：Windows7 64位
四、实验方法：启发式搜索
1.算法描述
1.将S放入open表，计算估价函数f(s)
2.判断open表是否为空，若为空则搜索失败，否则，将open表中的第一
个元素加入close表并对其进行扩展（每次扩展后加入open表中的元素
按照代价的大小从小到大排序，找到代价最小的节点进行扩展）
注：代价的计算公式f(n)=d(n)+w(n).其中f(n)为总代价，d(n)为节点
的度，w(n)用来计算节点中错放棋子的个数。
判断i是否为目标节点，是则成功，否则拓展i，计算后续节点f(j)，
利用f(j)对open表重新排序
2.算法流程图：
3.程序源代码：
# include
# include
# include
# include
typedef struct node {
int i,cost,degree,exp,father;
int a[3][3];
struct node *bef,*late;
struct node *son;
}treenode;
int flag=0,count=1,num=0,i=0;
void set(treenode *s);
void cpynode(treenode *s1,treenode *s2);
void add1(treenode *s,treenode *open);
void adjust1(treenode *close);
void jscost(treenode *s);
void tiaozheng(treenode *open);
void sortopen(treenode *open);
int test(treenode *s1,treenode *s2);
void position(treenode *s,treenode *open,treenode
*close,treenode *s1);
void printstr(treenode *open);
int search(treenode *s1,treenode *s2);
void input(treenode *s);
int cmpnode(treenode *s1,treenode *s2);
void print(treenode *s);
void add(treenode *s,treenode *close);
void xuhao(treenode *s);
void extend(treenode *r1,treenode *s,treenode *s1,treenode *open,treenode *close);
void main() {
treenode *s0,*s1,*s;
treenode *open,*close,*opend,*closed;
open=(treenode*)malloc(sizeof(treenode));
close=(treenode*)malloc(sizeof(treenode));
open->late=NULL;
close->late=NULL;
opend=open;
closed=close;
s0=(treenode*)malloc(sizeof(treenode));
set (s0);
s1=(treenode*)malloc(sizeof(treenode));
set(s1);
printf("请输入八数码的初始状态：（以空格为分隔）\n");
input (s0);
printf("请输入八数码的目标状态：（以空格为分隔）\n");
input(s1);
xuhao(s0);
add (s0,opend);
while(open->late!=NULL && flag==0) {
s=(treenode*)malloc(sizeof(treenode));
cpynode(s,open->late);
open=open->late;
add(s,close);
if(test(s,s1)==0){
flag=1; }
else{
position(s,open,close,s1);
sortopen(open); };};
if(open->late!=NULL) {
printf("搜索过程如下：\n ");
adjust1(close);
printstr(close);
printf("\n%d 步,%d 个节点\n",num,count);} else {
printf("查找错误 ! \n");}; }
void set(treenode *s) {
s->i=i;
s->father=0;
s->degree=0;
s->bef=NULL;
s->son=NULL;
s->late=NULL; };
void input(treenode *s) {
int j,k;
for(j=0;j<3;j++)
for(k=0;k<3;k++)
scanf("%d",&s->a[j][k]); };
