声明
严正声明：本站非期刊官网，非中介代理。
本站仅提供学术规范服务：快速预审、润色编辑服务、中英文查重、降重、去重服务、推荐合适的期刊投稿等学术规范服务。 如需提供学术规范服务请联系在线编辑。
国内刊号：11-1777/TP
国际刊号：1000-1239
发布日期:
作者：王荣全,欧阳丹彤,王艺源,刘思光,张立明,
关键词：基于模型诊断, 极小碰集, 可满足性问题, 碰集极小化, 集合覆盖,
在基于模型诊断中，诊断解通常是根据极小冲突集合簇进行相应的计算得到所有的极小碰集，所以提高极小碰集的求解效率是模型诊断的核心问题.因此提出结合基于元素覆盖集合度(degreeofelementcoverage,DOEC)极小化策略的SAT求解极小碰集的方法SAT-MHS(satisfiabilityproblem-minimalhittingsets).首先，方法SAT-MHS将碰集求解问题转换成SAT问题,即把所有的冲突集合以子句形式表示成SAT的输入CNF进行迭代求解.其次,提出比现有的基于子超集检测极小化策略(sub-supersetdetectingminimization,SSDM)更为高效的DOEC极小化策略进行极小化处理.由实验数据可见，与SSDM极小化策略相比，其优点是缩减了求解空间和迭代求解次数，尤其当求解规模较大问题时，其极小化效率越高.主要是因为其极小化不会随着待求解问题规模的增加而增加，而是只与冲突集合簇的大小相关，因此时间复杂度较低.实验结果表明，对于一些较大的实例，与目前效率最好的Boolean方法相比，SAT-MHS方法高效且易于实现，求解速度能提高10~20倍，DOEC极小化策略对比传统SSDM极小化策略能达到40倍左右.
来源：2018年第6期
《计算机研究与发展》期刊编辑部
严正声明：本站非期刊官网，非中介代理。
本站仅提供学术规范服务：快速预审、润色编辑服务、中英文查重、降重、去重服务、推荐合适的期刊投稿等学术规范服务。 如需提供学术规范服务请联系在线编辑。