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

Solution for Magic Square Problem Based on Bidirectional Breadth-first Search

作　　者：王桂平[1] 张帅[2] 

机构地区：[1]重庆大学计算机学院,重庆400030 [2]浙江财经学院信息学院,杭州310018

出　　处：《计算机工程》2011年第20期219-222,共4页Computer Engineering

基　　金：国家自然科学基金资助项目(50975250);浙江省自然科学基金资助项目(Y1110671)

摘　　要：将魔力方块问题与八数码问题进行对比分析,通过讨论魔力方块问题是否有解、解的最少步数、状态表示、状态判重、状态转换关系等相关问题,提出一种基于双向广度优先搜索和状态转换表的求解算法。实验结果表明,与有界深度优先搜索、简单广度优先搜索及A*搜索算法相比,该算法效率较高,稳定性较好,可以实现魔力方块问题的实时求解及演示。This paper introduces magic square problem,and analyzes 8-puzzle problem comparatively.It comprehensively discusses some issues relevant to solving magic square problem,such as whether there is a solution,minimum steps,state representation,state repetition judging,transition relation between states of magic square problem.It proposes a solution based on bidirectional Breadth-first Search（BFS） and state transition table.Experimental results prove that compared with other algorithms,the algorithm proposed is efficient and stable,which meets the requirements of real-time solving and presentation of magic square problem.

关 键 词：魔力方块问题 状态判重 状态转换表 双向广度优先搜索 八数码问题 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]