基于遗传算法的八数码问题的设计及实现.pdf

第20 期 计 算 机 技术 与发 展 VoI．20 No．3 2010年 3月 oOM 兀ERTECHNOU)GYANDDEVEU)l’M匮NT Mar． 2010 基于遗传算法的八数码问题的设计及实现 贺计文 ，宋承祥2，刘 弘 (1．山东师范大学信息科学与工程学院，山东济南 250014； 2．山东省教育厅，山东 济南 250011) 摘 要：Yr绍了遗传算法 (GA)在八数码问题中的应用。首先介绍了八数码问题及遗传算法的相关知识，分析了求解八数 码问题的传统解决方案；然后给出了八数码问题的遗传算法模型，并对此模型进行了算法的设计，即确定编码的表示、选 择算子、交叉算子、变异算子及适应度函数；最后把此算法运用到基于八数码问题的拼图游戏求解过程的动态演示上。文 中对此算法进行了多角度试验，试验表明采用遗传算法解决八数码问题是有效的、稳定的，具有较高的搜索效率。 关键词：／k数码问题；遗传算法；搜索算法 中图分类号：11)301．6 文献标识码 ：A 文章编号：1673—629X(2O10)o3—0105—04 DesignandImplementationofEightPuzzleProblem Based onGeneticAlgorithms HEji—wen ，SONGCheng-xiang2，LIU Hong (1．SchoolofInformationScienceandEngineering，Shandong NormalUniversity，Jinan250014，China； 2．EducationDepartmnetofShandong Province，Jinan250011，China) Abstract：Introducestheapplicationofgeneticalgorithmsintheeightpuzzleproblem．Firsdydepictedhteknowledgeabouttheeight E— zhproblem andthe GA，analyzedtheclassicalsolutions．ThenpresentedamodelbasedOnGAanddesignedthealgorithm basedonthe mode1．Lastlyimplme netde agamewhichcandemonstratetheprocessofmotiondynan~aclly．Thisalgorithm wastestde withseveralas· pects，itisprovde thatthe algoritmh isavailableandefficient，withthehighersearchefficinecy． Keywords：eightpuzzleproblme ；geneticalgorithms；searchalgorithms O 引 言 解，并分析和比较了三者所表现出来的性能。另一种 ． 八数码问题也称九官排定问题，是拼图游戏的基 方法是采用产生式系统来求解[2】，其中的控制策略同 础，是人工智能中的经典问题之一。该问题是在一个 样需要使用搜索算法。搜索算法的本质是把这些状态 3×3的方格上 ，放有数字 1～8，剩下一个格为空格，空 空间看作一颗四叉树，初始状态作为根节点，求解的过 格可以和其上下左右的数字交换；给定初始状态和目 程即为寻找一条从根节点到达 目标节点的路径的过 标状态，求能使初始状态转化为目标状态的一系列交 程，很显然，当目标节点的深度较深时，会