论文-八数码问题

《论文-八数码问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、人工智能课程设计题目:用A*算法解决8数码问题学院:信息科学与技术学院专业:计算机科学与技术2005年12月摘要本课题以人工智能两人支柱之一的搜索技术中的启发式搜索策略（即通过对向最终结果的逼近作评估来发现问题的解）为出发点，结合人工智能应用及其最新进展，阐述了人工智能搜索原理、启发式搜索算法和启发式断数等内容。本文讨论了各种状态空间搜索策略、启发式推理技术，并冃以八数码问题为例着重讨论了各种启发式函数及其特点，分析它们在问题求解时所起的作用。关键词:人工智能，搜索策略，启发式函数1・概述1.1八数码问题1.2A*算法A*算法的一般描述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.结束语参考文献附件一附件二1.概述1.1八数码问题8数码问题是指在3X3的九宫棋盘上有标号为I〜8的8个棋牌，和一个空白位，通过棋牌向空口位移动来改变棋盘布局，如何移动棋牌才能从初使布局到达H标布局.显然解答路径实际上就是一个合法的走步序列1.2A*算法A*算法属于一种启发式搜索，它扩展结点的次序类似于广度优先搜索，但不同的是每生

3、成一个子结点需要计算估价函数F,以估算起始结点的约朿经过该结点至达日标结点的最佳路径代价;每当扩展结点时，意是在所有待扩展结点屮选择具有最小F值的结点做为扩展对象，以便使搜索尽量沿最有希望的方向进行.A*算法只耍求产生问题的全部状态空间的部分结点及关系，就可以求解问题了，搜索效率较高。A*算法的一般描述1.3.1约定S：指示初使状态节点(Note)；G：指示搜索图OPEN：作为存放待扩展节点的表；SNS：子节点集合CLOSE：作为存放已被扩展节点的表Move_First(Open)：指示取Open表首节点作为当前要被扩展的节点n,同时将节

4、点n移到CLOSE表；F(n)=G(n)+H(n)：评价函数，用于排列节点在OPEN表中的位置1.3.2算法过程(t)G:=S;©OPEN:=(S),CLOSE:=();③如果OPEN为空则算法失败③n:=Move_First(OPEN);(5)如果n是目标结点，搜索完成。◎扩展节点m将非节点n祖先的子节点置于子点子集合SNS屮，并插入G,对SNS每个了节点计算F(n,ni)=G(n,ni)+H(ni)⑦标记与修改指针：1.把SNS中的子结点分为三类:全新结点，已出现于OPEN表的结点，已出现于CLOSE表的节点;2.加第一类子节点于OP

5、EN表;3•由评价函数值，选择最优结点,并移动子结点指向父节点的指针，改为指向新父节点(8)重新排序OPEN表中结点；⑨返1111语句③2.A*算法在VC6.0开发环境下的实现2.1.类（可参见附件）2.1.lCDisplay类由于结果以各种棋盘的布局来表示空白位的移动，因此建立这个类的hl的是记录棋盘布局，并指出这个布局是否已经存在，是否正解，是否己扩展（已扩展并不表示是正解，正解一定表示已扩展）•同时这个类的对象也是搜索树的节点2.1.2CMain类这个类负责A*算法的全部过程，如:初值与结果的取得，空白位的移动,评价函数值的计算，选

6、择当前最优移动方法，生成下一个棋盘布局,形成搜索树等2.1.3其它类1.CAI3Doc类：VC6.0AppWizard自动生成，在本程式中负责将CMain类对象的运算结果（搜索树）转换成可显示格式2.CAI3View类:VC6.0AppWizard口动生成，在本程序中负责将CAI3Doc类转换好的内容显示。3.CMainFrame类:VC6.0AppWizard自动生成，在本程序中负责界常处理（搜索出错，运算成功等）4.CAI3App类：VC6.0AppWizard自动生成,本程序中无特殊使用5.CPtrList类：在本程式中预定义为Li

7、st,它的对象用于树（搜索树，结果显示树）的存储6.CPoint类:在木程式中预肚义为Position,它的对象用于表示坐标2.2数据结构：在本程序屮，棋盘布局以一个3X3的二元数组表示；CDisplay类的对象作为搜索树的节点，搜索树以链表形式存储（可参见附件）程序流程图与相关说明：2.2.1生成搜索树注一:Opl=Op2表示将Op2的内容全部复制到Opl中，注二：标志为解状态的原因是为了找到解图；标志为某状态为解状态的同时也标记此状态为已扩展注三：取得空白位的位置在0p2初使化时就已完成。注四：由于G值对于子结点是相同的，因此只要比较

8、H值就相当于比较了F值3・主要程序代码及注释要想得到最优的就需要使用广度优先搜索，九宫的所以排列有9!种，也就是362880种排法，数据量是非常大的，我使用的广度搜索，需要记住每一个结点的排列