检索结果-南通市图书馆

计算机研究与发展 2024年

作者：蒋璐宇欧阳丹彤张奇太然张立明吉林大学计算机科学与技术学院符号计算与知识工程教育部重点实验室(吉林大学)

极小不可满足子集（minimal unsatisfiable subset，MUS）的求解是理论计算机科学的重要问题.由于极小不可满足子集的个数随问题规模呈指数级增长，现有算法致力于在合适的时间限制内尽求解出可能多的MUS.在庞大的搜索空间中，选择合适... 详细信息

极小不可满足子集（minimal unsatisfiable subset，MUS）的求解是理论计算机科学的重要问题.由于极小不可满足子集的个数随问题规模呈指数级增长，现有算法致力于在合适的时间限制内尽求解出可能多的MUS.在庞大的搜索空间中，选择合适的节点来扩展可以大幅减小收缩和扩充操作的时间开销，从而提高算法的求解效率.提出一种基于增量信息交互的MUS求解算法MARCO-MSS4MUS，利用MUS、极小修正集（minimal correction set，MCS）和极大可满足子集（maximal satisfiable subset，MSS）之间的对偶和互补关系，采用MARCO算法框架增量求解MSS 和MUS的过程中，根据已求解的MSS的交集和并集信息辅助选择节点来扩展，即通过增量的MSS信息启发用于扩展节点选择以加速MUS枚举，这一过程同时利于算法找到更多的MSS，在枚举过程中新识别出的MSS又能辅助下一轮扩展节点的选择，从而实现了增量信息的有效交互.针对交互的增量信息提出2个定理及2个推论，从理论角度分析了MARCO-MSS4MUS算法的可行性，并通过MUS标准测试用例上的实验验证了算法相较于当前先进算法的优越性，在部分测试用例上的结果显示新算法的枚举效率和枚举获胜个数较已有算法均有显著的提高.

关键词：极小不可满足子集极大可满足子集不可行分析碰集对偶性

来源：

同方期刊数据库评论

在线全文

同方期刊数据库

学校读者我要写书评

暂无评论

结合问题特征与局部搜索的极小不可满足子集求解方法研究

结合问题特征与局部搜索的极小不可满足子集求解方法研究

引用

作者：董博文吉林大学

学位级别：硕士

在计算机科学领域中,命题可满足性问题（Propositional Satisifiability problem,SAT问题）是被研究最多的约束可满足性问题之一。SAT问题源于数理逻辑中经典命题逻辑关于公式的可满足性概念,是计算机科学理论中的重要问题,同时也是第... 详细信息

在计算机科学领域中,命题可满足性问题（Propositional Satisifiability problem,SAT问题）是被研究最多的约束可满足性问题之一。SAT问题源于数理逻辑中经典命题逻辑关于公式的可满足性概念,是计算机科学理论中的重要问题,同时也是第一个已知的NP-complete问题,对于SAT问题的理论研究极大地推动了计算机科学的发展。极小不可满足子集（Minimal Unsatisfiable Subset,MUS）是SAT问题的一个扩展问题:对于一组约束集合,如果该约束集不可以同时被满足,则可以从中找到MUS,每一个MUS都代表着约束与约束之间的冲突信息。但是,由于约束中冲突的数量可能是指数级别的,完整的MUS枚举是非常耗时的,所以对于MUS的部分枚举的研究是很有意义的。在理想情况下,每一个MUS的求解时间都要求不大于求解单个MUS的时间。在目前的MUS枚举算法当中,Re MUS是求解MUS效率最高的方法,该算法以在线递归的方式求解并输出MUS,并且可以在任意时刻停止。其主要是通过减少可满足性检测的次数,从而加快了求解MUS的速度。在给定的时间限制内,得到了更多的MUS。本文将在该算法的基础上,提出两种改进的算法,思路如下:目前主流的MUS枚举算法的遍历结构基本都为哈斯图,通过哈斯图可以构建节点与节点之间的联系,并且从图中选择某一节点,调用完备的SAT求解器判断该节点的可满足性。而对于一组约束集合,完备求解器可以肯定地回答是否存在一组赋值使得该约束集可满足,但是并不能够保证什么时候能得到结果,所以盲目的调用完备SAT求解器无疑会消耗大量的时间。而不完备的SAT求解器则注重在更短的时间内找到该约束集的一组可行赋值。然而,如果不完备求解器未找到一组可行赋值,则无法确定该约束集的可满足性。由此,本文提出了一种将不完备求解器与完备求解器结合使用的MUS求解算法LSRe MUS:当求解的某一子集的基数（包含约束的数量）小于一定值时则调用不完备的求解器,当不完备求解器无法确定其可满足性时,则再次调用完备求解器进行求解。通过这种方法,有效降低了验证约束集的可满足性的时间。此外,本文在LSRe MUS的基础上对于每一次迭代中约束集的选择进行优化,给出了改进的LSRe MUS-U算法。当一个约束出现在某一个或更多MUSes当中时,则该约束更有可能出现在其他的MUS当中,由此,本方法会为所有已知的MUSes创建一个集合,在每找到一个MUS时,都将其中的约束都放入该集合当中,并在下一次约束集的选择时添加该集合中的部分约束。通过这种方法,有效减少了不必要的可满足性检查并提升了求解效率。

关键词：极小不可满足子集哈斯图 SAT求解器局部搜索命题可满足性问题不可满足性分析

来源：

同方学位论文库评论

在线全文

同方学位论文库

学校读者我要写书评

暂无评论

针对MUS求解问题的加强剪枝策略

引用

软件学报 2024年第4期35卷 1964-1979页

作者：蒋璐宇欧阳丹彤董博文张立明吉林大学计算机科学与技术学院吉林长春130012 吉林大学软件学院吉林长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 吉林长春130012

极小不可满足子集(minimal unsatisfiable subsets,MUS)的求解是布尔可满足性问题中的一个重要子问题.对于一个给定的不可满足问题,其MUS的求解能够反映出问题中导致其不可满足的关键原因.然而,MUS的求解是一项极其耗时的任务,不同的剪... 详细信息

极小不可满足子集(minimal unsatisfiable subsets,MUS)的求解是布尔可满足性问题中的一个重要子问题.对于一个给定的不可满足问题,其MUS的求解能够反映出问题中导致其不可满足的关键原因.然而,MUS的求解是一项极其耗时的任务,不同的剪枝过程将直接影响到搜索空间的大小、算法的迭代次数,从而影响算法的求解效率.提出一种针对MUS求解的加强剪枝策略ABC(accelerating by critical MSS),依据MSS、MCS、MUS这3者之间的对偶性和碰集关系特点,提出cMSS和subMUS概念,并总结出4条性质,即每个MUS必是subMUS的超集,进而在避免对MCS的碰集进行求解的情况下有效利用MUS和MCS互为碰集的特征,有效避免求解碰集时的时间开销.当subMUS不可满足时,则subMUS是唯一的MUS,算法将提前结束执行;当subMUS可满足时,则剪枝掉此节点,进而有效避免对求解空间中的冗余空间进行搜索.同时,通过理论证明ABC策略的有效性,并将其应用于目前最高效的单一化模型算法MARCO和双模型算法MARCO-MAM,在标准测试用例下的实验结果表明,该策略可以有效地对搜索空间进行进一步剪枝,从而提高MUS的枚举效率.

关键词：极小不可满足子集极大可满足子集 MUS枚举幂集探索不可行分析

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

基于双模型的MUS求解方法

引用

计算机研究与发展 2019年第12期56卷 2623-2631页

作者：欧阳丹彤高菡田乃予刘梦张立明吉林大学软件学院长春130012 吉林大学计算机科学与技术学院长春130012 符号计算与知识工程教育部重点实验室(吉林大学) 长春130012

求解不可满足问题的极小不可满足子集(minimal unsatisfiable subset,MUS)是人工智能领域的重要研究方向.MARCO-M方法是目前采用单一极大化模型求解MUS效率最高的方法,但此方法未对求解空间进行进一步有效剪枝.针对MARCO-M方法的不足,... 详细信息

求解不可满足问题的极小不可满足子集(minimal unsatisfiable subset,MUS)是人工智能领域的重要研究方向.MARCO-M方法是目前采用单一极大化模型求解MUS效率最高的方法,但此方法未对求解空间进行进一步有效剪枝.针对MARCO-M方法的不足,结合可满足问题求解复杂度低于不可满足问题的特征,提出基于双模型即极大中间化模型的MARCO-MAM方法求解MUS.此方法对中间模型求解若得到极大可满足子集(maximal satisfiable subset,MSS),则利用可满足问题对应求解空间对不可满足问题的求解空间进行剪枝,即利用MSS对应的空间来对MUS搜索空间进行剪枝,进而通过缩减未探索空间来提高MUS求解效率;如果中间模型进行求解得到MUS时,则减少了MARCO-M方法中MUS的不可满足迭代求解次数.此方法避免了MARCO-M方法单一极大化模型求解MUS时未有效利用其他优化技术对求解空间进行剪枝的问题.实验结果表明:与MARCO-M方法相比MARCO-MAM方法效率较高,尤其在大规模问题或较大搜索空间时效率提高更为明显.

关键词：命题可满足问题极小不可满足子集极大可满足子集幂集探索双模型

来源：

维普期刊数据库

同方期刊数据库评论

在线全文

学校读者我要写书评

暂无评论

欢迎您,

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案：

请选择收藏分类：

通借通还

欢迎您,

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

在线全文

在线全文

在线全文

在线全文

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：