Article(id=1327010734699032651, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327010443811468006, articleNumber=null, orderNo=null, doi=10.7544/issn1000-1239.202440326, pmid=null, cstr=null, oa=null, hot=null, price=null, onlineType=0, articleFormat=0, articleType=null, articleTypeStr=research-article, receivedDate=1716220800000, receivedDateStr=2024-05-21, revisedDate=1727539200000, revisedDateStr=2024-09-29, acceptedDate=1728921600000, acceptedDateStr=2024-10-15, onlineDate=1794313613818, onlineDateStr=2026-11-10, pubDate=1746028800000, pubDateStr=2025-05-01, doiRegisterDate=null, doiRegisterDateStr=null, onlineIssueDate=1794313613818, onlineIssueDateStr=2026-11-10, onlineJustAcceptDate=null, onlineJustAcceptDateStr=null, onlineFirstDate=null, onlineFirstDateStr=null, sourceXml=null, magXml=null, createTime=1794313613818, creator=13701087609, updateTime=1794313613818, updator=13701087609, issue=Issue{id=1327010443811468006, tenantId=1146029695717560320, journalId=1324759914146529478, year='2025', volume='62', issue='5', pageStart='1091', pageEnd='1329', issueExtLink='null', onlineDate='null', pubDate='1746028800000', pubDateStr='2025-05-01', beforeIssueId=null, nextIssueId=null, price=null, status=1, issueComplete=1, articleOrder=1, issueType=-1, specialIssue=null, createTime=1794313544465, creator='13701087609', updateTime=1794376781779, updator='13701087609', preIssue=null, nextIssue=null, articleTotal=null, ext={EN=IssueExt(id=1327275680737374365, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327010443811468006, language=EN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=), CN=IssueExt(id=1327275680737374366, tenantId=1146029695717560320, journalId=1324759914146529478, issueId=1327010443811468006, language=CN, specialIssueTitle=, coverIllustrator=null, specialIssueEditor=, specialIssueAbout=)}, issueFiles=null, downloadFileDto=null}, startPage=1226, endPage=1234, ext={EN=ArticleExt(id=1327010735038771276, articleId=1327010734699032651, tenantId=1146029695717560320, journalId=1324759914146529478, language=EN, title=Incremental Information Interaction-Based Algorithm for Enumerating MUSes, columnId=1325489891789910943, journalTitle=Journal of Computer Research and Development, columnName=Artificial Intelligence, runingTitle=null, highlight=null, articleAbstract=

Enumerating minimal unsatisfiable subsets (MUS) is an important issue in theoretical computer science. Given an unsatisfiable Boolean formula, the number of its MUS is exponentially related to the formula’s scale. Contemporary methods aim to identify MUSes as many as possible within appropriate time limits. Dealing with the huge search space and choosing a suitable node to expand can markedly reduce the time consumption on shrink and grow operations, thereby the algorithm could obtain better performance. We introduce an incremental information interaction-based MUS solving algorithm, denoted as MARCO-MSS4MUS, which utilizes the duality and complementary relationships among MUS, minimal correction set (MCS), and maximal satisfiable subset (MSS). Based on the framework of MARCO algorithm, the proposed algorithm selects a more suitable node to expand via intersection and union information of previously identified MSSes during the search, i.e., the incremental MSS information is employed as a heuristic for node selection to accelerate the enumeration of MUS. This process also benefits in identifying more MSSes, in turn, the incremental MSS information helps select a better node for next exploration, thereby achieving an interaction of incremental information. Two theorems and two corollaries regarding interactive incremental information are proposed and the feasibility of our MARCO-MSS4MUS algorithm is theoretically analyzed. Experiments on standard MUS benchmark instances show the superiority of the proposed algorithm over state-of-the-art algorithms. Both the enumeration efficiency and the number of enumerated wins of the proposed algorithm are significantly improved compared with existing algorithms.

, authors=Luyu Jiang, Dantong Ouyang, Qi Zhang, Ran Tai, Liming Zhang*, authorsList=Luyu Jiang, Dantong Ouyang, Qi Zhang, Ran Tai, Liming Zhang, authorCompany=null, correspAuthors=Liming Zhang, authorNote=

born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

, correspAuthorsNote=null, copyrightStatement=Copyright © 2025 Journal of Computer Research and Development. All rights reserved., copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=null, magXml=null, pdfUrl=null, pdf=null, pdfFileSize=null, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=null, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=null, mapNumber=null, fund=null), CN=ArticleExt(id=1327010738629095517, articleId=1327010734699032651, tenantId=1146029695717560320, journalId=1324759914146529478, language=CN, title=基于增量信息交互的极小不可满足子集求解算法, columnId=1325489892104483745, journalTitle=计算机研究与发展, columnName=人工智能, runingTitle=null, highlight=null, articleAbstract=

极小不可满足子集(minimal unsatisfiable subset,MUS)的求解是理论计算机科学的重要问题. 由于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标准测试用例上的实验验证了所提算法相较于当前先进算法的优越性,在部分测试用例上的结果显示所提算法的枚举效率和枚举获胜个数较已有算法均有显著的提高.

, authors=蒋璐宇, 欧阳丹彤, 张奇, 太然, 张立明*, authorsList=蒋璐宇, 欧阳丹彤, 张奇, 太然, 张立明, authorCompany=null, correspAuthors=张立明, authorNote=

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题、组合优化问题、基于模型的诊断问题

1968年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为自动推理、基于模型的诊断问题

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题和基于模型的诊断问题

1997年生. 博士研究生. CCF学生会员. 主要研究方向为组合优化、基于模型的诊断问题

1980年生. 博士,正高级工程师. CCF高级会员. 主要研究方向为可满足性问题和基于模型的诊断问题

, correspAuthorsNote=
张立明()
, copyrightStatement=版权所有 © 2025 计算机研究与发展编辑部, copyrightOwner=null, extLink=null, articleAbsUrl=null, sourceXml=dI1fxYJtAWzxgNVFV4FgLQ==, magXml=dvtKqPy4ppyAK9VKi5VsvA==, pdfUrl=null, pdf=BNkKSNYPQRCWQq8fgl/L0A==, pdfFileSize=1105328, pdfExtLink=null, richHtmlUrl=null, mobilePdfUrl=null, reviewReport=null, pdfFirstPage=null, abstractGraph=ubaAPB42uh8tVtLJBLR6aQ==, abstractGraphContent=null, abstractVideo=null, citation=null, cebUrl=null, magXmlContent=y/yUl87+i96rPLduDLrshQ==, mapNumber=null, fund=null)}, authors=[Author(id=1327010739082080357, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=jiangluyu1998@163.com, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739136606310, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739082080357, language=EN, stringName=Luyu Jiang, firstName=Luyu, middleName=null, lastName=Jiang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739207909479, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739082080357, language=CN, stringName=蒋璐宇, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"GpNg/Pg3cVLjz+Op3l8zYQ==","content":"

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题、组合优化问题、基于模型的诊断问题

"}, bioImg=GpNg/Pg3cVLjz+Op3l8zYQ==, bioContent=

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题、组合优化问题、基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739279212649, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=ouyd@jlu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739379875946, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739279212649, language=EN, stringName=Dantong Ouyang, firstName=Dantong, middleName=null, lastName=Ouyang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

"}, bioImg=null, bioContent=

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739459567723, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739279212649, language=CN, stringName=欧阳丹彤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"7bLggtRfWc81/92mtF+HLw==","content":"

1968年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为自动推理、基于模型的诊断问题

"}, bioImg=7bLggtRfWc81/92mtF+HLw==, bioContent=

1968年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为自动推理、基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739514093677, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739581202542, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739514093677, language=EN, stringName=Qi Zhang, firstName=Qi, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739652505711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739514093677, language=CN, stringName=张奇, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"m/Fq2UFWUDuoz2occI3Ofg==","content":"

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题和基于模型的诊断问题

"}, bioImg=m/Fq2UFWUDuoz2occI3Ofg==, bioContent=

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题和基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739765751921, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739832860786, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739765751921, language=EN, stringName=Ran Tai, firstName=Ran, middleName=null, lastName=Tai, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739899969651, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739765751921, language=CN, stringName=太然, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"8wzuuJL3O2VJ4AR14cX5fg==","content":"

1997年生. 博士研究生. CCF学生会员. 主要研究方向为组合优化、基于模型的诊断问题

"}, bioImg=8wzuuJL3O2VJ4AR14cX5fg==, bioContent=

1997年生. 博士研究生. CCF学生会员. 主要研究方向为组合优化、基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739962884213, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=limingzhang@jlu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327010740013215862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739962884213, language=EN, stringName=Liming Zhang, firstName=Liming, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010740063547511, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739962884213, language=CN, stringName=张立明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"p7CovTa+pNlw0WoAHlcsog==","content":"

1980年生. 博士,正高级工程师. CCF高级会员. 主要研究方向为可满足性问题和基于模型的诊断问题

"}, bioImg=p7CovTa+pNlw0WoAHlcsog==, bioContent=

1980年生. 博士,正高级工程师. CCF高级会员. 主要研究方向为可满足性问题和基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null)], keywords=[Keyword(id=1327010740189376632, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, orderNo=1, keyword=minimal unsatisfiable subset (MUS)), Keyword(id=1327010741846126715, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, orderNo=2, keyword=maximal satisfiable subset (MSS)), Keyword(id=1327010742039064700, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, orderNo=3, keyword=infeasibility analysis), Keyword(id=1327010742232002685, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, orderNo=4, keyword=hitting set), Keyword(id=1327010742320083070, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, orderNo=5, keyword=duality), Keyword(id=1327010742399774847, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, orderNo=1, keyword=极小不可满足子集), Keyword(id=1327010742475272320, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, orderNo=2, keyword=极大可满足子集), Keyword(id=1327010742550769793, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, orderNo=3, keyword=不可行分析), Keyword(id=1327010742622072962, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, orderNo=4, keyword=碰集), Keyword(id=1327010742680793219, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, orderNo=5, keyword=对偶性)], refs=[Reference(id=1327010744119439503, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=1, rfOrder=0, authorNames=null, journalName=null, refType=null, unstructuredReference=Cai Shaowei, Zhang Xindi. Deep cooperation of CDCL and local search for SAT[C]//Proc of the 24th Int Conf on Theory and Applications of Satisfiability Testing. Berlin: Springer, 2021: 64−81, articleTitle=null, refAbstract=null), Reference(id=1327010744173965456, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=2, rfOrder=1, authorNames=null, journalName=null, refType=null, unstructuredReference=Cai Shaowei, Zhang Xindi, Fleury M, et al. Better decision heuristics in CDCL through local search and target phases[J]. Journal of Artificial Intelligence Research, 2022, 74: 1515−1563, articleTitle=null, refAbstract=null), Reference(id=1327010744236880018, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=3, rfOrder=2, authorNames=null, journalName=null, refType=null, unstructuredReference=Zheng Jiongzhi, He Kun, Zhou Jianrong, et al. BandMaxSAT: A local search MaxSAT solver with multi-armed bandit[C]//Proc of the 31st Int Joint Conf on Artificial Intelligence. Freiburg: IJCAI, 2022: 1901–1907, articleTitle=null, refAbstract=null), Reference(id=1327010744316571795, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=3, authorNames=null, journalName=null, refType=null, unstructuredReference=王荣全,欧阳丹彤,王艺源,等. 结合DOEC极小化策略的SAT求解极小碰集方法[J],计算机研究与发展,2018,55(6):1273–1281, articleTitle=null, refAbstract=null), Reference(id=1327010744417235092, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=4, rfOrder=4, authorNames=null, journalName=null, refType=null, unstructuredReference=Wang Rongquan, Ouyang Dantong, Wang Yiyuan, et al. Solving minimal hitting sets method with SAT based on DOEC minimization[J]. Journal of Computer Research and Development, 2018, 55(6): 1273–1281 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327010744488538261, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=5, rfOrder=5, authorNames=null, journalName=null, refType=null, unstructuredReference=Metodi A, Stern R, Kalech M, et al. A novel SAT-based approach to model based diagnosis[J]. Journal of Artificial Intelligence Research, 2014, 51: 377−411, articleTitle=null, refAbstract=null), Reference(id=1327010744564035734, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=6, authorNames=null, journalName=null, refType=null, unstructuredReference=田乃予,欧阳丹彤,刘梦,等. 基于子集一致性检测的诊断解极小性判定方法[J],计算机研究与发展,2019,56(7):1396–1407, articleTitle=null, refAbstract=null), Reference(id=1327010744622755991, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=6, rfOrder=7, authorNames=null, journalName=null, refType=null, unstructuredReference=Tian Naiyu, Ouyang Dantong, Liu Meng, et al. A method of minimality-checking of diagnosis based on subset consistency detection[J]. Journal of Computer Research and Development, 2019, 56(7): 1396–1407 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327010744689864856, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=7, rfOrder=8, authorNames=null, journalName=null, refType=null, unstructuredReference=Zhou Huisi, Ouyang Dantong, Zhao Xiangfu, et al. Two compacted models for efficient model-based diagnosis[C]//Proc of the 36th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2022: 3885–3893, articleTitle=null, refAbstract=null), Reference(id=1327010746325643417, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=8, rfOrder=9, authorNames=null, journalName=null, refType=null, unstructuredReference=Ouyang Dantong, Liao Mengting, Ye Yuxin. Lightweight axiom pinpointing via replicated driver and customized SAT-solving[J]. Frontiers of Computer Science, 2023, 17(2): 172315, articleTitle=null, refAbstract=null), Reference(id=1327010746401140890, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=9, rfOrder=10, authorNames=null, journalName=null, refType=null, unstructuredReference=Arif M F, Mencía C, Marques-Silva J. Efficient MUS enumeration of Horn formulae with applications to axiom pinpointing[C]//Proc of the 18th Int Conf on Theory and Applications of Satisfiability Testing. Berlin: Springer, 2015: 324–342, articleTitle=null, refAbstract=null), Reference(id=1327010746459861147, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=10, rfOrder=11, authorNames=null, journalName=null, refType=null, unstructuredReference=Hunter A, Konieczny S. On the measure of conflicts: Shapley inconsistency values[J]. Artificial Intelligence, 2010, 174(14): 1007−1026, articleTitle=null, refAbstract=null), Reference(id=1327010746526970012, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=11, rfOrder=12, authorNames=null, journalName=null, refType=null, unstructuredReference=Xiao Guohui, Ma Yue. Inconsistency measurement based on variables in minimal unsatisfiable subsets[C]//Proc of the 20th European Conf on Artificial Intelligence. Ohmsha: IOS, 2012: 864–869, articleTitle=null, refAbstract=null), Reference(id=1327010746615050397, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=12, rfOrder=13, authorNames=null, journalName=null, refType=null, unstructuredReference=Shazli S Z, Tahoori M B. Using Boolean satisfiability for computing soft error rates in early design stages[J]. Microelectronics Reliability, 2010, 50(1): 149−159, articleTitle=null, refAbstract=null), Reference(id=1327010746686353566, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=13, rfOrder=14, authorNames=null, journalName=null, refType=null, unstructuredReference=Andraus Z, Liffiton M, Sakallah K. Reveal: A formal verification tool for Verilog designs[C]//Proc of the 15th Int Conf on Logic for Programming Artificial Intelligence and Reasoning. Berlin: Springer, 2008: 343–352, articleTitle=null, refAbstract=null), Reference(id=1327010746787016863, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=14, rfOrder=15, authorNames=null, journalName=null, refType=null, unstructuredReference=Liffiton M, Sakallah K. On finding all minimally unsatisfiable subformulas[G]//LNCS 3569: Proc of the 8th Int Conf on Theory & Applications of Satisfiability Testing. Berlin: Springer, 2005: 173–186, articleTitle=null, refAbstract=null), Reference(id=1327010746849931424, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=15, rfOrder=16, authorNames=null, journalName=null, refType=null, unstructuredReference=Liffiton M, Sakallah K. Algorithms for computing minimal unsatisfiable subsets of constraints[J]. Journal of Automated Reasoning, 2008, 40(1): 1−33, articleTitle=null, refAbstract=null), Reference(id=1327010746925428897, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=16, rfOrder=17, authorNames=null, journalName=null, refType=null, unstructuredReference=Bailey J, Stuckey P. Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization[C]//Proc of the 7th Int Workshop on Practical Aspects of Declarative Languages. Berlin: Springer, 2005: 174–186, articleTitle=null, refAbstract=null), Reference(id=1327010747009314978, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=17, rfOrder=18, authorNames=null, journalName=null, refType=null, unstructuredReference=Liffiton M, Malik A. Enumerating infeasibility: Finding multiple MUSes quickly[C]//Proc of the 10th Int Conf on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Berlin: Springer, 2013: 160–175, articleTitle=null, refAbstract=null), Reference(id=1327010747101589667, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=18, rfOrder=19, authorNames=null, journalName=null, refType=null, unstructuredReference=Liffiton M, Previti A, Malik A, et al. Fast, flexible MUS enumeration[J]. Constraints, 2016, 21(2): 223−250, articleTitle=null, refAbstract=null), Reference(id=1327010747177087140, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=20, authorNames=null, journalName=null, refType=null, unstructuredReference=欧阳丹彤,高菡,田乃予,等. 基于双模型的MUS求解方法[J],计算机研究与发展,2019,56(12):2623−2631, articleTitle=null, refAbstract=null), Reference(id=1327010747290333349, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=19, rfOrder=21, authorNames=null, journalName=null, refType=null, unstructuredReference=Ouyang Dantong, Gao Han, Tian Naiyu, et al. MUS enumeration based on double-model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623–2631 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327010747416162470, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=22, authorNames=null, journalName=null, refType=null, unstructuredReference=蒋璐宇,欧阳丹彤,董博文,等. 针对MUS求解问题的加强剪枝策略[J],软件学报,2024,35(4):1964−1979, articleTitle=null, refAbstract=null), Reference(id=1327010747479077031, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=20, rfOrder=23, authorNames=null, journalName=null, refType=null, unstructuredReference=Jiang Luyu, Ouyang Dantong, Dong Bowen, et al. Enhanced pruning scheme for enumerating MUS[J]. Journal of Software, 2024, 35(4): 1964−1979 (in Chinese), articleTitle=null, refAbstract=null), Reference(id=1327010747546185896, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=21, rfOrder=24, authorNames=null, journalName=null, refType=null, unstructuredReference=Bendík J, Benes N, Cerna I, et al. Tunable online MUS/MSS enumeration[G]//LIPIcs 65: Proc of the 36th IARCS Annual Conf on Foundations of Software Technology and Theoretical Computer Science. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2016: 50: 1–50: 13, articleTitle=null, refAbstract=null), Reference(id=1327010747609100457, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=22, rfOrder=25, authorNames=null, journalName=null, refType=null, unstructuredReference=Bendík J, Cerna I, Benes N. Recursive online enumeration of all minimal unsatisfiable subsets[G]//LNCS 11138: Proc of the 16th Int Symp on Automated Technology for Verification and Analysis. Berlin: Springer, 2018: 143–159, articleTitle=null, refAbstract=null), Reference(id=1327010747684597930, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=23, rfOrder=26, authorNames=null, journalName=null, refType=null, unstructuredReference=Bendík J, Cerna I. Replication-guided enumeration of minimal unsatisfiable subsets[C]//Proc of the 26th Int Conf on Principles and Practice of Constraint Programming. Berlin: Springer, 2020: 37–54, articleTitle=null, refAbstract=null), Reference(id=1327010747747512491, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=24, rfOrder=27, authorNames=null, journalName=null, refType=null, unstructuredReference=Bendík J, Cerna I. Rotation based MSS/MCS enumeration[C]//Proc of the 23rd Int Conf on Logic for Programming, Artificial Intelligence and Reasoning. Stockport, UK: EasyChair, 2020: 120–137, articleTitle=null, refAbstract=null), Reference(id=1327010747810427052, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=25, rfOrder=28, authorNames=null, journalName=null, refType=null, unstructuredReference=Bendík J, Meel K. Counting maximal satisfiable subsets[C]//Proc of the 35th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2021: 3651–3660, articleTitle=null, refAbstract=null), Reference(id=1327010747877535917, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=26, rfOrder=29, authorNames=null, journalName=null, refType=null, unstructuredReference=Bendík J. On decomposition of maximal satisfiable subsets[C]//Proc of the 21st Conf on Formal Methods in Computer Aided Design. Piscataway, NJ: IEEE, 2021: 212−221, articleTitle=null, refAbstract=null), Reference(id=1327010747953033390, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=27, rfOrder=30, authorNames=null, journalName=null, refType=null, unstructuredReference=Previti A, Marques-Silva J. Partial MUS enumeration[C]//Proc of the 27th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2013: 818–825, articleTitle=null, refAbstract=null), Reference(id=1327010748024336559, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, doi=null, pmid=null, pmcid=null, year=null, volume=null, issue=null, pageStart=null, pageEnd=null, url=null, language=null, rfNumber=28, rfOrder=31, authorNames=null, journalName=null, refType=null, unstructuredReference=Een N, Sorensson N. An extensible SAT-solver[G]//LNCS 2919: Proc of the 6th Int Conf on Theory and Applications of Satisfiability Testing. Berlin: Springer, 2004: 502–518, articleTitle=null, refAbstract=null)], funds=null, companyList=[AuthorCompany(id=1327010738851393630, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, xref=null, ext=[AuthorCompanyExt(id=1327010738859782239, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, companyId=1327010738851393630, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=College of Computer Science and Technology, Jilin University, Changchun 130012), AuthorCompanyExt(id=1327010738868170848, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, companyId=1327010738851393630, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=吉林大学计算机科学与技术学院 长春 130012)]), AuthorCompany(id=1327010738947862625, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, xref=null, ext=[AuthorCompanyExt(id=1327010738956251234, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, companyId=1327010738947862625, language=EN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012), AuthorCompanyExt(id=1327010738973028451, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, companyId=1327010738947862625, language=CN, country=null, province=null, city=null, postcode=null, companyName=null, departmentName=null, remark=符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012)])], figs=[ArticleFig(id=1327010742789845124, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, label=Figure 1, caption=Hasse diagram, figureFileSmall=NoEZD1fsLF6BjStpnSiFqQ==, figureFileBig=ubaAPB42uh8tVtLJBLR6aQ==, tableContent=null), ArticleFig(id=1327010742856953989, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, label=图1, caption=哈斯图, figureFileSmall=NoEZD1fsLF6BjStpnSiFqQ==, figureFileBig=ubaAPB42uh8tVtLJBLR6aQ==, tableContent=null), ArticleFig(id=1327010743041503367, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, label=Figure 2, caption=Comparative results on win number of each algorithm under different time limits, figureFileSmall=hs7lkWahe2MN0M0uF6N7AA==, figureFileBig=IqpVoxmXV0tq3m3/XJalhw==, tableContent=null), ArticleFig(id=1327010743100223624, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, label=图2, caption=各算法在不同时间限制下的获胜个数对比结果, figureFileSmall=hs7lkWahe2MN0M0uF6N7AA==, figureFileBig=IqpVoxmXV0tq3m3/XJalhw==, tableContent=null), ArticleFig(id=1327010743247024265, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, label=Table 1, caption=Comparative Results on the Number of MUS of Each Algorithm Under 0.5 h Time Limit, figureFileSmall=null, figureFileBig=null, tableContent=
测试用例本文算法MARCO+[18]MARCO-
MAM[19]
MARCO-
ABC[20]
注:黑体数值表示MUS枚举个数的最优结果.
fdmus_b14_134491158181173
fdmus_b14_14153828384
fdmus_b14_2101807880
fdmus_b15_29154515253
fdmus_b15_29451474447
fdmus_b15_3041323331
fdmus_b15_4211151142157
fdmus_b15_4632174191189
fdmus_b17_10371338539500
fdmus_b17_13242587757
fdmus_b17_14562195178186
fdmus_b17_420197158154161
fdmus_b20_1411161718
fdmus_b20_1711201921
fdmus_b20_238145444845
fdmus_b20_341945188190176
fdmus_b20_3491333133
fdmus_b20_3811293231
fdmus_b20_492215384040
fdmus_b20_498520616565
fdmus_b21_1111141314
fdmus_b21_1121141315
fdmus_b21_1671353134
fdmus_b21_481115312831
fdmus_b21_9694115118118
fdmus_b22_1021343636
fdmus_b22_1131121212
fdmus_b22_1331464054
fdmus_b22_1721212223
fdmus_b22_24161292730
fdmus_b22_3561141414
fdmus_b22_488480514751
fdmus_b22_6001151420
fdmus_b22_6621232320
), ArticleFig(id=1327010743398019210, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, label=表1, caption=

0.5 h时间限制下各算法枚举的MUS个数对比结果

, figureFileSmall=null, figureFileBig=null, tableContent=
测试用例本文算法MARCO+[18]MARCO-
MAM[19]
MARCO-
ABC[20]
注:黑体数值表示MUS枚举个数的最优结果.
fdmus_b14_134491158181173
fdmus_b14_14153828384
fdmus_b14_2101807880
fdmus_b15_29154515253
fdmus_b15_29451474447
fdmus_b15_3041323331
fdmus_b15_4211151142157
fdmus_b15_4632174191189
fdmus_b17_10371338539500
fdmus_b17_13242587757
fdmus_b17_14562195178186
fdmus_b17_420197158154161
fdmus_b20_1411161718
fdmus_b20_1711201921
fdmus_b20_238145444845
fdmus_b20_341945188190176
fdmus_b20_3491333133
fdmus_b20_3811293231
fdmus_b20_492215384040
fdmus_b20_498520616565
fdmus_b21_1111141314
fdmus_b21_1121141315
fdmus_b21_1671353134
fdmus_b21_481115312831
fdmus_b21_9694115118118
fdmus_b22_1021343636
fdmus_b22_1131121212
fdmus_b22_1331464054
fdmus_b22_1721212223
fdmus_b22_24161292730
fdmus_b22_3561141414
fdmus_b22_488480514751
fdmus_b22_6001151420
fdmus_b22_6621232320
), ArticleFig(id=1327010743519654027, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, label=Table 2, caption=Comparative Results on the Number of MUS of Each Algorithm Under 1 h Time Limit, figureFileSmall=null, figureFileBig=null, tableContent=
测试用例本文算法MARCO+[18]MARCO-
MAM[19]
MARCO-
ABC[20]
注:黑体数值表示MUS枚举个数的最优结果.
fdmus_b14_1341367513574584
fdmus_b14_141484199194203
fdmus_b14_2104205183204
fdmus_b15_291345102109108
fdmus_b15_29419010093100
fdmus_b15_304175595363
fdmus_b15_421395294305327
fdmus_b15_4632369420405
fdmus_b17_103793833810821085
fdmus_b17_1324188117149116
fdmus_b17_14562386383374
fdmus_b17_420537318323327
fdmus_b20_1411323536
fdmus_b20_1711383538
fdmus_b20_238500939292
fdmus_b20_3412424629600639
fdmus_b20_3491666863
fdmus_b20_3811667167
fdmus_b20_492806888986
fdmus_b20_4981528179176200
fdmus_b21_1111272929
fdmus_b21_1121262627
fdmus_b21_1671706370
fdmus_b21_481924646365
fdmus_b21_96987300309311
fdmus_b22_1021636770
fdmus_b22_1131232325
fdmus_b22_133310098108
fdmus_b22_1721424142
fdmus_b22_241313606060
fdmus_b22_3561282727
fdmus_b22_4881524110106122
fdmus_b22_6001263429
fdmus_b22_6621474438
), ArticleFig(id=1327010743771312268, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, label=表2, caption=

1 h时间限制下各算法枚举的MUS个数对比结果

, figureFileSmall=null, figureFileBig=null, tableContent=
测试用例本文算法MARCO+[18]MARCO-
MAM[19]
MARCO-
ABC[20]
注:黑体数值表示MUS枚举个数的最优结果.
fdmus_b14_1341367513574584
fdmus_b14_141484199194203
fdmus_b14_2104205183204
fdmus_b15_291345102109108
fdmus_b15_29419010093100
fdmus_b15_304175595363
fdmus_b15_421395294305327
fdmus_b15_4632369420405
fdmus_b17_103793833810821085
fdmus_b17_1324188117149116
fdmus_b17_14562386383374
fdmus_b17_420537318323327
fdmus_b20_1411323536
fdmus_b20_1711383538
fdmus_b20_238500939292
fdmus_b20_3412424629600639
fdmus_b20_3491666863
fdmus_b20_3811667167
fdmus_b20_492806888986
fdmus_b20_4981528179176200
fdmus_b21_1111272929
fdmus_b21_1121262627
fdmus_b21_1671706370
fdmus_b21_481924646365
fdmus_b21_96987300309311
fdmus_b22_1021636770
fdmus_b22_1131232325
fdmus_b22_133310098108
fdmus_b22_1721424142
fdmus_b22_241313606060
fdmus_b22_3561282727
fdmus_b22_4881524110106122
fdmus_b22_6001263429
fdmus_b22_6621474438
), ArticleFig(id=1327010743897141389, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=EN, label=Table 3, caption=Comparative Results on the Number of MUS of Each Algorithm Under 2 h Time Limit, figureFileSmall=null, figureFileBig=null, tableContent=
测试用例本文算法MARCO+[18]MARCO-
MAM[19]
MARCO-
ABC[20]
注:黑体数值表示MUS枚举个数的最优结果.
fdmus_b14_1342852156614861664
fdmus_b14_1411422642598642
fdmus_b14_210467637611609
fdmus_b15_291587231252253
fdmus_b15_294762224208218
fdmus_b15_304468143124144
fdmus_b15_4211398581689673
fdmus_b15_4632764787823
fdmus_b17_1037359333823622356
fdmus_b17_1324473228290229
fdmus_b17_14562766746750
fdmus_b17_4201082738664673
fdmus_b20_1411677071
fdmus_b20_1711747474
fdmus_b20_238952222219236
fdmus_b20_3415424156214961623
fdmus_b20_3493141157149
fdmus_b20_3813162170158
fdmus_b20_4923043352375322
fdmus_b20_4983091552510518
fdmus_b21_1111555760
fdmus_b21_1121535253
fdmus_b21_16724153151148
fdmus_b21_4812343224152175
fdmus_b21_961837715710738
fdmus_b22_1024136135133
fdmus_b22_1131454749
fdmus_b22_133259226223229
fdmus_b22_1721888986
fdmus_b22_241898145136142
fdmus_b22_3561635862
fdmus_b22_4883426428390476
fdmus_b22_6001626269
fdmus_b22_6621817675
), ArticleFig(id=1327010743976833166, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, language=CN, label=表3, caption=

2 h时间限制下各算法枚举的MUS个数对比结果

, figureFileSmall=null, figureFileBig=null, tableContent=
测试用例本文算法MARCO+[18]MARCO-
MAM[19]
MARCO-
ABC[20]
注:黑体数值表示MUS枚举个数的最优结果.
fdmus_b14_1342852156614861664
fdmus_b14_1411422642598642
fdmus_b14_210467637611609
fdmus_b15_291587231252253
fdmus_b15_294762224208218
fdmus_b15_304468143124144
fdmus_b15_4211398581689673
fdmus_b15_4632764787823
fdmus_b17_1037359333823622356
fdmus_b17_1324473228290229
fdmus_b17_14562766746750
fdmus_b17_4201082738664673
fdmus_b20_1411677071
fdmus_b20_1711747474
fdmus_b20_238952222219236
fdmus_b20_3415424156214961623
fdmus_b20_3493141157149
fdmus_b20_3813162170158
fdmus_b20_4923043352375322
fdmus_b20_4983091552510518
fdmus_b21_1111555760
fdmus_b21_1121535253
fdmus_b21_16724153151148
fdmus_b21_4812343224152175
fdmus_b21_961837715710738
fdmus_b22_1024136135133
fdmus_b22_1131454749
fdmus_b22_133259226223229
fdmus_b22_1721888986
fdmus_b22_241898145136142
fdmus_b22_3561635862
fdmus_b22_4883426428390476
fdmus_b22_6001626269
fdmus_b22_6621817675
)], attaches=null, journal=Journal(id=1324759606947315908, delFlag=0, nameCn=计算机研究与发展, nameEn=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, issn=1000-1239, eissn=null, cn=11-1777/TP, coden=null, periodic=0, language=CN, oaType=null, ccby=null, superviseOffice=null, ownerOffice=null, pubOffice=null, editorOffice=null, officeType=null, aims=null, clcCode=null, officeProv=null, officeCity=null, officeAddr=null, officeZip=null, officeEmail=null, officePhone=null, editDirector=null, officeDirector=null, officeDirectorPhone=null, officeStaffNum=null, officeEmpNum=null, coverPicUrl=k2l8zgqwstuxxevFX2qxVA==, journalPrice=null, startedYear=null, abbrevIsoEn=Journal of Computer Research and Development, journalRemark=null, publicationField=null, createdTime=1793776903141, updatedTime=1793850698612, createdBy=18614031015, updatedBy=13701087609, firstLetterCn=J, firstLetterEn=J, subjectCode=Electronic Information, subjectName=null, subjectCodeEn=Electronic Information, subjectNameEn=null, picCn=k2l8zgqwstuxxevFX2qxVA==, picEn=r6k0Ry+RD+c/VXj5QarmDw==, jcr=null, cjcr=null, exts=[JournalExt(id=1325069127710286688, language=CN, name=计算机研究与发展, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698640, updatedTime=1793850698640, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""}), JournalExt(id=1325069127777395553, language=EN, name=Journal of Computer Research and Development, nameHistory1=null, nameHistory2=null, managedBy=, sponsoredBy=, publishedBy=, editorOffice=, officeProv=null, officeCity=null, officeAddr=, officeZip=, editDirector=, officeDirector=null, officePhone=null, coverPicUrl=null, journalRemark=, submitArticleUrl=null, websiteUrl=, createdTime=1793850698656, updatedTime=1793850698656, createdBy=13701087609, updatedBy=13701087609, submissionGuidelinesUrl=, submissionAuthorUrl=https://crad.ict.ac.cn/journalx/authorLogOn.action, submissionEditorUrl=https://crad.ict.ac.cn/journalx/editorLogOn.action, submissionReviewUrl=https://crad.ict.ac.cn/journalx/expertLogOn.action, submissionCeEditorUrl=https://crad.ict.ac.cn/journalx/editorInChiefLogOn.action, submissionAeEditorUrl=, option={"copyright":""})], databaseList=null, tenantJournalId=1324759914146529478, websiteList=[Website(id=1325070300139892771, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN, language=CN, createTime=1793850978169, createBy=18614031015, updateTime=1793851040259, updateBy=18614031015, name=计算机研究与发展-中文, tplId=1146099689490845704, title=计算机研究与发展, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070893751349360, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=articleTextType, value=kx, createTime=1793851119697, updateTime=1793851119697, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893730377837, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=banner, value=null, createTime=1793851119692, updateTime=1793851119692, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893772320883, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=grayFlag, value=0, createTime=1793851119702, updateTime=1793851119702, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893721989228, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851119690, updateTime=1793851119690, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893784903797, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=minRunFlag, value=0, createTime=1793851119705, updateTime=1793851119705, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893742960751, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/file/pic, createTime=1793851119695, updateTime=1793851119695, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893780709492, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=silenceFlag, value=0, createTime=1793851119704, updateTime=1793851119704, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893738766446, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_cn_619/, createTime=1793851119694, updateTime=1793851119694, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893755543665, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeColor, value=null, createTime=1793851119698, updateTime=1793851119698, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070893763932274, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300139892771, code=themeStyle, value=null, createTime=1793851119700, updateTime=1793851119700, creator=18614031015, updator=18614031015)]), Website(id=1325070300580294698, webName=null, webTitle=null, webDomain=null, webCopyrigh=null, webIpcNo=null, seoTitle=null, seoKeywords=null, seoDescription=null, tenantJournalId=null, journalId=1324759914146529478, journalNameCn=null, journalNameEn=null, grayFlag=null, tenantId=1146029695717560320, platformId=null, journalGroupId=null, journalGroupNameCn=null, journalGroupNameEn=null, type=1, domain=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN, language=EN, createTime=1793850978274, createBy=18614031015, updateTime=1793851036638, updateBy=18614031015, name=计算机研究与发展-英文, tplId=1146101810881728533, title=Journal of Computer Research and Development, delFlag=0, indexPage=/home, props=[WebsiteProps(id=1325070925288321148, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=articleTextType, value=kx, createTime=1793851127216, updateTime=1793851127216, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925263155321, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=banner, value=null, createTime=1793851127210, updateTime=1793851127210, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925309292671, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=grayFlag, value=0, createTime=1793851127221, updateTime=1793851127221, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925254766712, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=logo, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic?fileId=U27tDsy717YF7XSPA+Vwdw==, createTime=1793851127208, updateTime=1793851127208, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925326069889, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=minRunFlag, value=0, createTime=1793851127225, updateTime=1793851127225, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925279932539, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=picServerUrl, value=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/file/pic, createTime=1793851127214, updateTime=1793851127214, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925317681280, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=silenceFlag, value=0, createTime=1793851127223, updateTime=1793851127223, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925271543930, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=staticResourcePath, value=https://castjournals.cast.org.cn/joweb/cast_kjdb_en_623/, createTime=1793851127212, updateTime=1793851127212, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925292515453, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeColor, value=null, createTime=1793851127217, updateTime=1793851127217, creator=18614031015, updator=18614031015), WebsiteProps(id=1325070925300904062, tenantId=1146029695717560320, journalId=null, journalGroupId=null, siteId=1325070300580294698, code=themeStyle, value=null, createTime=1793851127219, updateTime=1793851127219, creator=18614031015, updator=18614031015)])], journalTitle=计算机研究与发展, weixinUrl=null, journalUrl=https://crad.ict.ac.cn/, iacademicId=null, status=1, seqNo=null, journalTitleEn=Journal of Computer Research and Development, journalPhotoCn=k2l8zgqwstuxxevFX2qxVA==, journalPhotoEn=r6k0Ry+RD+c/VXj5QarmDw==, journalFirstLetter=J, journalRecommend=null, journalNew=null, journalCollection=null, jcrJf=null, cjcrJf=null, jcrJfStr=null, cjcrJfStr=null, submissionFirstDecision=null, sciSubjectClassification=null, casSubjectClassification=null, citeScore=null, totalCitationFrequency=null, icpCode=null, psCode=null, advertisingLicenseCode=null, copyrightInformation=null, country=null, option=, provinceCode=null, provinceName=null, collectFlag=false, interPubPlatform=, interPubPlatformUrl=null), detailUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202440326, detailUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/10.7544/issn1000-1239.202440326, pdfUrlCn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/PDF/10.7544/issn1000-1239.202440326, pdfUrlEn=https://castjournals.cast.org.cn/joweb/jsjyjyfz/EN/PDF/10.7544/issn1000-1239.202440326, aliStartDate=0, aliEndDate=0, collectionFlag=false, citedCount=null, citedUrl=null, previewStatus=0, delFlag=0, hasFullText=1, orderTime=1746028800000, fullTextJson=null, articleText=null, reference=null)
收藏切换
基于增量信息交互的极小不可满足子集求解算法
蒋璐宇 , 欧阳丹彤 , 张奇 , 太然 , 张立明 *
计算机研究与发展 | 人工智能 2025,62(5): 1226-1234
收起
收藏切换
计算机研究与发展 |人工智能 2025 , 62 (5) : 1226 -1234
基于增量信息交互的极小不可满足子集求解算法
全屏
[Author(id=1327010739082080357, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=0, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=jiangluyu1998@163.com, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739136606310, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739082080357, language=EN, stringName=Luyu Jiang, firstName=Luyu, middleName=null, lastName=Jiang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739207909479, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739082080357, language=CN, stringName=蒋璐宇, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"GpNg/Pg3cVLjz+Op3l8zYQ==","content":"

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题、组合优化问题、基于模型的诊断问题

"}, bioImg=GpNg/Pg3cVLjz+Op3l8zYQ==, bioContent=

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题、组合优化问题、基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739279212649, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=1, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=ouyd@jlu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739379875946, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739279212649, language=EN, stringName=Dantong Ouyang, firstName=Dantong, middleName=null, lastName=Ouyang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

"}, bioImg=null, bioContent=

born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739459567723, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739279212649, language=CN, stringName=欧阳丹彤, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"7bLggtRfWc81/92mtF+HLw==","content":"

1968年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为自动推理、基于模型的诊断问题

"}, bioImg=7bLggtRfWc81/92mtF+HLw==, bioContent=

1968年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为自动推理、基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739514093677, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=2, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739581202542, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739514093677, language=EN, stringName=Qi Zhang, firstName=Qi, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739652505711, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739514093677, language=CN, stringName=张奇, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"m/Fq2UFWUDuoz2occI3Ofg==","content":"

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题和基于模型的诊断问题

"}, bioImg=m/Fq2UFWUDuoz2occI3Ofg==, bioContent=

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题和基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739765751921, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=3, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=null, emailSecond=null, emailThird=null, correspondingAuthor=0, authorType=1, ext={EN=AuthorExt(id=1327010739832860786, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739765751921, language=EN, stringName=Ran Tai, firstName=Ran, middleName=null, lastName=Tai, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"content":"

born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010739899969651, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739765751921, language=CN, stringName=太然, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=null, address=null, bio={"img":"8wzuuJL3O2VJ4AR14cX5fg==","content":"

1997年生. 博士研究生. CCF学生会员. 主要研究方向为组合优化、基于模型的诊断问题

"}, bioImg=8wzuuJL3O2VJ4AR14cX5fg==, bioContent=

1997年生. 博士研究生. CCF学生会员. 主要研究方向为组合优化、基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null), Author(id=1327010739962884213, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, orderNo=4, firstName=null, middleName=null, lastName=null, nameCn=null, orcid=null, stid=null, country=null, authorPic=null, dead=0, email=limingzhang@jlu.edu.cn, emailSecond=null, emailThird=null, correspondingAuthor=1, authorType=1, ext={EN=AuthorExt(id=1327010740013215862, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739962884213, language=EN, stringName=Liming Zhang, firstName=Liming, middleName=null, lastName=Zhang, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"content":"

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

"}, bioImg=null, bioContent=

born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

, aboutCorrespAuthor=null), CN=AuthorExt(id=1327010740063547511, tenantId=1146029695717560320, journalId=1324759914146529478, articleId=1327010734699032651, authorId=1327010739962884213, language=CN, stringName=张立明, firstName=null, middleName=null, lastName=null, prefix=null, suffix=null, authorComment=null, nameInitials=null, affiliation=null, department=null, xref=*, address=null, bio={"img":"p7CovTa+pNlw0WoAHlcsog==","content":"

1980年生. 博士,正高级工程师. CCF高级会员. 主要研究方向为可满足性问题和基于模型的诊断问题

"}, bioImg=p7CovTa+pNlw0WoAHlcsog==, bioContent=

1980年生. 博士,正高级工程师. CCF高级会员. 主要研究方向为可满足性问题和基于模型的诊断问题

, aboutCorrespAuthor=null)}, companyList=null)]
蒋璐宇 , 欧阳丹彤 , 张奇, 太然, 张立明*
作者信息
  • 吉林大学计算机科学与技术学院 长春 130012
  • 符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012
通讯作者:
张立明()
作者简介:

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题、组合优化问题、基于模型的诊断问题

1968年生. 博士,教授,博士生导师. CCF高级会员. 主要研究方向为自动推理、基于模型的诊断问题

1998年生. 博士研究生. CCF学生会员. 主要研究方向为可满足性问题和基于模型的诊断问题

1997年生. 博士研究生. CCF学生会员. 主要研究方向为组合优化、基于模型的诊断问题

1980年生. 博士,正高级工程师. CCF高级会员. 主要研究方向为可满足性问题和基于模型的诊断问题

Incremental Information Interaction-Based Algorithm for Enumerating MUSes
Luyu Jiang , Dantong Ouyang , Qi Zhang, Ran Tai, Liming Zhang*
Affiliations
  • College of Computer Science and Technology, Jilin University, Changchun 130012
  • Key Laboratory of Symbol Computation and Knowledge Engineering (Jilin University), Ministry of Education, Changchun 130012
  • born in 1998. PhD candidate. Student member of CCF. Her main research interests include SAT, combinatorial optimization, and model-based diagnosis problem

    born in 1968. PhD, professor, PhD supervisor. Senior member of CCF. Her main research interests include automatic reasoning and model-based diagnosis problem. ()

    born in 1998. PhD candidate. Student member of CCF. His main research interests include SAT and model-based diagnosis problem

    born in 1997. PhD candidate. Student member of CCF. His main research interests include combinatorial optimization and model-based diagnosis problem

    born in 1980. PhD, senior engineer. Senior member of CCF. His main research interests include SAT and model-based diagnosis problem

出版时间: 2025-05-01 doi: 10.7544/issn1000-1239.202440326
文章导航
收藏切换

极小不可满足子集(minimal unsatisfiable subset,MUS)的求解是理论计算机科学的重要问题. 由于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标准测试用例上的实验验证了所提算法相较于当前先进算法的优越性,在部分测试用例上的结果显示所提算法的枚举效率和枚举获胜个数较已有算法均有显著的提高.

极小不可满足子集  /  极大可满足子集  /  不可行分析  /  碰集  /  对偶性

Enumerating minimal unsatisfiable subsets (MUS) is an important issue in theoretical computer science. Given an unsatisfiable Boolean formula, the number of its MUS is exponentially related to the formula’s scale. Contemporary methods aim to identify MUSes as many as possible within appropriate time limits. Dealing with the huge search space and choosing a suitable node to expand can markedly reduce the time consumption on shrink and grow operations, thereby the algorithm could obtain better performance. We introduce an incremental information interaction-based MUS solving algorithm, denoted as MARCO-MSS4MUS, which utilizes the duality and complementary relationships among MUS, minimal correction set (MCS), and maximal satisfiable subset (MSS). Based on the framework of MARCO algorithm, the proposed algorithm selects a more suitable node to expand via intersection and union information of previously identified MSSes during the search, i.e., the incremental MSS information is employed as a heuristic for node selection to accelerate the enumeration of MUS. This process also benefits in identifying more MSSes, in turn, the incremental MSS information helps select a better node for next exploration, thereby achieving an interaction of incremental information. Two theorems and two corollaries regarding interactive incremental information are proposed and the feasibility of our MARCO-MSS4MUS algorithm is theoretically analyzed. Experiments on standard MUS benchmark instances show the superiority of the proposed algorithm over state-of-the-art algorithms. Both the enumeration efficiency and the number of enumerated wins of the proposed algorithm are significantly improved compared with existing algorithms.

minimal unsatisfiable subset (MUS)  /  maximal satisfiable subset (MSS)  /  infeasibility analysis  /  hitting set  /  duality
蒋璐宇, 欧阳丹彤, 张奇, 太然, 张立明. 基于增量信息交互的极小不可满足子集求解算法. 计算机研究与发展, 2025 , 62 (5) : 1226 -1234 . DOI: 10.7544/issn1000-1239.202440326
Luyu Jiang, Dantong Ouyang, Qi Zhang, Ran Tai, Liming Zhang. Incremental Information Interaction-Based Algorithm for Enumerating MUSes[J]. Journal of Computer Research and Development, 2025 , 62 (5) : 1226 -1234 . DOI: 10.7544/issn1000-1239.202440326
极小不可满足子集(minimal unsatisfiable subset,MUS)的求解是布尔可满足性问题(satisfiability,SAT)[1-4]的重要扩展问题之一. 给定一个布尔逻辑公式,当公式被判定为不可满足时,则需要进一步分析出哪些子句之间起了冲突导致公式不可满足. 而这些“冲突”正是该布尔逻辑公式所对应的MUS. 由于MUS是基于数理逻辑表达的,因此该问题广泛应用于采用逻辑语言描述且含有冲突的系统中,其作用在于定位冲突进而解决冲突,使得系统恢复一致性. 在计算机领域,MUS求解对于电子设计自动化、形式化验证等方向具有重要意义. 例如,在软件工程领域,对一个正在开发的系统进行需求分析时,需要首先将需求使用逻辑语言进行形式化描述,再进行需求的一致性检查,即确保所有需求间具有一致性(可满足)且没有冗余,若检查出不一致(不可满足)或冗余,则最好以最小化的形式向用户展示,以暴露需求中的核心问题,从而对其做出相应的修改使得所有需求可以同时被满足,将需求形式化描述所得公式的MUS就是不一致需求的极小集合;在基于模型的诊断问题[5-7]中,当电路的实际输出与期望输出不一致时,就需要对电路中的组件进行故障诊断,将电路的系统描述、组件和输入输出信息形式化描述为一个不可满足的逻辑公式,对该公式求解其MUS,即对应于电路的极小冲突集,代表电路中存在冲突的组件集合的最小单位,而该公式的极小修正集(minimal correction set,MCS)对应于电路的诊断解,意味着去掉MCS中的组件后电路的输出正常,电路的剩余部分具有一致性. 除此之外,MUS的枚举在很多领域都有广泛的应用,如描述逻辑中的公理定位问题[8-9]、本体中的不一致检测[10-11]、软硬件验证问题[12-13]等.
本文的主要贡献为3个方面:
1)所提算法采用了极大可满足子集(maximal satisfiable subset,MSS)的交集和并集作为启发信息,定义了新的启发式帮助指导选择下一次扩展的节点.
2)提出了2个定理及其推论. 从理论层面分析了增量式求解MSS和MUS的过程中,MSS的交集和并集信息对于枚举MUS的效率提升的可行性.
3)提供多种时间限制下的对比实验,在MUS标准测试用例上的实验结果表明,本文所提算法MARCO-MSS4MUS可以有效利用MSS信息以加速对MUS的枚举过程,在部分用例上的枚举效率有数倍的提升效果.
MUS的枚举算法目前主要分为2类:基于碰集对偶性的方法和基于种子缩减的方法. 第1类方法主要利用了MUS和MCS互为碰集的对偶性特点,以及MSS与MCS互为补集的特点,首先计算出全部的MSS,再求其补集得到全部的MCS,最后对全部的MCS构成的集合簇求碰集得出全部的MUS,代表算法有CAMUS[14-15], DAA[16]. 第2类方法主要依赖对搜索空间的剪枝来识别MUS,代表算法有MARCO[17]及其变体[18-20]、TOME[21]算法、ReMUS[22]算法和UNIMUS[23]算法等. 其中,MARCO算法利用哈斯图结构,每找到一个节点必会将其收缩成一个MUS或扩充成一个MSS,再对搜索空间中的无解空间进行剪枝;TOME算法则将哈斯图结构看作纵向的链式结构,找寻每一条链的可满足节点和不可满足节点的交界处,收集这些节点来识别出真正的MSS和MUS;ReMUS算法则以递归的方式计算当前节点所表示集合的MUS;UNIMUS算法则是在原有搜索空间的基础上定义了一个动态的子搜索空间,使用识别出的MUS的并集的幂集与未探索空间的交集作为新的搜索空间来选择节点进行扩展. 尽管ReMUS和UNIMUS展现出良好的求解效率,但这2种算法致力于极致的MUS枚举,无法识别出任何的MSS. 尽管MSS的计算较MUS更容易,但MSS的枚举同样有着不可替代的意义[24-26]. 因此,本文将继续针对MARCO类算法框架提出新的枚举算法,充分利用搜索过程中识别出的MSS交集和并集等信息作为选择扩展节点的启发信息,辅助算法选择更合适的节点进行扩展,在此过程中利用增量的MSS信息不断优化节点选择,使得MSS和MUS之间的信息进行有效交互,进一步促进MUS的枚举.
本节将首先介绍不可满足的布尔逻辑公式中的3种特殊集合——MUS,MSS,MCS的概念,以及三者之间的对偶和互补关系. 之后介绍在枚举此类集合的算法中普遍采用的对搜索空间的刻画方法.
定义1. MUS[15]. 给定一个不可满足的布尔逻辑公式F,称集合U是F的一个MUS,当且仅当 U $ \subseteq $ F,且U不可满足,$ \forall $ c $ \in $ U,U\{c}可满足.
定义2. MSS[15]. 给定一个不可满足的布尔逻辑公式F,称集合S是F的一个MSS,当且仅当 S $ \subseteq $ F,且S可满足,$ \forall $ c $ \in $ F\S,S $ \cup ${c}不可满足.
定义3. MCS[15]. 给定一个不可满足的布尔逻辑公式F,称集合C是F的一个MCS,当且仅当C $ \subseteq $ F,且F\C可满足,$ \forall $ c $ \in $ C,F\{C\{c}}不可满足.
定义4. 碰集[4]. 称集合H是集合簇Q的碰集,当且仅当H同时满足:$H \subseteq \mathop {\cup}\limits_{{Q' \in Q}} Q' $;对于 $ \forall $Q′ $ \in $ Q ,$H \cap Q' \ne \varnothing $,其中Q′代表集合簇Q中的集合.
定义5. 极小碰集[4]. 称集合簇Q的一个碰集H是极小的,当且仅当H是Q的碰集且H的任意真子集都不是Q的碰集.
从问题定义中可以看出,MSS和MCS的定义是互补的,因此布尔逻辑公式F的每个MSS在F下的补集都是F的一个MCS. 此外,MUS代表了导致公式F不可满足的子句的极小集合,而MCS代表从公式F中去除该部分后不一致性被修复的子句集合,故MCS和MUS都对应着与公式的不可满足性相关的子句集合. 已有文献[27]证明了MUS与MCS之间互为碰集的对偶关系.
针对MUS枚举问题,给定一个含有n个子句的布尔逻辑公式F,其幂集就构成了算法的整个搜索空间,用1个节点表示F的1个子集,那么搜索空间中就有2n个节点. MARCO算法采用子句映射的方式,将每个子句映射为1个新的变量,从而形成1个新的布尔逻辑公式map来刻画搜索空间. 向上剪枝操作BlockUp和向下剪枝操作BlockDown就是向map中添加相应的子句从而对搜索空间进行剪枝. 判断一个节点是否被扩展过只需要对map中该节点所含子句所对应的映射变量赋值后进行可满足性检查. 公式map可被可视化为哈斯图(图示为含有4个子句的布尔逻辑公式F所对应的搜索空间),如图1所示. 可以看出,相比于传统方式存储2n个节点及节点之间的联系,使用逻辑公式map刻画的搜索空间大大减小了内存消耗又保证了搜索效率.
MARCO算法作为MUS枚举问题的经典算法,近年来已有多个改进版本. 经典MARCO算法的具体描述如算法1所示. 首先,将给定的公式进行子句到变量的映射,形成一个新的公式map用于表示搜索空间(行①). 之后开始在搜索空间中寻找MUS,执行一个while循环,当哈斯图中还有未探索的节点时,map为可满足的,循环终止的条件是map不可满足,即搜索空间中所有的节点都已探索过(或已被剪枝)(行②). 在循环中,算法通过调用函数getUnexplored(map)在map中找到一个未探索的节点seed,检查其可满足性. 当seed可满足时,说明seed所表示的集合是公式F的一个可满足子集,于是将seed扩展为一个MSS,并将seed所表示集合的全部子集对应的节点从哈斯图中剪枝;当seed不可满足时,意味着seed所表示的集合是F的一个不可满足子集,于是将seed收缩为一个MUS,并将seed所表示集合的全部超集对应的节点剪枝,重复此过程直到所有节点均被探索或剪枝,算法停止,所有的MUS和MSS被输出.
MARCO的现有变体主要有3种:第1种[18],对算法1的行③进行改进,更改为选择一个极大的未探索节点,这样算法更偏向于先搜索不可满足的seed,且这种方式下找到的seed若可满足则一定是MSS,可以省去Grow操作;第2种[19],对循环中每轮选择的seed个数进行改进,增加一个基数为seed所代表集合一半的子集对应的节点作为第2个seed参与搜索,这样的改进使得算法偏向于中上层的节点优先探索;第3种[20],找到一类特殊的MSS并根据其特性计算出当前可确定的全部MUS的子集,将其对应的节点剪枝,这类改进可以进一步对搜索空间进行剪枝,在一定程度上加速对MUS的枚举效率.
算法1. MARCO算法.
输入:给定的布尔逻辑公式F;
输出:已识别的MSS 集合SMSS和MUS 集合SMUS.
① map←F中子句映射为变量形成的新公式;
② while map可满足do
③  seed←getUnexplored (map);
④ if seed是可满足的
⑤   SMSS←Grow (seed);/*扩充操作*/
⑥  输出SMSS;
⑦   map←map∧BlockDown (seed);
⑧ else /*seed不可满足*/
⑨   SMUS←Shrink (seed);/*收缩操作*/
⑩  输出SMUS;
⑪   map←map∧BlockUp (seed);
⑫ end if
⑬ end while
基于第3节对MARCO已有改进的分析,本文在结合上述改进的基础上提出新的算法MARCO-MSS4MUS. 本节首先介绍所提算法的思想与理论依据,之后给出算法的详细描述.
由于MUS, MSS, MCS这3种集合之间均存在紧密的联系,在算法枚举的过程中可以充分利用MSS的信息来促进MUS的枚举. 具体而言,由于MSS与MCS互为补集,而MCS又与MUS互为碰集,于是可以利用MCS建立起MSS与MUS之间信息传递的桥梁. 基于上述思想,结合增量式求解碰集的特点,给出以下定理、推论及证明过程. 其中,定理1和定理2对应于问题的全部MSS和全部MUS均被找出时的情况,而推论1和推论2则对应于部分MSS和部分MUS被找出时的情况.
定理1. 令集合SIMSS表示所求出的MSS的交集,当全部的MSS被求出时,出现在集合SIMSS中的元素一定不会出现在任何MUS中.
证明. 反证法. 假设存在一个元素a $\in $ SIMSS且出现在MUS集合 U1中. 已知a $\in $ U1,由于MUS与MCS互为极小碰集,根据极小碰集的定义,则必有一个MCS集合 C1,满足a $\in $ C1∩U1,于是一定有a $\in $ C1. 而已知a $\in $ SIMSS,于是对任意的MSS集合 S,都有a $\in $ S,根据MSS与MCS互补的性质,对任意的MCS集合 C,都有a $ \notin $ C,与a $\in $ C1相矛盾. 故原假设不成立,不存在这样的元素a既出现在SIMSS中又出现在某一MUS中. 证毕.
推论1. 令集合SIMSS表示所求出的MSS的交集,在增量式得到MSS的过程中,当前集合SIMSS中的元素一定不会出现在部分MUS中.
证明. 反证法. 类似地,假设存在一个元素a $\in $ SIMSS且a出现在全部MUS中. 根据a $\in $ SIMSS,有a属于当前找到的所有MSS,又由于MSS与MCS互补,有a不属于当前找到的任意MCS. 根据a出现在全部MUS中及MUS与MCS互为极小碰集的关系,有{a}必是一个MCS,与前面根据a $\in $ SIMSS的条件推断出a不属于当前找到的任意MCS的结论相矛盾,故原假设不成立. 证毕.
定理2. 令集合SUMSS表示所求出的MSS的并集,令集合SCoUMSS为SUMSS的补集. 当全部的MSS被求出时,对任意元素u $\in $ SCoUMSS,一定存在一个MUS集合 U满足u $\in $ U.
证明. 对于任意元素u $\in $ SCoUMSS,必有u $ \notin $ SUMSS,于是有u不属于任意MSS集合S. 由于MSS与MCS互为补集,于是有u属于所有MCS集合 C. 由于MCS与MUS互为极小碰集,则根据极小碰集的定义,对任意u $\in $ C,必存在一个MUS集合 U1,满足u $\in $ U1. 证毕.
推论2. 令集合SUMSS表示所求出的MSS的并集,令集合SCoUMSS为SUMSS的补集. 在增量式得到MSS的过程中,当前集合SCoUMSS中的元素一定出现在部分MUS中.
证明. 反证法. 假设存在一个元素a $\in $ SCoUMSS且a不会出现在任何MUS中. 根据a $\in $ SCoUMSS,有a $ \notin $ SUMSS,有a不属于当前找到的任意MSS,又由于MSS与MCS互为补集,有a属于当前找到的全部MCS,又由于MUS与MCS互为极小碰集,根据碰集定义可知,一定存在一个MUS集合 U′ 满足a $\in $ U′ ,与假设中a不会出现在任何MUS中相矛盾. 故假设不成立. 证毕.
基于定理1及其推论1对MSS交集的理论分析以及定理2和其推论2对MSS并集的补集的理论分析,在算法2每轮选择扩展节点seed时,引入一个新的启发式在原本的seed基础上做出相应调整:将seed与MSS的交集即集合SIMSS做差集后,再与MSS的并集的补集即集合SCoUMSS做并集,得到新的扩展节点seed′. 判断新节点是否未被探索过:若未探索,则扩展seed′而非seed;否则,扩展seed. 在实验中发现,如果seed与集合SIMSS直接做差集,得到的seed′节点会过小,位于哈斯图的靠底部位,使得算法将过于偏向对MSS的枚举,于是调整为seed与集合SIMSS的子集做差集,子集选择基数为集合SIMSS基数1/3的任意子集. 引入启发式后的seed′更加符合MUS的特点,从一定程度上减小收缩操作的时间消耗,更快收缩为一个MUS.
算法2是本文所提算法MARCO-MSS4MUS的伪代码描述.
算法2. MARCO-MSS4MUS算法.
输入:给定的布尔逻辑公式F;
输出:已识别的MSS集合 SMSS和MUS集合 SMUS.
① map←F中子句映射为变量形成的新公式;
② while map可满足do
③  seed←getUnexploredMax (map);
④ if seed是可满足的
⑤   SMSS←seed;
⑥  输出SMSS;
⑦   SIMSS←SIMSS ∩ SMSS;
⑧   SUMSS←SUMSS ∪ SMSS;
⑨   map←map∧BlockDown (seed);
⑩  if seed 是关键MSS
⑪    SMCS←co (seed);
⑫    subU←subU∪SMCS;
⑬    map←map∧BlockDown (subU);
⑭  end if
⑮ else /*seed不可满足*/
⑯   seed′ ←seed – sub (SIMSS)∪co (SUMSS);
⑰  if seed′ 未被探索
⑱   if seed′ 可满足
⑲     SMSS←Grow (seed′);
⑳    输出SMSS;
㉑     SIMSS←SIMSS ∩ SMSS;
㉒     SUMSS←SUMSS ∪ SMSS;
㉓     map←map∧BlockDown (seed′);
㉔   else /* seed′ 不可满足*/
㉕     SMUS←Shrink (seed′);
㉖    输出SMUS;
㉗     map←map∧BlockUp (seed′);
㉘   end if
㉙  else /*seed′已被探索*/
㉚    SMUS←Shrink (seed);
㉛   输出SMUS;
㉜    map←map∧BlockUp (seed);
㉝  end if
㉞ end if
㉟ end while
在经典MARCO算法的基础上,行③表示seed节点的选择方式采用的是已有改进中的第1种,即选择极大未探索的seed版本;行⑩~⑭使用的是已有改进中的第3种,找到一类特殊的MSS即关键MSS,由于关键MSS对应的MCS为单元素集合,将关键MSS的补集元素加入集合subU中,并将subU对应的节点剪枝. 其中,co (seed)指seed的补集,sub (seed)指seed的子集. 本文的改进主要体现在:
1)算法每找到一个新的MSS时,更新MSS交集SIMSS和MSS并集SUMSS(行⑦⑧㉑㉒);2)算法找到的待探索节点seed不可满足时,不直接执行下一步收缩操作Shrink (seed),而是通过新的启发式在seed的基础上先与SIMSS的子集作差集,再与SUMSS的补集作并集,得到新的探索节点seed′(行⑯). 若seed′已探索,则还是选择seed来探索;否则,使用seed′代替seed作为探索节点. MARCO-MSS4MUS算法没有改变经典MARCO算法及其变体的剪枝方式,而是进一步利用了搜索过程中获取的MSS信息来改进所选择的探索节点,从减少收缩和扩充操作的执行时间的角度加速了MUS的枚举效率.
本节将所提出的新算法MARCO-MSS4MUS与当前最先进的算法MARCO+1, MARCO-MAM②,MARCO-ABC2进行对比. 实验设备为一台60 GB RAM、Intel Xeon E5-2690v4 2.6 GHz的CPU、64位Ubuntu 18.04版本Linux操作系统的主机. 算法所用的编程语言均为Python 3.7版本,可满足性检查过程调用的MiniSAT求解器[28]为C++语言编写. 采用标准测试用例SAT11中的MUS实例3对算法进行测试,并对每组实验设置了3种时间限制,分别为0.5 h, 1 h, 2 h.
表1、表2、表3分别对应0.5 h, 1 h, 2 h时间限制下各个算法所枚举出的MUS个数的对比结果.实验结果显示,在算法执行的前期,所提算法枚举MUS的效率在部分实例上并没有已有的先进算法表现好,但随着运行时间的增加,所提算法对MUS的枚举效率出现了显著的提升,在大部分实例上的结果远远优于对比算法. 这样的现象应用本文的理论分析也是可解释的:由于算法是基于极大化版本的MARCO算法,因此在搜索初期,算法优先从哈斯图的顶层选择节点来扩展,因此在算法初期找到的MSS往往偏大,这就使得MSS的交集可能偏大,MSS的并集也偏大,MSS并集的补集则偏小. 于是,所提算法的启发式即在原先选择的待探索节点基础上先与MSS交集做差集,再与MSS并集的补集做并集得到新的待扩展节点就会偏小,使得算法在初期更倾向于对MSS的枚举,当算法找到的MSS数量逐渐增加后,结合其交集和并集得到的启发式的信息才会更偏向于MUS,此时,算法将大量搜索出MUS,这也与本文的实验结果相吻合. 综上,本文所提算法的特点是在搜索初期会更偏向于搜索MSS,在搜索到的MSS逐渐积累后,算法对MUS的枚举效率会呈现显著提升.
为更清晰地可视化实验结果,对表1、表2、表3的结果分别计算获胜个数并绘制成柱状图,如图2所示. 每个算法在每种时间限制下的获胜个数即在各个测试用例下,若该算法枚举MUS个数最多则记为获胜1次,统计所有测试用例下的总获胜次数. 从图2可以看出,所提算法MARCO-MSS4MUS的获胜个数仅在0.5 h的时间限制下没有超过对比算法MARCO-ABC,但在1 h和2 h的时间限制下的实验结果中,MARCO-MSS4MUS的获胜个数均优于其他对比算法. 这也印证了在前文中的分析,MARCO-MSS4MUS算法的启发式引导它在搜索的前期更偏向于收集更多的MSS,从而导致MUS的枚举个数极少,但在其收集到足够多的MSS后,充分利用已有MSS的信息将引导算法逐渐偏向于搜索MUS,使得算法枚举MUS的效率呈现出显著的增长.
本文提出了一种针对MUS枚举问题的新算法MARCO-MSS4MUS. 基于经典MARCO框架及已有改进,在增量式求解MUS和MSS的过程中,进一步利用了搜索过程中枚举出的MSS的交集和并集作为启发式信息,指导算法对于待扩展节点的选择,从而引导搜索逐渐朝着偏向MUS的方向进行,减少收缩和扩充操作的耗时以达到加速MUS枚举的目的. 提出2个新的定理及其推论为MARCO-MSS4MUS的有效性提供了理论依据,从理论角度说明了在MSS交集中的元素不一定出现在MUS中,在MSS并集的补集中的元素一定出现在部分MUS中,因此基于以上信息对待扩展节点进行相应的集合运算操作得到新的待扩展节点将更倾向于找到一个MUS. 最后,标准测试用例的实验表明,MARCO-MSS4MUS在枚举获胜个数和枚举效率2方面均较已有算法有显著的提高.
作者贡献声明:蒋璐宇提出了算法思路和实验方案,负责代码编写、撰写并修改论文;欧阳丹彤确定选题及指导论文写作;张奇负责文献资料的查阅和整理;太然负责整理实验数据;张立明负责对论文提出修改意见.

参考文献 引证文献
排序方式:
1
Cai Shaowei, Zhang Xindi. Deep cooperation of CDCL and local search for SAT[C]//Proc of the 24th Int Conf on Theory and Applications of Satisfiability Testing. Berlin: Springer, 2021: 64−81
2
Cai Shaowei, Zhang Xindi, Fleury M, et al. Better decision heuristics in CDCL through local search and target phases[J]. Journal of Artificial Intelligence Research, 2022, 74: 1515−1563
3
Zheng Jiongzhi, He Kun, Zhou Jianrong, et al. BandMaxSAT: A local search MaxSAT solver with multi-armed bandit[C]//Proc of the 31st Int Joint Conf on Artificial Intelligence. Freiburg: IJCAI, 2022: 1901–1907
4
王荣全,欧阳丹彤,王艺源,等. 结合DOEC极小化策略的SAT求解极小碰集方法[J],计算机研究与发展,2018,55(6):1273–1281
Wang Rongquan, Ouyang Dantong, Wang Yiyuan, et al. Solving minimal hitting sets method with SAT based on DOEC minimization[J]. Journal of Computer Research and Development, 2018, 55(6): 1273–1281 (in Chinese)
5
Metodi A, Stern R, Kalech M, et al. A novel SAT-based approach to model based diagnosis[J]. Journal of Artificial Intelligence Research, 2014, 51: 377−411
6
田乃予,欧阳丹彤,刘梦,等. 基于子集一致性检测的诊断解极小性判定方法[J],计算机研究与发展,2019,56(7):1396–1407
Tian Naiyu, Ouyang Dantong, Liu Meng, et al. A method of minimality-checking of diagnosis based on subset consistency detection[J]. Journal of Computer Research and Development, 2019, 56(7): 1396–1407 (in Chinese)
7
Zhou Huisi, Ouyang Dantong, Zhao Xiangfu, et al. Two compacted models for efficient model-based diagnosis[C]//Proc of the 36th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2022: 3885–3893
8
Ouyang Dantong, Liao Mengting, Ye Yuxin. Lightweight axiom pinpointing via replicated driver and customized SAT-solving[J]. Frontiers of Computer Science, 2023, 17(2): 172315
9
Arif M F, Mencía C, Marques-Silva J. Efficient MUS enumeration of Horn formulae with applications to axiom pinpointing[C]//Proc of the 18th Int Conf on Theory and Applications of Satisfiability Testing. Berlin: Springer, 2015: 324–342
10
Hunter A, Konieczny S. On the measure of conflicts: Shapley inconsistency values[J]. Artificial Intelligence, 2010, 174(14): 1007−1026
11
Xiao Guohui, Ma Yue. Inconsistency measurement based on variables in minimal unsatisfiable subsets[C]//Proc of the 20th European Conf on Artificial Intelligence. Ohmsha: IOS, 2012: 864–869
12
Shazli S Z, Tahoori M B. Using Boolean satisfiability for computing soft error rates in early design stages[J]. Microelectronics Reliability, 2010, 50(1): 149−159
13
Andraus Z, Liffiton M, Sakallah K. Reveal: A formal verification tool for Verilog designs[C]//Proc of the 15th Int Conf on Logic for Programming Artificial Intelligence and Reasoning. Berlin: Springer, 2008: 343–352
14
Liffiton M, Sakallah K. On finding all minimally unsatisfiable subformulas[G]//LNCS 3569: Proc of the 8th Int Conf on Theory & Applications of Satisfiability Testing. Berlin: Springer, 2005: 173–186
15
Liffiton M, Sakallah K. Algorithms for computing minimal unsatisfiable subsets of constraints[J]. Journal of Automated Reasoning, 2008, 40(1): 1−33
16
Bailey J, Stuckey P. Discovery of minimal unsatisfiable subsets of constraints using hitting set dualization[C]//Proc of the 7th Int Workshop on Practical Aspects of Declarative Languages. Berlin: Springer, 2005: 174–186
17
Liffiton M, Malik A. Enumerating infeasibility: Finding multiple MUSes quickly[C]//Proc of the 10th Int Conf on AI and OR Techniques in Constriant Programming for Combinatorial Optimization Problems. Berlin: Springer, 2013: 160–175
18
Liffiton M, Previti A, Malik A, et al. Fast, flexible MUS enumeration[J]. Constraints, 2016, 21(2): 223−250
19
欧阳丹彤,高菡,田乃予,等. 基于双模型的MUS求解方法[J],计算机研究与发展,2019,56(12):2623−2631
Ouyang Dantong, Gao Han, Tian Naiyu, et al. MUS enumeration based on double-model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623–2631 (in Chinese)
20
蒋璐宇,欧阳丹彤,董博文,等. 针对MUS求解问题的加强剪枝策略[J],软件学报,2024,35(4):1964−1979
Jiang Luyu, Ouyang Dantong, Dong Bowen, et al. Enhanced pruning scheme for enumerating MUS[J]. Journal of Software, 2024, 35(4): 1964−1979 (in Chinese)
21
Bendík J, Benes N, Cerna I, et al. Tunable online MUS/MSS enumeration[G]//LIPIcs 65: Proc of the 36th IARCS Annual Conf on Foundations of Software Technology and Theoretical Computer Science. Dagstuhl, Germany: Schloss Dagstuhl--Leibniz-Zentrum für Informatik, 2016: 50: 1–50: 13
22
Bendík J, Cerna I, Benes N. Recursive online enumeration of all minimal unsatisfiable subsets[G]//LNCS 11138: Proc of the 16th Int Symp on Automated Technology for Verification and Analysis. Berlin: Springer, 2018: 143–159
23
Bendík J, Cerna I. Replication-guided enumeration of minimal unsatisfiable subsets[C]//Proc of the 26th Int Conf on Principles and Practice of Constraint Programming. Berlin: Springer, 2020: 37–54
24
Bendík J, Cerna I. Rotation based MSS/MCS enumeration[C]//Proc of the 23rd Int Conf on Logic for Programming, Artificial Intelligence and Reasoning. Stockport, UK: EasyChair, 2020: 120–137
25
Bendík J, Meel K. Counting maximal satisfiable subsets[C]//Proc of the 35th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2021: 3651–3660
26
Bendík J. On decomposition of maximal satisfiable subsets[C]//Proc of the 21st Conf on Formal Methods in Computer Aided Design. Piscataway, NJ: IEEE, 2021: 212−221
27
Previti A, Marques-Silva J. Partial MUS enumeration[C]//Proc of the 27th AAAI Conf on Artificial Intelligence. Palo Alto, CA: AAAI, 2013: 818–825
28
Een N, Sorensson N. An extensible SAT-solver[G]//LNCS 2919: Proc of the 6th Int Conf on Theory and Applications of Satisfiability Testing. Berlin: Springer, 2004: 502–518
2025年第62卷第5期
115
50
0
引用本文
BibTeX
文章信息
doi: 10.7544/issn1000-1239.202440326
  • 接收时间:2024-05-21
  • 首发时间:2026-11-10
  • 出版时间:2025-05-01
补充材料
相关文章
文章信息
作者
出版历史
  • 收稿日期:2024-05-21
  • 修回日期:2024-09-29
  • 录用日期:2024-10-15
基金
作者信息
    吉林大学计算机科学与技术学院 长春 130012
    符号计算与知识工程教育部重点实验室(吉林大学) 长春 130012

通讯作者:

张立明()
参考文献
分享链接
https://castjournals.cast.org.cn/joweb/jsjyjyfz/CN/10.7544/issn1000-1239.202440326
分享至
全文二维码

扫描看全文

引用本文
BibTeX
本文的引用情况
2种不同金属材料的力学参数
科
Family
属数
Number of
genus
种数
Number of
species
占总种数比例
Percentage of
total species (%)
属
Genus
种数
Number of
species
占总种数比例
Percentage of total
species (%)
鹅膏菌科Amanitaceae 2 11 5.26 鹅膏菌属 Amanita 10 4.78
小菇科 Mycenaceae 2 12 5.74 丝盖伞属 Inocybe 5 2.39
多孔菌科 Polyporaceae 8 14 6.70 蜡蘑属 Laccaria 5 2.39
红菇科 Russulaceae 3 23 11.00 小皮伞属 Marasmius 6 2.87
小菇属 Mycena 11 5.26
光柄菇属 Pluteus 5 2.39
红菇属 Russula 17 8.13
栓菌属 Trametes 5 2.39
关闭全屏