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

摘要

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