| 基于扩展失败文字检测的MaxSAT完备算法 |
| |
| 引用本文： | 刘燕丽,朱文杰,张婷. 基于扩展失败文字检测的MaxSAT完备算法[J]. 计算机工程与设计, 2015, 0(3): 669-673 |
| |
| 作者姓名： | 刘燕丽 朱文杰 张婷 |
| |
| 作者单位： | 武汉科技大学理学院,湖北武汉,430081 |
| |
| 基金项目： | 国家自然科学基金项目(51306133) |
| |
| 摘 要： | 为提高MaxSAT完备算法剪枝率和运算效率，分析失败文字检测寻找冲突集的过程，提出扩展失败文字检测方法。通过延长失败文字搜索冲突的路径，形成搜索1步、2步和任意步的递进失败文字检测方式，实现改进的MaxsatzEF算法。实验测试了MaxSAT国际竞赛4个类别的500多个算例，实验结果表明，递进失败文字检测方法找到了更多独立冲突集，可有效提高算法的下界，大幅缩短复杂算例的运行时间。
|
| 关 键 词： | NP难问题 可满足性问题 最大可满足性问题 分支限界 失败文字检测 |
MaxSAT complete algorithm based on extended failed literal detection |
| |
| LIU Yan-li , ZHU Wen-jie , ZHANG Ting. MaxSAT complete algorithm based on extended failed literal detection[J]. Computer Engineering and Design, 2015, 0(3): 669-673 |
| |
| Authors: | LIU Yan-li ZHU Wen-jie ZHANG Ting |
| |
| Affiliation: | LIU Yan-li;ZHU Wen-jie;ZHANG Ting;Department of Science,Wuhan University of Science and Technology; |
| |
| Abstract: | |
| |
| Keywords: | NP complete problem satisfiability problem maximum satisfiability problem branch and bounds failed literal de-tection |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
