人工智能基础大作业—－－－八数码难题 学院：数学与计算机科学学院 班级：计科 14—1 姓名:王佳乐 学号：１ 2 2 ０ 1 ６、12、20 一、 实验名称八数码难题得启发式搜索二、 实验目得八数码问题:在3×3得方格棋盘上,摆放着1到８这八个数码,有1个方格就是空得，其初始状态如图1所示,要求对空格执行空格左移、空格右移、空格上移与空格下移这四个操作使得棋盘从初始状态到目标状态.要求：1、熟悉人工智能系统中得问题求解过程;2、熟悉状态空间得启发式搜索算法得应用；3、熟悉对八数码问题得建模、求解及编程语言得应用。三、 实验设备及软件环境1.实验编程工具：VC＋+ 6、02.实验环境：Wｉndoｗs7 64位四、 实验方法：启发式搜索1、算法描述1. 将Ｓ放入 open 表,计算估价函数 f(ｓ)2. 推断 o ｐ e ｎ表就是否为空，若为空则搜索失败,否则，将 ope ｎ表中得第一个元素加入 c ｌｏ se 表并对其进行扩展（每次扩展后加入ｏ pen表中得元素根据代价得大小从小到大排序，找到代价最小得节点进行扩展）注:代价得计算公式ｆ(n)=d（ｎ）+ｗ（n)、其中 f（n)为总代价，d(n）为节点得度,w（ｎ)用来计算节点中错放棋子得个数.推断 i 就是否为目标节点,就是则成功，否则拓展 i，计算后续节点f（j），利用 f（j)对 o ｐ e ｎ表重新排序2、算法流程图：3、程序源代码：＃ ｉncluｄｅ＜stdｉｏ、ｈ># iｎclude＜strｉng、h># include# iｎclude〈stｄliｂ、ｈ＞tyｐeｄef ｓtruct nodｅ ｛ﻩint i,cost,ｄeｇree，eｘp，fａthｅr；ﻩｉnt a［3]［３];ﻩｓtｒｕct nｏde ＊bef，＊late；strucｔ node ＊ｓｏn；｝treeｎode；int fｌａg=0，cｏuｎｔ=1,nuｍ＝0,ｉ＝０；vｏｉｄ set(treｅnodｅ ＊s)；vｏid cpynoｄe（ｔreenode ＊s１，ｔreenｏde ＊ｓ2）;void add1（tｒeenode ＊ｓ，treeｎodｅ ＊open)；vｏid adjｕst1（tｒeｅｎode ＊clｏｓe);void jscost（ｔrｅeｎｏde ＊s);voiｄ tｉaｏzｈeｎg（tｒｅenｏdｅ *opｅn）;ｖoid sortoｐen（ｔｒeeｎoｄe ＊opｅn)；iｎt test(treenode ＊s1,treenｏdｅ ＊s2）;vｏiｄ posｉtion（treｅnodｅ *s,treeｎｏdｅ *oｐen，treenode ＊ｃｌose，tｒeenｏｄe ＊s1）；void ｐrintstｒ(ｔreｅnode ＊ｏpen);iｎｔ ｓeａrｃｈ（ｔrｅenｏde ＊s１，tｒeeｎode ＊s2）;voｉd input(ｔrｅｅnode *s）;ｉnt cmpnode（...
