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

摘要：

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

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

所属期刊栏目：29

分类号：TP18(自动化基础理论)

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

在线出版日期：2019-01-09（万方平台首次上网日期，不代表论文的发表时间）

页数：共14页

页码：3733-3746