基于多线程技术的分辨函数析取范式生成算法

摘要

基于分辨矩阵计算信息系统的所有约简,都需要将合取范式转化为析取范式,但是该转化过程存在组合爆炸问题.为解决该问题,根据合取范式、合取运算和析取运算的特点,构建析取范式转化的并行模型,提出基于多线程技术的分辨函数析取范式生成算法,利用Windows的自动线程调度功能提高范式转换的效率.实验结果表明,该算法的析取范式转化效率会随着合取范式长度的增加而提高,适合在多核CPU计算机上运行.%It is required to translate conjunction normal form into disjunction normal form when using discernibility matrix to compute all reducts of an information system. But there exists the combination explosion problem in this transformation process. Following the properties of conjunction normal form, And operator and OR operator, this paper constructs a parallel model for the transformation process, and then proposes a multi-thread technology-based algorithm for generating disjunction normal forms. The proposed algorithm improves the efficiency of transformation by using the functions of automatic thread scheduling of Windows. Experimental results show that the algorithm seems more efficient in the cases where conjunction normal forms have relatively large length, making good use of multi-core CPU resources of computers.