科研之友
微信
新浪微博
Facebook
分享链接
摘要
在基于模型的诊断推理过程中，极小碰集求解效率是决定诊断快慢的关键一步.本文在原有极小冲突集合簇与极小碰集簇的基础上，充分考虑它们与新增冲突集中元素的关系，提出一种新型的优化增量策略.在原有极小冲突集簇中，首先通过启发式策略抽取部分集合进行极小化，从而大幅度缩短求解时间；然后通过优化的增量策略快速补全并更新解集，进而提高整体求解效率.为进一步提高算法的效率，提出按冲突集的势从小到大增量排序，利用新型优化的增量策略依次递归计算，并最终求得原始问题集合簇所有解集的全增量算法CIMHS(Complete Increment Minimal Hitting Set).实验结果表明，在许多情形下，CIMHS算法较其他经典的极小碰集求解算法，可减少1至3个数量级的运行时间.
- 单位
