八数码 A*算法 附报告

以A*算法作为本程序的算法，利用f=g+h;其中g代表每个结点的深度，h代表该结点与目标结点相差的位置。利用open，close表作为辅助。把每个同一层次的结点放进open表中，再选取最小代价放入close表中。close表中的结点即为最优路径中的一个结点。直到找出目标的结点，然后打印。 ① 判断OPEN表是否为空的函数 ② 求OPEN表中估价函数值最小的结点的函数 ③ 判断初始状态是否可到达目标状态的函数 ④ 求估价函数值p(n)-曼哈顿距离 ⑤ 产生新状态的函数，共四个，空格上/下/左/右移动 ⑥ 判重函数，判断新节点在OPEN,CLOSE表中是否已经有了 ⑦

#include
#include
#include
#include
typedef struct Node
{
	int p;        //曼哈顿距离
	int g;        //代价
	int f;        //估价函数值
	int flag;     //标志结点是否被访问过，1为访问过，0为没访问过
	int num_state[9];//当前状态
	struct Node *father; //指向父亲结点
}eight_node*eight_number;

////定义open和close表结构体
typedef struct Node1
{
   eight_node data;
   struct Node1 *next;
}LNode*linkNode;

int destination_num[] ={123456780};  //目标状态

//添加新的结点到open表close表中
void add_node（linkNode &opeight_number newNode）
{
	linkNode p;
	int i;
	p=（linkNode）malloc（sizeof（LNode））;
	p->data.f=newNode->f;
	p->data.father=newNode->father;
	p->data.flag=newNode->flag;
	p->data.g=newNode->g;
	for（i=0;i<9;i++）
	   p->data.num_state[i]=newNode->num_state[i];
	p->data.p=newNod

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件      15319  2008-12-21 13:00  Eight_Puzzle.cpp

     文件      32256  2009-05-29 21:16  AI_课程设计报告.doc

----------- ---------  ---------- -----  ----

                47575                    2