人工智能基础大作业----八数码难题一、实验名称八数码难题的启发式搜索二、实验目的八数码问题：在3×3的方格棋盘上,摆放着1到8这八个数码，有1个方格是空的，其初始状态如图１所示,要求对空格执行空格左移、空格右移、空格上移和空格下移这四个操作使得棋盘从初始状态到目标状态
要求：1．熟悉人工智能系统中的问题求解过程；2
熟悉状态空间的启发式搜索算法的应用;3．熟悉对八数码问题的建模、求解及编程语言的应用
三、实验设备及软件环境1
实验编程工具：VＣ+＋６
实验环境:Wｉｎdｏwｓ7６4位四、实验方法：启发式搜索1
将S放入opｅｎ表,计算估价函数f（ｓ)2
判断open表是否为空,若为空则搜索失败,否则，将opｅn表中的第一个元素加入cｌose表并对其进行扩展（每次扩展后加入oｐen表中的元素按照代价的大小从小到大排序，找到代价最小的节点进行扩展）注：代价的计算公式f（n)=d(ｎ)+w(ｎ)
其中f（n)为总代价，d(n)为节点的度，ｗ(n)用来计算节点中错放棋子的个数
判断i是否为目标节点,是则成功,否则拓展i,计算后续节点f(j),利用f(ｊ)对opｅn表重新排序2
算法流程图:3
程序源代码：#inclｕdelａtｅ＝ＮULL；cloｓｅ－>late＝NUＬL；opｅnｄ=ｏpen;ﻩcｌｏseｄ=ｃlose；s0＝(ｔｒｅｅnoｄe＊）mａllｏc（ｓiｚeoｆ(trｅenoｄe));set（s0);ﻩs1=（tｒeｅnode*）malloc（sｉzeoｆ(ｔreeｎｏde));set(s1);ﻩprintf（"请输入八数码的初始状态：(以空格为分隔）\n＂)；ﻩｉnｐut(ｓ０）;ﻩpriｎｔf（＂请输入八数码的目标状态:(以空格为分隔)\ｎ");ﻩｉｎput(ｓ１）;xuｈａｏ(ｓ0);ﻩaｄd(s０，ｏpｅnd）;ﻩﻩwhｉle(oｐen->
