• 中国精品科技期刊
  • CCF推荐A类中文期刊
  • 计算领域高质量科技期刊T1类
高级检索

基于双模型的MUS求解方法

欧阳丹彤, 高菡, 田乃予, 刘梦, 张立明

欧阳丹彤, 高菡, 田乃予, 刘梦, 张立明. 基于双模型的MUS求解方法[J]. 计算机研究与发展, 2019, 56(12): 2623-2631. DOI: 10.7544/issn1000-1239.2019.20180852
引用本文: 欧阳丹彤, 高菡, 田乃予, 刘梦, 张立明. 基于双模型的MUS求解方法[J]. 计算机研究与发展, 2019, 56(12): 2623-2631. DOI: 10.7544/issn1000-1239.2019.20180852
Ouyang Dantong, Gao Han, Tian Naiyu, Liu Meng, Zhang Liming. MUS Enumeration Based on Double-Model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623-2631. DOI: 10.7544/issn1000-1239.2019.20180852
Citation: Ouyang Dantong, Gao Han, Tian Naiyu, Liu Meng, Zhang Liming. MUS Enumeration Based on Double-Model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623-2631. DOI: 10.7544/issn1000-1239.2019.20180852
欧阳丹彤, 高菡, 田乃予, 刘梦, 张立明. 基于双模型的MUS求解方法[J]. 计算机研究与发展, 2019, 56(12): 2623-2631. CSTR: 32373.14.issn1000-1239.2019.20180852
引用本文: 欧阳丹彤, 高菡, 田乃予, 刘梦, 张立明. 基于双模型的MUS求解方法[J]. 计算机研究与发展, 2019, 56(12): 2623-2631. CSTR: 32373.14.issn1000-1239.2019.20180852
Ouyang Dantong, Gao Han, Tian Naiyu, Liu Meng, Zhang Liming. MUS Enumeration Based on Double-Model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623-2631. CSTR: 32373.14.issn1000-1239.2019.20180852
Citation: Ouyang Dantong, Gao Han, Tian Naiyu, Liu Meng, Zhang Liming. MUS Enumeration Based on Double-Model[J]. Journal of Computer Research and Development, 2019, 56(12): 2623-2631. CSTR: 32373.14.issn1000-1239.2019.20180852

基于双模型的MUS求解方法

基金项目: 国家自然科学基金项目(61872159,61672261,61502199)
详细信息
  • 中图分类号: TP18

MUS Enumeration Based on Double-Model

  • 摘要: 求解不可满足问题的极小不可满足子集(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方法效率较高,尤其在大规模问题或较大搜索空间时效率提高更为明显.
    Abstract: The MUS (minimal unsatisfiable subset) for solving unsatisfiable problems is an important research direction in the field of artificial intelligence. The MARCO-M method is currently the most efficient way of solving MUS. It uses a single way to enumerate MUS, called maximal-model, without further effective pruning. For the shortcoming of MARCO-M, MARCO-MAM method is proposed which uses maximal-middle model to enumerate MUS. It emphasizes the characteristic that the complexity of solving satisfiable problem is less than the one of solving unsatisfiable problem, that is, solving an MSS is easier than solving an MUS. There are two solutions when using middle-model to improve the efficiency of MUS enumeration, if an MSS(maximal satisfiable subset) is found, the unexplored space of MUS can be pruned by blocking down the MSS. Else, an MUS is found that the times of the unsatisfiable iteration will be reduced. The double-model selects seeds from the top and middle of the hasse diagram, respectively, rather than a single top-down. The maximal model does not effectively use other excellent techniques to reduce the solution space when enumerating MUS. The experimental results show that the MARCO-MAM method is more efficient than the MARCO-M method, especially in large-scale problems or large search spaces.
  • 期刊类型引用(8)

    1. 李晶,贾园园,张磊. MuSig多重签名的实用拜占庭容错共识算法. 计算机应用研究. 2025(02): 352-356 . 百度学术
    2. 时小虎,姚鑫,孙延风,马德印. 基于贡献度和数据有效性检验的共识机制. 东北大学学报(自然科学版). 2024(02): 160-169+178 . 百度学术
    3. 万林. 基于区块链技术的P2P网络分布式数字签名系统设计. 安徽水利水电职业技术学院学报. 2024(03): 43-48 . 百度学术
    4. 唐淑敏,金瑜. 区块链中基于中国剩余定理投票方案的共识机制. 计算机应用. 2023(02): 458-466 . 百度学术
    5. 张宝,田有亮,高胜. 基于博弈论抗共谋攻击的全局随机化共识算法. 网络与信息安全学报. 2022(04): 98-109 . 百度学术
    6. 刘恒飞,张毅. 区块链技术及其应用. 福建电脑. 2021(01): 174-175 . 百度学术
    7. 李杰,李雷孝,孔冬冬. 一种基于中文助记词的椭圆曲线密钥生成方案. 内蒙古工业大学学报(自然科学版). 2020(02): 128-135 . 百度学术
    8. 张彭奕,宋杰. 区块链共识算法效能优化研究进展. 计算机科学. 2020(12): 296-303 . 百度学术

    其他类型引用(9)

计量
  • 文章访问数:  852
  • HTML全文浏览量:  1
  • PDF下载量:  234
  • 被引次数: 17
出版历程
  • 发布日期:  2019-11-30

目录

    /

    返回文章
    返回