分布式并行宽度优先搜索与15-迷问题的完全解

摘要

宽度优先搜索(Breadth-First Search,BFS)是一种基本的最佳优先搜索算法(Best-First Search).它在模型检查、模式数据库计算以及确定问题状态空间半径等领域中有着重要的应用.宽度优先搜索作为一种系统的图搜索算法,它通常比深度优先搜索(Depth-First Search,DFS)有效得多,后者无法探测出表示同一状态的重复节点并且需要在产生所有路径后才能确定出最优解.但是,宽度优先搜索的适用规模因其空间需求大的特点受到极大限制.近来,利用磁盘作为二级缓存来克服BFS内存限制的相关技术被提出.然而,单台计算机的存储能力总是有限的.因此引入分布式并行宽度优先搜索,结合多台机器的计算能力和存储资源来完成大规模的宽度优先搜索.最后,以15-迷(15-Puzzle)问题为平台,计算其完全解(状态空间规模超过1013).