昆明理工大学人工智能实验报告

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

1、昆明理工大学信息工程与自动化学院学生实验报告（2015——2016学年第一学期）课程名称：人工智能导论开课实验室：信自楼432室2015年10月26日年级、专业、班学号姓名成绩实验项口名称状态空间搜索实验一八数码问题求解指导教师胡蓉教师评语该同学是否了解实验原理：A.了解口B.基本了解口C.不了解口该同学的实验能力：A.强口氏中等口C.差口该同学的实验是否达到耍求:A.达到口B.基本达到口C.未达到口实验报告是否规范：A.规范口B.基本规范口C.不规范口实验过程是否详细记录：A.详细口•般口C.没有口教师签名：年月日目录一、实验问题2二、实验目的2三、实验原

2、理2四、程序框图3五、实验结果及分析41、随机检验42、该问题广度优先搜索算法的搜索树；53^该问题白勺Open表和Closed表：6六、结论7七、源程序及注释7一、实验问题八数码问题的求解，及程序设计。具体要求如下m30b目标状态在3*3的方格屮的棋盘屮任意摆放1到8个自然数和一个空格，其初始状态如下：2a00a初始状态请选择一种盲口搜索的算法或选择一•种启发式搜索的算法编程求解八数码问题，初始状态任选，并对使用进行合理分析做出合理结果。二、实验目的1、熟悉人工智能系统中的问题求解过程；2、熟悉状态空间的满口搜索和启发式搜索算法的运用；3、熟悉对八码数问题

3、的建模、求解及编程语言的运用；三、实验原理经过分析，8数码问题中可采用的搜速策略共冇：1•广度优先搜索2.深度优先搜索2.有界深度优先搜索4、最好优先搜索5、局部择优搜索一共五种。其中，广度优先搜索法是可采纳的，冇界深度优先搜索法是不完备的，最好优先和局部择优搜索法是启发式搜索法。在实验时，我采用了广度优先算法广度优先算法搜索原理：广度优先搜索就是始终先在同一级节点屮考杏，只有当同一级节点考察完之后，才考杏下一级的节点。(1)把起始节点放到OPEN表中：(2)如果OPEN是个空表，则没有解，失败退出；否则继续；(3)把笫一个节点从OPEN表屮移除，并把它放入

4、CLOSED的扩展节点表中；(4)扩展节点n。如果没有后继节点，则转向(2)；(5)把n的所冇后继结点放到OPEN表末端，并提供从这些后继结点回到n的指针；(6)如果n的任意一个后继结点是口标节点，则找到一个解答，成功退出，否则转(2)四、程序框图失败五.实验结果及分析1、随机检验初始状态为：□H3的运行结果为:运行结果如图所示;目标状态为：3FJLzJJj2＞该问题广度优先搜索算法的搜索树;S解路径：S>MSg3＞该问题的Open表和Closed表:OPENCLOSEDSoABCDSoBCDEFSoACDEFGHSoABDEFGHIJSoABCEFGHIJ

5、KLSoABCDFGHIJKLMSoABCDEGHIJKLMNSoABCDEFHIJKLMN0SoABCDEFGIJKLMN0PSoABCDEFGHJKLMN0PQSoABCDEFGHTKLMN0PQRSoABCDEFGHlJLMN0PQRSSoABCDEFGHIJKMNOPQRSTSoABCDEFGIIIJKLNOPQRSTSgSoABCDEFGHIJKLM六、结论通过实验问题的求解过程就是搜索的过程，让我明白了采用适合的搜索算法是关键的，因为一个合适的算法对求解过程的效率冇很大的影响，包括各种规则、过程和算法等推理技术。八数码问题中，将牌的移动來描述规则

6、，是一种相对较简单的方法。虽然我使用的广度优先算法实现八数码问题，但是我不得不说广度优先算法其实是一种比较费劲的方式；然而深度优先将是一个相对好的方法，利用深度优先不但减少了程序实现的时间，是一种不错的方式。但最好的方式是启发式搜索方式实现，在很大程度上相对于前两种方式是一种非常好的实现方式，不但节省了时间，也节省了空间。这次试验使我对搜索算法有了一定的了解，并对实现这个问题的执行过程冇了更一步的认识。也通过它解决了八数码问题，但在实际的过程中还存在很多问题，也看了一些辅助书籍，以后还要加强学习，加强理论与实际的练习。总之，这次试验让我受益匪浅。七、源程序及

7、注释〃八数码问题——广度优先#includestructSnode{intparent;〃指向该结点父节点的编号intmap[9];public:voidTransformln(constint*d);voidTransformOut(int*d);}；voidSnode::TransformIn(constint*d){for(inti=0;iv9;++i)map[i]=d[i];}#defineMAX_OPEN_LEN50000#defineMAX_CLOSE_LEN5000()SnodeOPEN[MAX_OPEN_LEN];in

8、top=0;SnodeCLOSE[MAX_CLOSE