人工智能 八数码问题 A*算法 C语言

人工智能实验 A*算法 算法可能不完美但是自己一点点写出来的 希望能对你有所启发

#include
#include
#include

typedef struct data
{
	        int  number[9];            //八数码的九个数
			int  death;                //用于估价函数的深度信息
			int  w_number;             //用于估价函数的不在位信息
			int  f_value;              //最终值越小越好  
	   struct data  *parent;           //当前节点的父节点

}Tree_node*Tree;                     //定义结构体节点为 Tree_node 和指向此类结构体的指针Tree

/***************open表的建立***存放已经生成但未扩展节点********/
typedef struct open_list
{        
	   Tree open_node[1000000];              //用于储存节点Tree_open的open表，并设置其容量为100
	   int  length;                      //open表当前长度  初始值为-1
}list_o*list_open_node;                      //定义结构体节点为 list_k 和指向此类结构体的指针list_node

list_open_node open;                          //定义一个open表

/**************close表的建立**存放已扩展或将要扩展的节点******/
typedef struct close_list
{        
	   Tree close_node[1000000];              //用于储存节点close表，并设置其容量为100
	   int  length;                      //open表当前长度  初始值为-1
}list_c*list_close_node;                      //定义结构体节点为 list_c和指向此类结构体的指针list_close_node

list_close_node close;                          //定义一个open表



Tree bt;                                 //定义一个根节点 所有的扩展节点都是在此基础上建立的      
int num=0;

int first[9]={578306124};//初始结点 26步 
// int first[9]={318764025};//21步 

// int first[9]={834265170};//13步 

//int first[9]={216408753};//18步    

//   int first[9]={203184765};    //4步 

    int final[9]={123804765};
	int order[100][9];


 /**** *** x-3 *** ******/
 /**** x-1  x  x+1 ******/
 /**** *** x+3 *** ******/

int direction[4] ={-33-11};    //可移动的四个方向   分别表示上移 下移 左移 右移


 /*****/
int find（Tree node）               //寻找八数码中0所在的位置 
{
	int i;
	for（i=0;i<9;i++）
	{
		if（node->number[i]==0）
			return i;                      //返回0所在的位置
	}
	return 0;
}

/************节点存入open表**********/
void  save_open（Tree p）                     
{
	open->open_node[open->length+1]=p;
	open->length++;
}

/************open表判断是否为空**********/
int is_open_blank（list_open_node open）
{
	if（open->length==-1）
		return 1;
	else
		return 0;
}
/************判断新生成节点是否为目标节点**********/
int  is_goal（Tree p）
{
	int i;
	for（i=0;i<9;i++）
	{  
		if（final[i]!=p->number[i]）
			return 0;
	}
	 return 1;
}

/************节点存入close表**********/
void  save_close（Tree p）                           
{
	close->close_node[close->length+1]=p;
	close->length++;
}

/*******************单纯不在位估价******************
int w_value（Tree p）              //估价函数 
{
    int in_right_number=0;
	for（i=0;i<9;i++）
	{  
		if（final[i]!=p->number[i]）
		   n_right_number++;
	}
	 return n_right_number;    
}*********/



int find_position（int num）
{
	int i;
	for（i=0;i<9;i++）
	{
       if（num==final[i]）
		   return i;
	}
}


/*******************估价优化***************************/
int w_value（Tree p）              //估价函数 
{
	
	int now_linenow_columnfinal_linefinal_colum

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

     文件      33792  2017-05-09 21:46  八数码\Debug\vc60.idb

     文件      53248  2017-05-09 21:45  八数码\Debug\vc60.pdb

     文件     204870  2017-05-09 21:46  八数码\Debug\yiwei.exe

     文件     199384  2017-05-09 21:46  八数码\Debug\yiwei.ilk

     文件      15945  2017-05-09 21:45  八数码\Debug\yiwei.obj

     文件     190292  2017-05-09 21:45  八数码\Debug\yiwei.pch

     文件     459776  2017-05-09 21:46  八数码\Debug\yiwei.pdb

     文件       9380  2017-05-04 17:53  八数码\yiwei.c

     文件       3387  2017-05-09 21:45  八数码\yiwei.dsp

     文件        518  2017-05-09 21:46  八数码\yiwei.dsw

     文件      50176  2017-05-09 21:46  八数码\yiwei.ncb

     文件      48640  2017-05-09 21:46  八数码\yiwei.opt

     文件        749  2017-05-09 21:46  八数码\yiwei.plg

     文件      27583  2017-05-09 21:49  八数码\算法思想.docx

     目录          0  2017-05-09 21:46  八数码\Debug

     目录          0  2017-05-09 21:49  八数码

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

              1297740                    16