八数码问题C代码 可直接运行

八数码问题代码，用全局择优解决八数码问题，启发函数采用曼哈顿路径和计算不同节点两种方法。对学习人工智能图搜索应该很有帮助。

#include
#include
#include
#define SIZE 10000
int start[3][3]={0};
int end[3][3]={0};
struct node 
{
	int index;//结点序号
    int p_index;//父结点序号 
    int matrix[3][3];// 八数码状态
    int h_function;//启发式函数值
};
node open[SIZE]; //存放已经生成的未考察的节点
int openlength=0;
int openlast=0;//open表最后一个数据的位置
node closed[SIZE]; //存放已经考察过得节点
int closedlength=0;
int closedlast=0;//closed表最后一个数据的位置
int fail=0;//失败标记，fail=1则搜索失败
int n_index=0;//节点标记序号
int extend[3][3]={0};
int n_root=0;
struct Root{
	node resultRoot[SIZE];
	int length;
};
void init（Root &r）{
	r.length=0;
};
void read（）{
	printf（“输入初始节点：\n“）;
	int ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			scanf（“%d“&start[i][j]）;
		}
	}
	printf（“输入目标节点：\n“）;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			scanf（“%d“&end[i][j]）;
		}
	}
	printf（“\n“）;
}
int isEqual（int a[][3]int b[][3]）{//判断节点是否与目标节点相同
	int ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			if（a[i][j]!=b[i][j]）{
				return 0;
			}
		}
	}
	return 1;
}
int arouse（int a[][3]）{//用曼哈顿路径求启发函数
	int distance=0;
	int ij;
	int locate（int m[][3]int n）;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			int location=locate（enda[i][j]）;
			int i1=location/3;
			int j1=location%3;
			distance+=（int）fabs（i1-i）+（int）fabs（j1-j）;
		}
	}
	return distance;
}
void copy_matrix（int a[][3]int b[][3]）{
	int ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			a[i][j]=b[i][j];
		}
	}
}
void inopen（int a[][3]）{//节点进入open表，同时节点编号置0，配以指向父节点的指针，同时openlength和openlast加一
	copy_matrix（open[openlast].matrixextend）;//将第二个参数矩阵copy到第一个
	open[openlast].index=0;//放入open表中，序号为0
	open[openlast].p_index=n_index;
	open[openlast].h_function=arouse（extend）;
	openlength++;
	openlast++;
}
void cut（）{//将open[0]放入closed表中
	closed[closedlast].index=n_index;
	closed[closedlast].p_index=open[0].p_index;
	closed[closedlast].h_function=open[0].h_function;
	copy_matrix（closed[closedlast].matrixopen[0].matrix）;
	open[0].index=-1;
	openlength--;
	closedlength++;
	closedlast++;
}
int locate（int a[][3]int b）{//返回0所在位置
	int ij;
	for（i=0;i<3;i++）{
		for（j=0;j<3;j++）{
			if（a[i][j]==b）
				return i*3+j;
		}
	}
	return -1;
}
void exchange（int *aint *b）{
	int t;
	t=*a;
	*a=*b;
	*b=t;
}
void copy（node &anode &b）{
	a.index=b.index;
	a.p_index=b.p_index;
	a.h_function=b.h_function;
	copy_matrix（a.matrixb.matrix）;
}
void adjust（）{//调整open表和closed表
	int i;
	for（i=0;i		if（open[i].index==-1）{
			copy（open[i]open[openlast-1]）;
			openlast--;
		}
	}
	for（i=0;i		if（closed[i].index==-1）{
			copy（closed[i]closed[closedlast]）;
			closedlast--;
		}
	}
}
void exchangeNode（int iint j）{
	node a;
	copy（aopen[i]）;
	copy（open[i]open[j]）;
	copy（open[j]a）;
}
void sort（）{//对open表中元素以升序排列
	int ij;
	for（i=openlength-1;i>0;i--）{
		for（j=0;j			if（open[j].h_function>open[j+1].h_function）{
				exchangeNode（jj+1）;
			}
		}
	}
}
int seek

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----
     文件        6146  2010-11-28 00:34  八数码.cpp
     文件         240  2010-11-28 00:36  启发函数.txt