资源描述：
《人工智能课程设计--八数码问题》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、人工智能课程设计题目:用A*算法解决8数码问题学院:信息科学与技术学院专业:计算机科学与技术2005年12月摘要本课题以人工智能两大支柱之一的搜索技术中的启发式搜索策略（即通过对向最终结果的逼近作评估来发现问题的解）为出发点，结合人工智能应用及其最新进展，阐述了人工智能搜索原理、启发式搜索算法和启发式函数等内容。本文讨论了各种状态空间搜索策略、启发式推理技术，并且以八数码问题为例着重讨论了各种启发式函数及其特点，分析它们在问题求解时所起的作用。关键词：人工智能，搜索策略，启发式函数15目录1.概述1.1八数码问题1.2A*算法1.3A*算法的一般描述1
2、.3.1约定1.3.2算法过程2.A*算法在VC6.0开发环境下的实现2.1类2.1.1CDisplay类2.1.2CMain类2.1.3其它类2.2数据结构2.2.1生成搜索树3．主要程序代码及注释4．其它5.结束语参考文献附件一附件二151.概述1.1八数码问题8数码问题是指在3X3的九宫棋盘上有标号为1～8的8个棋牌,和一个空白位,通过棋牌向空白位移动来改变棋盘布局,如何移动棋牌才能从初使布局到达目标布局.显然解答路径实际上就是一个合法的走步序列1.2A*算法A*算法属于一种启发式搜索,它扩展结点的次序类似于广度优先搜索,但不同的是每生成一个子结
3、点需要计算估价函数F,以估算起始结点的约束经过该结点至达目标结点的最佳路径代价;每当扩展结点时,意是在所有待扩展结点中选择具有最小F值的结点做为扩展对象,以便使搜索尽量沿最有希望的方向进行.A*算法只要求产生问题的全部状态空间的部分结点及关系,就可以求解问题了,搜索效率较高。1.3A*算法的一般描述1.3.1约定S：指示初使状态节点（Note）；G：指示搜索图OPEN：作为存放待扩展节点的表；SNS：子节点集合CLOSE：作为存放已被扩展节点的表Move_First(Open)：指示取Open表首节点作为当前要被扩展的节点n，同时将节点n移到CLOSE
4、表；F(n)=G(n)+H(n)：评价函数，用于排列节点在OPEN表中的位置1.3.2算法过程G:=S;OPEN:=(S),CLOSE:=();如果OPEN为空则算法失败n:=Move_First(OPEN);如果n是目标结点，搜索完成。扩展节点n，将非节点n祖先的子节点置于子点子集合SNS中，并插入G，对SNS每个子节点计算F(n,ni)=G(n,ni)+H(ni)标记与修改指针：1.把SNS中的子结点分为三类:全新结点,已出现于OPEN表的结点,已出现于CLOSE表的节点;2.加第一类子节点于OPEN表;3.由评价函数值,选择最优结点,并移动子结点
5、指向父节点的指针,改为指向新父节点重新排序OPEN表中结点；返回语句152.A*算法在VC6.0开发环境下的实现2．1.类（可参见附件）2.1.1CDisplay类由于结果以各种棋盘的布局来表示空白位的移动,因此建立这个类的目的是记录棋盘布局,并指出这个布局是否已经存在,是否正解,是否已扩展(已扩展并不表示是正解,正解一定表示已扩展).同时这个类的对象也是搜索树的节点2.1.2CMain类这个类负责A*算法的全部过程,如:初值与结果的取得,空白位的移动,评价函数值的计算,选择当前最优移动方法,生成下一个棋盘布局,形成搜索树等2.1.3其它类1.CAI3
6、Doc类：VC6.0AppWizard自动生成，在本程式中负责将CMain类对象的运算结果(搜索树)转换成可显示格式2.CAI3View类:VC6.0AppWizard自动生成,在本程序中负责将CAI3Doc类转换好的内容显示。3.CMainFrame类:VC6.0AppWizard自动生成,在本程序中负责异常处理（搜索出错，运算成功等）4.CAI3App类：VC6.0AppWizard自动生成,本程序中无特殊使用5.CPtrList类：在本程式中预定义为List,它的对象用于树（搜索树，结果显示树）的存储6.CPoint类：在本程式中预定义为Posi
7、tion,它的对象用于表示坐标2.2数据结构：在本程序中,棋盘布局以一个3X3的二元数组表示；CDisplay类的对象作为搜索树的节点，搜索树以链表形式存储（可参见附件）程序流程图与相关说明：2.2.1生成搜索树15当前操作状态＝初状态（注一）当前操作状态加入搜索树中并标记为解状态（注二）当前状态和结果状态相同提交成功结束处理取得空白位位置（注三）从空白位的位置确定空白位的可移动方向根据移动方向产生当前状态的子状态集开始运算初状态与结果状态已确认应用程序框架建立查询子状态集，如果某一子状态已经存在，则为其标志为已存在子状态集中各个子状态是否全部标记为已
8、存在计算没有标记为已存在的子状态的H值（注四）选择H值最小的子状态，标记为解状态。同时当前操作
