摘要: 将魔力方块问题与八数码问题进行对比分析,通过讨论魔力方块问题是否有解、解的最少步数、状态表示、状态判重、状态转换关系等相关问题,提出一种基于双向广度优先搜索和状态转换表的求解算法。实验结果表明,与有界深度优先搜索、简单广度优先搜索及A*搜索算法相比,该算法效率较高,稳定性较好,可以实现魔力方块问题的实时求解及演示。
关键词:
魔力方块问题,
状态判重,
状态转换表,
双向广度优先搜索,
八数码问题
Abstract: 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.
Key words:
magic square problem,
state repetition judging,
state transition table,
bidirectional Breadth-first Search(BFS),
8-puzzle problem
中图分类号:
王桂平, 张帅. 基于双向广度优先搜索的魔力方块问题求解[J]. 计算机工程, 2011, 37(20): 219-222.
WANG Gui-Beng, ZHANG Shuai. Solution for Magic Square Problem Based on Bidirectional Breadth-first Search[J]. Computer Engineering, 2011, 37(20): 219-222.