人工智能基础大作业----八数码难题学院:数学与计算机科学学院班级:计科14-1姓名:王佳乐学号:2.12.20一、试验名称八数码难题启发式搜索二、试验目八数码问题:在3×3方格棋盘上,摆放着1到8这八个数码,有1个方格是空,其初始状态如图1所表示,要求对空格实施空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态。要求:1.熟悉人工智能系统中问题求解过程;2.熟悉状态空间启发式搜索算法应用;3.熟悉对八数码问题建模、求解及编程语言应用。三、试验设备及软件环境1.试验编程工具:VC++6.02.试验环境:Windows764位四、试验方法:启发式搜索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<stdio.h>#include<string.h>#include<malloc.h>#include<stdlib.h>typedefstructnode{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,treenode*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,treenode*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,*opend,*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("请输入八数码初始状态:（以空格为分隔）\n");input(s0);printf("请输入八数码目标状态:（以空格为分隔）\n");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){