标题:合取范式3可满足问题的局部搜索近似算法
作者:朱大铭;马绍汉;张平平
作者机构:[朱大铭] 山东大学计算机科学技术学院, 济南, 山东 250101, 中国.;[马绍汉] 山东大学计算机科学技术学院, 济南, 山东 250101, 中国.;[张平平] 山东大学计算机科学 更多
通讯作者:Zhu, DM(dmzhu@sdu.edu.cn)
通讯作者地址:[Zhu, D.-M] School of Computer Science and Technology, Shandong University, Jinan 250101, China;
来源:计算机学报
出版年:2010
卷:33
期:7
页码:1127-1139
DOI:10.3724/SP.J.1016.2010.01127
关键词:算法; 复杂性; 近似性能比; 可满足性; 局部搜索
摘要:合取范式最大可满足问题是理论计算机科学的核心问题.局部搜索被许多求解实践证明是解答合取范式最大可满足问题十分有效的方法,但未见关于局部搜索算法解 答该问题性能分析的结果.文中讨论最大3可满足问题(Max-(3)-Sat)的局部搜索算法并分析算法性能.证明Max-(3)-Sat问题的一位跳变 局部搜索算法的近似性能比为4/3;证明一位跳变局部搜索后跟有条件全体跳变算法,解答Max-(3)-Sat问题的近似性能比为5/4.设计一位跳变加 全体跳变的新局部搜索算法,证明新算法解答Max-(3)-Sat问题的近似性能比为8/7.将8/7-近似局部搜索算法推广为解答Max-(k)-Sa t问题的局部搜索算法,证明算法的近似性能比为(2k+2)/(2k+l), k≥4.设计解答 Max-(k)-Sat问题的两位跳变局部搜索算法,证明两位跳变局部搜索算法的近似性能比为1+1/(2k+l+k(k-l)/ (n-k), k≥4.局部搜索算法经多次运行可进一步提高求解性能.文中结果显示,局部搜索算法在合取范式最大可满足问题求解实践中表现出高性能,有其必然性.
收录类别:EI;CSCD;SCOPUS
Scopus被引频次:1
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-77955297832&doi=10.3724%2fSP.J.1016.2010.01127&partnerID=40&md5=60bab517b5c97b0d3cebf0b4592824f2
TOP