资源描述:
《人工智能A星算法解决八数码难题程序代码.docx》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
1、#include"Stdio.h"#include"Conio.h"#include"stdlib.h"#include"math.h"voidCopy_node(structnode*p1,structnode*p2);voidCalculate_f(intdeepth,structnode*p);voidAdd_to_open(structnode*p);voidAdd_to_closed(structnode*p);voidRemove_p(structnode*name,structnode*p);intTest_A_B(st
2、ructnode*p1,structnode*p2);structnode*Search_A(structnode*name,structnode*temp);voidPrint_result(structnode*p);structnode//定义8数码的节点状态{ints[3][3];//当前8数码的状态inti_0;//当前空格所在行号intj_0;//当前空格所在列号intf;//当前代价值intd;//当前节点深度inth;//启发信息,采用数码"不在位"距离和structnode*father;//指向解路径上该节点的父节
3、点structnode*next;//指向所在open或closed表中的下一个元素};structnodes_0={{2,8,3,1,6,4,7,0,5},2,1,0,0,0,NULL,NULL};//定义初始状态structnodes_g={{1,2,3,8,0,4,7,6,5},1,1,0,0,0,NULL,NULL};//定义目标状态structnode*open=NULL;//建立open表指针structnode*closed=NULL;//建立closed表指针intsum_node=0;//用于记录扩展节点总数//**
4、*********************************************************//********************************************//**********************主函数开始**********************//********************************************//***********************************************************voidmain(
5、){intbingo=0;//定义查找成功标志,bingo=1,成功structnodes;//定义头结点sstructnode*target,*n,*ls,*temp,*same;//定义结构体指针Copy_node(&s_0,&s);//复制初始状s_0态给头结点sCalculate_f(0,&s);//计算头结点的代价值Add_to_open(&s);//将头结点s放入open表while(open!=NULL)//只要open表不为空,进行以下循环{n=open;//n指向open表中当前要扩展的元素ls=open->next
6、;Add_to_closed(n);open=ls;//将n指向的节点放入closed表中if(Test_A_B(n,&s_g))//当前n指向节点为目标时,跳出程序结束;否则,继续下面的步骤{bingo=1;break;}elseif(n->j_0>=1)//空格所在列号不小于1,可左移{temp=n->father;if(temp!=NULL&&temp->i_0==n->i_0&&temp->j_0-1==n->j_0)//新节点与其祖父节点相同;else//新节点与其祖父节点不同,或其父节点为起始节点{temp=(struct
7、node*)malloc(sizeof(structnode));//给新节点分配空间Copy_node(n,temp);//拷贝n指向的节点状态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=n;//新节点指向其父节点if(same=Se
8、arch_A(closed,temp))//在closed表中找到与新节点状态相同的节点{if(temp->ff)//temp指向的节点,其代价比closed表中相同状态节点代价小,加入open表{Remo