用VC++实现基于A算法的八数码问题

《用VC++实现基于A算法的八数码问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、Vol.16No.9Sep.2006计算机技术与发展(I)卜MUTERTECHNOLOGYAXI)I^EVEIDPMFNT用VC++实现基于A*算法的八数码问题朱永红，张燕平(安徽大学计算智能与信号处理教育部重点实验室，安緻合肥230039)摘要:在人工智能领域中，八数码问题一直都是一个游戏难题。介绍了八数码问题,然后在启发式搜索算法上对A*算法定义进行了解释，并在其旨在提高搜索效率的方面作了比较详尽的介绍，详细描述了基于图搜索算法的解决此类问题的一种启发式搜索算法一A*算法。再依据这种算法用可视化编程语言

2、VC++6.0来实现八数码问题的求解过程•取得了预期的搜索解，提高了搜索效率。关键词:八数码问题;启发式搜索;A*算法中图分类号:TP18文献标识码:A文章编号：1673-629X(2006)09-0032-03ProgrammingforEight一FigurePuzzleProblemBasedonAlgorithmA*withVisualC++ZHUYong-hong,ZHANGYan-ping(MinistryofEducationKeyLab.ofIntelligenceComputingandS

3、ignalProcessing,AnhuiUniversity»Hefei230039•China)Abstract:EightFigurePuzzleproblemisalwaysagamepuzzleinartificialintelligence・ThispaperintroducestheEight一FigurePuzzleproblem.ThenitexplainsthedefinitionofalgorithmA*andmakesitclearhowtoimprovetheefficiencyo

4、fsearchanddescribethealgo・rithmA*whichisoneofheuristicsearchbasedongraplisearch・AccordingtothisalgorithmdisplaytheprocessofexpbringtheEight一FigurePuzzleproblembyVC++6・0.whichresultsinthebestsolutionandimprovestheefficiencyofsearch.Keywords：Eight-FigurePuzz

5、leproblem;heuristicsearch;algorithmA*八数码问題的一个实例0引言八数码问题是人工智能的一个经典的问题。文中通过设计一个基于A好算法的状态空间搜索程序，对于给定的初始状态，采用h(n)=/>0)表示以每一个将牌与目标位置之间距离的总和作为启发函数的度量，并用可视化编程语言VC++来实现该问题。1问题描述八数码问题⑴就是在一个3x3的九宫格棋盘上，摆有8个将牌，每一个将牌都刻有1〜8中的某一个数码。棋盘中留有一个空格，允许其周围的某一个将牌向空格移动,这样通过移动将牌就可以不

6、断改变将牌的布局。这种求解的问题是:给定一种初始的将牌布局或结构(称初始状态)和一个目标布局(称目标状态)，问如何移动数码,收稿日期：2006-01-03基金项目：国家自然科学茶金资助项忖(60475017);教仔部M士点堆金资助顶目(20040357002)作者简介:朱永红(19X1-)，男，安徹旌徳人，硕:t研究生，研究方向为种能计算;张燕平，教授•硕I:研究牛•导帅，研究领域为人工神经网络、机器学习、人匸智能屁金融工程中的应用。实现从初始状态到目标状态的转变•如图1所示⑵。问题的实质就是寻找一个合法

7、的动作序列。2A*算法启发式搜索24是利用问题拥有启发信息引导搜索,以达到减小搜索范围、降低问题复杂度的目的。在启发式搜索过程中，要对Open表进行排序，这就要有一种方法来计箕待扩展结点有希望通向目标结点的不同程度，人们总是希望能找到最有可能通向目标结点的待扩展结点优先扩展。一种最常用的方法是定义一个评价函数对各个结点进行计算，其目的就是用来估算出“有希望”的结点。用/来标记评价函数，用/(")表示结点”的评价函数值,并用f来排列等待扩展的结点,然后选择具有最小./值的结点作为下一个要扩展的结点。A*算法心

8、⑸是一种冇序搜索算法，其特点在于对评价函数的定义上。这个评价函数/使得在任意结点匕找甬数值/(”)能估算出从结点S到结点”的最小代价路径的代价与从结点“到某一目标结点的城小代价路径的代价的总和，也就是说f(n)是约束通过结点n的一条最小代价路径的代价的一个估计。再定义一个函数/»,使得在任意一个结点“上的函数值/*(^)就是从结点S到结点n的一条最佳路径的实际代价加上从结点"到目标结点的一条最佳路径的代价之和，即