昆明理工大学 八数码实验报告.doc

《昆明理工大学 八数码实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、昆明理工大学信息工程与自动化学院学生实验报告（2014—2015学年第1学期）课程名称：人工智能及其应用开课实验室：信自楼5042014年11月26日年级、专业、班计科122班学号201210405204姓名邹华宇成绩实验项目名称八数码问题指导教师吴霖教师评语该同学是否了解实验原理：A.了解□B.基本了解□C.不了解□该同学的实验能力：A.强□B.中等□C.差□该同学的实验是否达到要求：A.达到□B.基本达到□C.未达到□实验报告是否规范：A.规范□B.基本规范□C.不规范□实验过程是否详细记录：A.详细□B.一般□C.没有

2、□教师签名：年月日一、上机目的及内容1.上机内容：求解八数码问题。问题描述：八数码难题，问题描述：在3×3方格棋盘上，分别放置了标有数字1,2,3,4,5,6,7,8的八张牌，初始状态S0，目标状态S1如图所示，可以使用的操作有：空格上移，空格左移，空格右移，空格下移。只允许位于空格左，上，右，下方的牌移入空格。用广度优先搜索策略寻找从初始状态到目标状态的解路径。2.上机目的:（1）复习程序设计和数据结构课程的相关知识；（2）熟悉人工智能系统中的问题求解过程；（3）熟悉对八码数问题的建模、求解及编程语言的运用。二、实验原理及

3、基本技术路线图（方框原理图或程序流程图）-22-（1）建立一个只含有起始节点S的搜索图G，把S放到一个叫做OPEN的未扩展节点的表中；（2）建立一个叫做CLOSED的已扩展节点表，其初始为空表；（3）LOOP:若OPEN表是空表，则失败退出；（4）选择OPEN表上的第一个节点，把它从OPEN表移除并放进CLOSED表中，称此节点为节点n；（5）若n为一目标节点，则有解并成功退出，此解是追踪图G中沿着指针从n到S这条路径而得到的；（6）扩展节点n，同时生成不是n的祖先的那些后继节点的集合M。把M的这些成员作为n的后继节点舔到图

4、中；（7）对那些未曾在G中出现过的M成员设置一个通向n的指针。把M的这些成员加进OPEN表。对已经在OPEN表或CLOSED表上的成员，确定是否需要更改通到n的指针方向；（8）按某一任意方式或按某个探视值，重排OPEN表。-22-开始把S放入OPEN表OPEN表为空把第一个节点（n）从OPEN移至CLOSED表n为目标节点成功失败把n的后继节点n放入OPEN表的末端，提供返回节点的指针修改指针方向重排OPEN表宽度优先算法实现过程（1）把起始节点放到OPEN表中；（2）如果OPEN是个空表，则没有解，失败退出；否则继续；（3

5、）把第一个节点从OPEN表中移除，并把它放入CLOSED的扩展节点表中；（4）扩展节点n。如果没有后继节点，则转向（2）；（5）把n的所有后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；（6）如果n的任意一个后继结点是目标节点，则找到一个解答，成功退出，否则转（2）。-22-开始把S放入OPEN表OPEN表为空失败把第一个节点n从把S放入OPEN表移除，放到CLOSED表中移除扩展n，把它的后继节点放入OPEN表的末端，提供回到n的指针是否任何节点为目标节点成功深度优先实现过程（1）把起始节点S放入未扩展节点O

6、PEN表中。如果此节点为一目标节点，则得一个解；（2）如果OPEN为一空表，则失败退出；（3）把第一个节点从OPEN表移到CLOSED表；（4）如果节点n的深度等于最大深度，则转向（2）；（5）扩展节点n，产生其全部后裔，并把它们放入OPEN表的前头。如果没有后裔，则转向（2）；（6）如果后继结点中有任一个目标节点，则得到一个解，成功退出，否则转向（2）。-22-开始把S放入OPEN表S是否为目标节点成功把第一个节点n从把S放入OPEN表移除，放到CLOSED表中移除节点n深度是否等于最深界限OPEN表为空失败扩展n，把它的

7、后继放入OPEN表的前头，提供回到n的指针是否有任何后继节点为目标节点成功三、所用仪器、材料（设备名称、型号、规格等或使用软件）1台PC及VISUALC++6.0软件四、实验方法、步骤（或：程序代码或操作过程）1、先创建项目，新建SourceFile文件：main.cpp。#include#include"Node.h"#include"Queue.h"#include"Search.h"#include"Tree.h"voidCreateNode1(std::vector&s)-22-{s.p

8、ush_back(2);s.push_back(8);s.push_back(3);s.push_back(1);s.push_back(0);s.push_back(4);s.push_back(7);s.push_back(6);s.push_back(5);}voidCreateNo