基于双向广度优先搜索的魔力方块问题求解.pdf

第37卷 第2O期 计 算 机 工 程 2011年 10月 V_01-37 No．20 ComputerEngineering 0ctober 20l1 · 人工智能及识别技术 · 文章编号：1oo 428(2011)2 219—4 文献标识码；A 中踞分类号；TP3016· 基于双向广度优先搜索的魔力方块问题求解 王桂平 ，张 帅 (1．重庆大学计算机学院，重庆 400030；2．浙江财经学院信息学院，杭州 310018) 摘 要 ：将魔力方块问题与八数码问题进行对比分析，通过讨论魔力方块问题是否有解、解的最少步数、状态表示、状态判重、状态转换 关系等相关问题，提出一种基于双向广度优先搜索和状态转换表的求解算法。实验结果表明，与有界深度优先搜索、简单广度优先搜索及 A搜索算法相比，该算法效率较高，稳定陛较好，可以实现魔力方块问题的实时求解及演示。 关健诃：魔力方块问题；状态判重；状态转换表 ；双向广度优先搜索；八数码问题 SolutionforM agicSquareProblem Based0nBidirecti0nalBreadth．firstSearch WANG Gui-ping ，ZHANG Shuai (1．CollegeofComputerScience，ChongqingUniversity，Chongqing400030，China； 2．SchoolofInformation，ZhejiangUniversityofFinancialandEconomy，Hangzhou310018，China) [Abstract]Thispaperintroducesmagicsquareproblem，andanalyzes8-puzzleproblemcompraatively．Itcomprehensivelydiscussessomeissues relevnattosolvingmagicsquareproblem，suchaswhetherthereisasolution，minimumsteps，staterepresentation，staterepetitionjudging，trnasition relationbetweenstatesofmagicsquareproblem ItproposesasolutionbasedonbidirectionalBreadht—firstSearch(BFS)andstatertansitiontable． Experimentalresultsprovehtatcomparedwiht ohteralgorihtms，htealgorithm proposedisefficientna dsatble，whichmeetshterequirementsof real—timesolvingnadpresentationofmagicsquraeproblem． [Keywords!magicsquareproblem；satteI℃petiti0njudging；statertansitiontable；bidirectionalBreadth—firstSearch(BFS)；8-puzzleproblem DOI：10．3969／j．issn．1000—3428．2011．20．076 1 概述 魔力方块问题可以采用简单的搜索算法(eU广度优先搜 八数码问题、迷宫问题、过河问题等是人工智能领域的 索和深度优先搜索)、启发式搜索算法(如A搜索算法)以及其 经典问题 ，广泛用于状态表示、盲 目搜索和启发式搜索算法 他智能算法(如遗传算法)进行求解。因此，魔力方块问题可 的研究。这些问题的求解一般都涉及状态表示、状态判重、