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



Abstract:Minimal hitting set (MHS) problem is an important problem with widely applications in artificial intelligence. During computing all minimal hitting set, how to check the minimality of hitting sets is a key issue. Most of exhaustive MHS algorithms ensure the minimality of results by using subset checking method where its effectiveness is mainly relevant to the scale of minimal hitting sets, i.e., the larger the scale of the MHSs is, the lower the effectiveness of this method has. Consequently, when coming to solve the massive cases, the effectiveness of these algorithms is not high. To overcome this problem, this paper proposes independent coverage checking (ICC) and then develops it into an incremental method named ⅡCC. The effectiveness of this method is irrelevant to the scale of minimal hitting sets. Moreover, when computing all MHS by the incremental MHS algorithm with ⅡCC, it can incrementally test the minimality of candidate solutions, resulting in cutting down many unnecessary non-minimal hitting sets. ⅡCC is used to optimize the Boolean algorithm which is an incremental MHS algorithm using subset checking. The results show that ⅡCC method significantly outperforms the subset checking methods in terms of running time.



PDF全文下载地址:

http://jos.org.cn/jos/article/pdf/5311