分布式状态空间生成的设计与实现

状态空间生成的并行化是针对状态空间爆炸问题而提出的一种重要手段。提出了一种基于MapReduce的分布式状态空间生成方案，与现有的同类研究相比，它无需用户关心生成算法的并行化，具有简单易用性；与常规的MapReduce的用法相比，它增加了输入文件的自动生成和作业运行的自动循环控制。该方案已在小规模分布式环境下实现，实验结果表明：（1）基于Map-Reduce的分布式状态空间生成算法可以扩大模型的可求解规模；（2）对于状态空间规模的增长主要由托肯（token）数增加引起的一类模型，该算法具有良好的适应性和可扩展性。

Design and implementation of distributed state space generation

Parallelization of state space generation is an important technical method to deal with the state space explosion prob-lem.A practical approach based on MapReduce framework is presented.h has the virtues of simpleness and easiness to use,which let the user need not caring about how to parallelize the state space generation algorithm,and that is where it differs from the existing distributed state space generation algorithms.Meanwhile,the manner that the MapReduce framework is used in this ap-proach is also different from the common ones:h has the abilities of dynamically generating input files and repeatedly executing the state space generation process in need, while the common use of MapReduee is to one-off process vast amounts of data in-parallel.This approach has been implemented in a small-scale distributed environment and the experimental results show that: (1)distributed state space generation based on MapReduee does have the ability to analyze a model with large state space,and that (2)this method is quite applicable and sealable for a model with an increasing token number and a fixed place number, whose state space scales up mainly with the token number.