第5期2023年5月电子学报ACTAELECTRONICASINICAVol.51No.5May2023CIMHS：基于优化增量策略求解极小碰集的方法魏霞1，赵相福1，黄森2（1.烟台大学计算机与控制工程学院，山东烟台264005；2.浙江师范大学计算机系，浙江金华321000）摘要：在基于模型的诊断推理过程中，极小碰集求解效率是决定诊断快慢的关键一步.本文在原有极小冲突集合簇与极小碰集簇的基础上，充分考虑它们与新增冲突集中元素的关系，提出一种新型的优化增量策略.在原有极小冲突集簇中，首先通过启发式策略抽取部分集合进行极小化，从而大幅度缩短求解时间；然后通过优化的增量策略快速补全并更新解集，进而提高整体求解效率.为进一步提高算法的效率，提出按冲突集的势从小到大增量排序，利用新型优化的增量策略依次递归计算，并最终求得原始问题集合簇所有解集的全增量算法CIMHS（CompleteIncre⁃mentMinimalHittingSet）.实验结果表明，在许多情形下，CIMHS算法较其他经典的极小碰集求解算法，可减少1至3个数量级的运行时间.关键词：基于模型诊断；极小冲突集；极小碰集；增量策略；启发式策略；全增量基金项目：国家自然科学基金（No.61972360，No.62072392）中图分类号：TP306文献标识码：A文章编号：0372-2112(2023)05-1334-07电子学报URL:http://www.ejournal.org.cnDOI:10.12263/DZXB.20220482CIMHS:AMethodofComputingallMinimalHittingSetsforMinimalConflictSetsBasedonanOptimizedIncrementalStrategyWEIXia1,ZHAOXiang-fu1,HUANGSen2（1.SchoolofComputerandControlEngineering，YantaiUniversity，Yantai，Shandong264005，China;2.DepartmentofComputer，ZhejiangNormalUniversity，Jinhua，Zhejiang321000，China）Abstract:Intheprocessofmodel-baseddiagnosis,itisakeysteptoefficientlygenerateallminimalhittingsets.Inthispaper,anoveloptimizationstrategyforincrementaldiagnosisisproposed.Whenanewconflictsetisadded,therela⁃tionshipbetweentheoriginalminimalhittingsetsandthenewlyaddedconflictsetwillbeexploredthoroughly.Thetimecostcanbegreatlyreducedbyjoiningthecorrespondingheuristicstrategytoselectthespecificsetsinthecourseofmini⁃malitychecking.Thecomputingperformancecanbeimprovedconsiderablybyintroducingtheoptimizedincrementalstrat⁃egytoupdatethefinalresults.Furthermore,inordertoobtainthehigherefficiency,analgorit...
