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

关键词：局部搜索 单纯形法 

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