搜索
武汉理工大学学生实验报告书实验课程名称人工智能概论B实验名称八数码问题开课学院计算机科学与技术学院指导老师姓名学生姓名学号学生专业班级2016—2017学年第一学期一、实验要求及问题描述采取分组形式，2人一组，一人使用盲目搜索中的宽度优先搜索算法，另一人使用启发式搜索中的全局择优搜索或A*算法。每组提交一份大作业报告，该报告包括设计、实现、测试、实验对比结果分析、结论、个人体会与总结。提交截止时间：2016.11.18对任意的八数码问题，给出求解结果。例如：对于如下具体八数码问题：13212345⇨84678765通过设计启发函数，编程实现求解过程，如果问题有解，给出数码移动过程，否则，报告问题无解。250123873804641765二、实验原理2.1状态空间表示1、建立只有初始节点S0的搜索图，并将S0放入OPEN表中；2、建立CLOSE表并置空；3、对OPEN表进行判断，若OPEN表为空，则无解；4、将OPEN表中的第一个节点移出，放入CLOSE表中，记为节点n；5、判断节点n是否为目标节点。是，则有解，解为沿n到S0的路径，否，则进行步骤6；6、由节点n生成一组不是n的祖先的后继节点，记为集合P，将P中节点作为n的后继加入搜索图；7、对于在OPEN表和CLOSE表中没有出现过的集合P中的节点，设置指向节点n的指针，把这些节点放入OPEN表中；对于在OPEN表和CLOSE表中已经出现过的P中的节点，确定是否修改指向父节点的指针；8、重拍OPEN表节点顺序；9、转到步骤3。2.2数据结构设计//宽度优先搜索中，八数码地图节点结构体structEightDigit{intCube[3][3];DirectionLastDirection;structEightDigit*Parent;};//全局择优搜索中，八数码节点结构体structnode{intindex;//结点序号intp_index;//父结点序号intmatrix[3][3];//八数码状态inth_function;//启发式函数值};nodeopen[SIZE];//存放已经生成的未考察的节点nodeclosed[SIZE];//存放已经考察过得节点2.3启发式函数与相关算法//计算节点启发式函数值intarouse(inta[][3]){intnum=0;inti,j;for(i=0;i3;i++){for(j=0;j3;j++){if(a[i][j]==end[i][j]){num++;}}}return9-num;}//空白节点移动算法intlocation=locate(now,0);inti,j;i=location/3;j=location%3;copy_matrix(extend,now);if(i0)//空格上移{int*p=&extend[i][j];int*q=&extend[i-1][j];exchange(p,q);if(judge()){inopen(extend);}}copy_matrix(extend,now);if(i2)//空格下移{exchange(&extend[i][j],&extend[i+1][j]);if(judge()){inopen(extend);}}copy_matrix(extend,now);if(j0)//空格左移{exchange(&extend[i][j],&extend[i][j-1]);if(judge()){inopen(extend);}}copy_matrix(extend,now);if(j2)//空格右移{exchange(&extend[i][j],&extend[i][j+1]);if(judge()){inopen(extend);}}2.3广度优先搜索算法1、把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)；2、如果OPEN是个空表，则没有解，失败退出；否则继续；3、把第一个节点(节点n)从OPEN表移出，并把它放入CLOSE的扩展节点表中；4、扩展节点n。如果没有后继节点，则转向上述第2步；5、把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针；6、如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；否则转向第(2)步。流程图：广度优先搜索算法框图2.4全局择优搜索算法1、把起始节点放到OPEN表中，并计算启发式函数f(S0)（启发式函数f(S0)=初态与目标态不同的节点个数）；2、如果OPEN是个空表，则没有解，失败退出；否则继续；3、把OPEN表中的第一个节点（启发式函数最小的节点n），移入CLOSED表；4、如果n是目标节点，问题得解，退出。否则继续；5、判断节点n是否可扩展。若否则转向第(2)步，若是则转向(6)；6、对节点n进行扩展，并对其所有后继节点计算启发式函数f（n）的值，并为每个后继节点设置指向n节点的指针。把这些后继节点都送入OPEN表，然后对OPEN表中的全部节点按照估价函数值从小到大的顺序排序；7、转向第2步。流程图：全局择优搜索算法框图三、实验结果截图（共五组，每组均为宽度优先搜索和全局择优搜索，采用相同初始节点和目标节点）四、实验结果分析开始时在两种算法中设置时间函数，希望通过在同一台PC机上采用两种算法对同一组八数码问题进行求解，来比较两种算法的优劣，但是实际实验过程中发现了两种算法在总步数较少的情况下，以ms为单位的情况下，两者运行时间均很短，难以比较。通过比较两种算法总步数和生成状态总数可以发现，启发式搜索（全局择优搜索）还是效率上优于盲目搜索算法（广度优先搜索），好的启发式函数是设计可以帮助在搜索过程中大大减少搜索步数和算法时间。启发式搜索通过逐步对目标状态的逼近，在几步之内就能比起穷举每一种状态广度优先搜索在空间和时间上节省很多。五、个人体会与总结人工智能概论这门课程，是研究、开发用于模拟、延伸和拓展人的智能的理论、方法、技术及应用系统的一门新的科学。本次试验是搜索策略问题中比较著名的八数码问题。通过这次实验，首先对课本上各种搜索策略有了更深的了解，通过算法分析与设计，理解了各种搜索算法的思想，比起平时做作业时直接套入算法的过程，实验的过程更考验我们对于算法的理解，只有真正理解了各种搜索策略，才能在用相应高级语言实现八数码问题的过程中比较顺利。实验编码的过程是枯燥的，但是其不可否认的锻炼了我们的编程能力，让我们对于C语言的应用又更加熟练了。通过对于实验结果的分析，可以直观的发现盲目搜索和启发式搜索的在时间和空间的差别，启发式搜索明显优于盲目搜索，设置更加巧妙的启发式函数则会帮助问题的效率进一步提高。实验中只是对八数码问题做出了求解，采用两种策略，其实还可以在八数码问题的基础上进一步拓展到N数码的问题。我们可以在课下进一步思考其求解策略。这次实验给我带来的收货颇丰，希望以后还能有这种实验，将课堂上所学的相应算法投入到实际问题求解当中，很有趣，受益良多。