基于模型诊断中求解环形数据极小碰集的算法

来源：计算机集成制造系统杂志2026年第3期北京时间：

作者：李红玫, 黄森, 赵相福

单位：1.烟台大学计算机与控制工程学院2.吉林大学计算机科学与技术学院

摘要：极小碰集求解是人工智能领域中的重要问题之一。然而,当前多数求解算法往往忽视了冲突集合簇的结构特性,而结构信息在求解大规模问题时具有至关重要的作用。本文提出求解环形结构数据的环形算法(CLM)。该算法将复杂的环形结构简化成线性结构,采用LinearMerge算法高效求解;在产生所有极小候选解的过程中,将每个候选解的独立覆盖检测范围缩小至两个集合,避免了复杂的极小化操作,大幅度缩短了求解时间。为进一步提高效率,提出优化的环形算法(ICLM),该优化策略通过寻找相交元素个数最多的两个集合,连续选取交集元素将环形数据分解成若干相同的线性数据,利用节点重用方法提高求解效率。实验结果表明,CLM算法的求解时间相比于其他经典算法最多可减少99%以上。ICLM算法的时间复杂度大大降低,求解时间相比于CLM算法最多可减少45%以上。

关键词：极小碰集,线性数据,环形数据,布尔代数,独立覆盖

基金资助：国家自然科学基金资助项目(61972360,62072392);山东省自然科学基金资助项目(ZR2024MF111).