资源描述：
《631306050113程强+状态空间搜索+启发式搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、重庆交通大学计算机与信息学院验证性实验报告班级：计算机软件开发专业2013级1班学号：631306050113姓名：程强实验项目名称：状态空间搜索实验项目性质：验证性实验实验所属课程：人工智能实验室(中心)：软件中心实验室（语音楼8楼）指导教师：朱振国实验完成时间：2016年6月13日评阅意见：实验成绩：签名：年月日一、实验目的1.理解和掌握状态空间搜索的策略。二、实验内容及要求1．实验内容：在一个3*3的九宫中有1-8个数码及一个空格随即的摆放在其中的格子里，现在要求实验这个问题：将该九宫格调整为某种有序的形式。调整的规则是，每次只能将与空格（上、下、左、右）相
2、邻的一个数字平移到空格中。2．实验要求：用选定的编程语言编写程序，利用不同的搜索策略进行状态空间搜索（如宽度优先搜索、深度优先搜索、有界深度优先搜索等）三、实验设备及软件一台PC，Java四、设计方案㈠题目状态空间搜索㈡设计的主要思路状态空间法①建立一个只含有初始节点S0的搜索图G，把S0放入OPEN表中②建立CLOSED表，且置为空表③判断OPEN表是否为空表，若为空，则问题无解，退出④选择OPEN表中的第一个节点，把它从OPEN表移出，并放入CLOSED表将此节点记为节点n⑤考察节点n是否为目标节点，若是，则问题有解，成功退出。问题的解就是沿着n到S0的路径得
3、到。若不是转⑥①扩展节点n生成一组不是n的祖先的后继节点，并将它们记为集合M，将M中的这些节点作为n的后继节点加入图G中②对未在G中出现过的（OPEN和CLOSED表中未出现过的）集合M中的节点,设置一个指向父节点n的指针，并把这些节点放入OPEN表中；对于已在G中出现过的M中的节点，确定是否需要修改指向父节点的指针；对于已在G中出现过，并已在closed表中的M中的节点，确定是否需要修改通向他们后继节点的指针。③按某一任意方式或某种策略重排OPEN表中节点的顺序④转③宽度优先搜索算法
(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)
4、。
(2)如果OPEN是个空表，则没有解，失败退出；否则继续。(3)把第一个节点(节点n)从OPEN表移出，并把它放入CLOSED的扩展节点表中。(4)扩展节点n。如果没有后继节点，则转向上述第(2)步。(5)把n的所有后继节点放到OPEN表末端，并提供从这些后继节点回到n的指针。
(6)如果n的任一个后继节点是个目标节点，则找到一个解答，成功退出；
否则转向第(2)步。深度优先搜索算法
(1)把起始节点放到OPEN表中(如果该起始节点为一目标节点，则求得一个解答)(2)如果OPEN是个空表，则没有解，失败退出；否则继续。
(3)把第一个节点(节点n)从OPEN表
5、移出，并把它放入CLOSED的扩展节点表中。
(4)考察节点n是否为目标节点，若是，则找到问题的解，用回溯法求解路径，退出(5)如果没有后继节点，则转向上述第(2)步。
(6)扩展节点n，把n的所有后继节点放到OPEN表前端，并提供从这些后继节点回到n的指针。转向第(2)步。㈢主要功能通过一系列的数码移动，讲初始位置转化为目标位置五、主要代码packagecn.edu.nwsuaf.qhs.artificialintelligence.eightpuzzle;importjava.util.Arrays;publicclassEightPuzzleimplemen
6、tsCloneable{/*利用一个二维的数组来存储数据*/publicint[][]data;privateintblankPos_x,blankPos_y;privateintdepth;//无参构造函数publicEightPuzzle(){data=newint[3][3];}//传递一个数组，进行初始化的构造函数publicEightPuzzle(int[][]data){this.data=data;}//判断是不是和目标位置相同/*int[][]data1=newint[][]{{1,2,3},{4,5,6},{7,8,9}};int[][]data
7、2=newint[][]{{1,2,3},{4,5,6},{7,8,9}};System.out.println("Equals--->"+Arrays.equals(data1,data2));falseSystem.out.println("deepEquals--->"+Arrays.deepEquals(data1,data2));true*/publicbooleanisEquals(EightPuzzleep){returnArrays.deepEquals(this.data,ep.data);}publicStringtoString(){Stri
8、ngBuf
