MAX-SAT问题一种改进的局部搜索算法

摘要：

局部搜索算法是求解大规模SAT问题的高效算法。经典的局部搜索算法有GSAT、WSAT、TSAT、NSAT等,但这些算法的初始解都是随机产生的.本文提出了用单纯形法产生”初始概率”(每个变量取1的概率),用”初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束,使在局部搜索的开始阶段,满足的子句数大大增加,加快了收敛的速度.通过对不同规模的随机STA问题实例的实验表明,这些改进有效地提高了局部搜索算法求解SAT问题的效率。

关键词： 局部搜索 单纯形法 搜索算法 初始概率 收敛速度

作者: 赵同昇 朱文兴

作者单位: 福州大学数学与计算机科学学院,福建,福州,350002 福州大学离散数学与理论计算机科学研究中心,福建,福州,350002

会议类型: 国内会议

会议名称: 2008年全国理论计算机科学学术年会

会议地点: 西安

会议语种:中文

页码: 50-52,79

在线出版日期: 2008-09-19（万方平台首次上网日期，不代表论文的发表时间）