武汉理工大学人功智能概论八数码实验报告.doc

:..武汉理工大学学生实验报告书计算机科学与技术学院实验课程名称实验名称开课学院指导老师姓名学生姓名学 号学生专业班级人工智能概论B八数码问题20162017学年第一学期一、实验要求及问题描述采取分组形式,2人一组,一人使用盲目搜索中的宽度优先搜索算法,另一人使用启发式搜索中的全局择优搜索或A*算法。每组提交一份大作业报告,该报告包括设计、实现、测试、实验对比结果分析、结论、个人体会与总结。提交截止时间:,给出求解结果。例如:对于如下具体八数码问题:1324567812384765通过设计启发函数,编程实现求解过程,如果问题有解,给出数码移动过程,否则,报告问题无解。250123873804641765二、、 建立只有初始节点So的搜索图,并将S。放入OPEN表中;2、 建立CLOSE表并置空;3、 对OPEN表进行判断,若OPEN表为空,则无解;4、 将OPEN表中的第一个节点移出,放入CLOSE表中,记为节点n;5、 判断节点n是否为口标节点。是,则有解,解为沿n到S。的路径,否,则进行步骤6;6、 由节点n生成一组不是n的祖先的后继节点,记为集合P,将P中节点作为n的后继加入搜索图;7、 对于在OPEN表和CLOSE表中没有出现过的集合P中的节点,设置指向节点n的指针,把这些节点放入OPEN表屮;对于在OPEN表和CLOSE表屮已经出现过的P中的节点,确定是否修改指向父节点的指针;8、 重拍OPEN表节点顺序;9、 〃宽度优先搜索中,八数码地图节点结构体structEightDigit{intCube[3][3];tion;structEightDigit*Parent;};〃全局择优搜索中,八数码节点结构体structnode{intindex;//结点序号intp_index;//父结点序号intmatrix[3][3];//八数码状态inth_function;//启发式函数值};nodeopen[SIZE];//存放已经生成的未考察的节点nodeclosed[SIZE];//〃计算节点启发式函数值intarouse(inta[][3]){intnum=0;inti,j;for(i=0;i<3;i++){for(j=0;j<3;j++){if(a[i][j]==end[i][j]){num++;}}}return9-num;}〃空白节点移动算法intlocation=locatc(now,0);inti,j;i=location/3;j二location%3;copy_matrix(extend,now);if(i>0)//空格上移int*p二&extend[i][j];ini*q=&extend[i-1][j];exchange(p,q);if(judge())inopen(extend);}}copymatrix(extend,now);if(i<2)//空格下移{exchange(&d[i][j],&d[i+l][j]);if(judge()){inopen(extend);}}copy_matrix(extend,now);if(j>0)//空格左移{exchange(&extend[i][j],&extend[i][j-1]);if(judge()){inopen(extend);}}copy_matrix(extend,now);if(j<2)//空格右移{exchange(&extend[i][j],&extend[i][j+1]);if(judge()){inopen(extend);}}、 把起始节点放到OPEN表中(如果该起始节点为一目标节点,则求得一个解答);2、 如果OPE"是个空表,则没有解,失败退岀;否则继续;3、 把第一个节点(节点n)从OPEN表移出,并把它放入CLOSE的扩展节点表屮;4、 扩展节点n。如果没有后继节点,则转向上述第2步;5、 把n的所有后继节点放到OPEN表末端,并提供从这些后继节点回到n的指针;6、 如果n的任一个后继节点是个目标节点,则找到一个解答,成功退出;否则转向第(2)步。流程图:、 把起始节点放到OPEN表中,并计算启发式函数f(SO)(启发式函数f(SO)二初态与目标态不同的节点个数);2、 如果OPEN是个空表,则没有解,失败退出;否则继续;3、 把OPEN表中的第一个节点(启发式函数最小的节点n),移入CLOSED表;4、 如果n是目标节点,问题得