极小碰集求解中候选解极小性判定方法

来源：软件学报杂志2018年第12期北京时间：

作者：刘思光,欧阳丹彤,张立明

单位：刘思光，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001211,欧阳丹彤，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001202,张立明，吉林大学 计算机科学与技术学院, 吉林 长春 130012;符号计算与知识工程教育部重点实验室(吉林大学), 吉林 长春 13001203

摘要：极小碰集问题是人工智能中的重要问题，应用广泛.碰集极小性判定，作为极小碰集求解过程中的关键步骤，效率的高低会对极小碰集求解算法的耗时产生直接影响.现有的极小碰集求解算法主要使用子集检测方法进行碰集极小性判定.针对子集检测方法在极小碰集簇规模较大时效率较低的问题，提出了基于元素独立覆盖度检测的碰集极小性判定方法——ICC方法，剥离了碰集极小性判定耗时与极小碰集簇大小的相关性；通过深入分析增量求解过程中非极小碰集的产生原因，给出了ICC方法的增量判定形式ⅡCC方法，使其可以尽早发现并丢弃非极小候选解，为使用其增量极小碰集求解算法带来额外的剪枝效果，进一步提升算法的效率.实验结果表明：该方法易于实现，可扩展性强，对于当前效率较高的Boolean算法，使用ⅡCC方法后，算法可求解问题的规模和整体效率均有明显提升，效率提升最高达4个数量级以上.

关键词：基于模型诊断;极小碰集;碰集极小性判定;预剪枝;增量方法

基金资助：国家自然科学基金（61133011，61402196，61272208，61003101，61170092）；中国博士后科学基金（2013M541302）；吉林省科技发展计划基金（20140520067JH）；浙江师范大学计算机软件与理论省级重中之重学科开放基金（ZSDZZZZXK12）