资源描述：
《人工智能：八数码难题的启发式搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、人工智能基础大作业----八数码难题学院:数学与计算机科学学院2016.12.20一、实验名称八数码难题的启发式搜索二、实验目的八数码问题：在3×3的方格棋盘上，摆放着1到8这八个数码，有1个方格是空的，其初始状态如图1所示，要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。要求：1.熟悉人工智能系统中的问题求解过程；2.熟悉状态空间的启发式搜索算法的应用；3.熟悉对八数码问题的建模、求解及编程语言的应用。三、实验设备及软件环境1.实验编程工具：VC++6.02.实验环境：Windows764位一、实
2、验方法：启发式搜索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<
3、stdio.h>#include#include#includetypedefstructnode{inti,cost,degree,exp,father;inta[3][3];structnode*bef,*late;structnode*son;}treenode;intflag=0,count=1,num=0,i=0;voidset(treenode*s);voidcpynode(treenode*s1,treenode*s2);voidadd1(treenode*s,tree
4、node*open);voidadjust1(treenode*close);voidjscost(treenode*s);voidtiaozheng(treenode*open);voidsortopen(treenode*open);inttest(treenode*s1,treenode*s2);voidposition(treenode*s,treenode*open,treenode*close,treenode*s1);voidprintstr(treenode*open);intsearch(treenode*s1,treeno
5、de*s2);voidinput(treenode*s);intcmpnode(treenode*s1,treenode*s2);voidprint(treenode*s);voidadd(treenode*s,treenode*close);voidxuhao(treenode*s);voidextend(treenode*r1,treenode*s,treenode*s1,treenode*open,treenode*close);voidmain(){treenode*s0,*s1,*s;treenode*open,*close,*op
6、end,*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("请输入八数码的初始状态：（以空格为分隔）
7、");input(s0);printf("请输入八数码的目标状态：（以空格为分隔）");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
8、);};};if(open->late!=NULL){printf("搜索过程如下：");adjust1(close);printstr(close);prin
