求解SAT问题的局部搜索算法及其平均时间复杂性分析.docx

求解SAT问题的局部搜索算法及其平均时间复杂性分析
一、SAT问题简介
SAT（Satisfiability）问题是指对于布尔表达式是否存在一组变量值使得表达式成立的问题，是一类典型的NP完全（NP-Complete）问题，该问题的解的判定计算时间复杂性极高，目前还没有找到有效的算法，所以SAT问题一直是理论计算机科学中的一个热点问题。
二、SAT问题的局部搜索算法
1.爬山算法
爬山算法又叫作HillClimbingAlgorithm，是一种常用的基于领域搜索的算法，这种算法是一种贪心算法，每次寻找变化最小的答案，并更新为当前的解，该算法在解空间中单独移动，而不是在解空间中搜索一个大区域。
爬山算法的基本流程如下：
1）首先，根据问题模型，随机生成一个解作为初始解；
2）然后，当前解会去掉当前最优的、相对于当前解更优的解以及当前解对应的领域解；
3）接着，从当前所有解中选择最优的解作为下一个解，直到找到最优解或达到最大的迭代次数为止。
这里所说的领域解是指当前解的一个或多个变量被改变的解。
下面是爬山算法的伪代码：
初始化：S=10；
fori=1toSdo
构造一个随机的赋值X；
令E=sat-problem.evaluate(X);
repeat
构造X的邻居Y;
令ΔE=sat-problem.evaluate(Y)-E；
ifΔE>0then
令X=Y
令E=sat-problem.evaluate(X)
untilΔE≤0;
ifE<best-Ethen
令best-X=X;
令best-E=E
returnbest-E和best-X。
爬山算法常被用来求解最优解或最小值，求解SAT问题也可以利用其进行搜索，对于SAT问题中的一个解，我们可以抽象的理解为这个解的质量。因此，我们可以使用爬山算法在解空间中寻找最优的解。
2.模拟退火算法
模拟退火算法（SimulatedAnnealingAlgorithm）是一种基于概率搜索的算法，其中，搜索策略是被随机约束的策略。始于物理学中的模拟退火过程，该算法可以通过一些基本的概率搜索规则来避免局部极小，从而提高搜索效率。
模拟退火算法的基本原理是，总是寻找最小值，但不局限于在搜索最小值时立即接受更优解，而保留有一定的概率保留某些差解。当接受更劣质解时，接受概率取决于当前阶段和当前解的质量差异以及其他参数。因此，模拟退火算法使用无限小量的随机擦拭和随机跳跃的过程来避免被困在局部最小值中。
下面是模拟退火算法的伪代码：
初始化：X=I；
repeat
fori=1toKdo
构造一个随机的Y邻居
计算Δf=f(Y)-f(X)
ifΔf≤0thenX=Y
else
令r=rand（0，1）
ifr≤exp（-Δf/T）thenX=Y
令T=αT
until系统冷却
其中，K和α是根据问题模型的大小等来确定的。模拟退火算法可以确定最合适的温度，以实现在搜索过程中跳过局部极小的目标，从而实现在解空间中全局性搜索。
3.遗传算法
遗传算法（GeneticAlgorithm）是一种基于进化论的搜索算法，它是以生物进化中遗传机理为基础的一种求解问题的方法，该算法模拟了自然界中的生物进化和遗传过程，通过基因交叉、突变等操作从种群中选出用于产生下一代种群的适应度较高的个体，以期望产生真正的解。
遗传算法的基本思想是，从一开始的随机种群开始，通过交叉、变异等操作不断迭代产生更优秀的个体。在每一次迭代后，从当前的群体中，根据其适应度进行选择性的保留，而将较差的个体替换为新的优秀个体。以此，遗传算法通过不断迭代来寻找解空间中的最优解。
下面是遗传算法的伪代码：
1）初始化：构建一个随机初始种群P;
2）进化：不停的进行以下步骤：
a.应用选择运算选择适应度较高的个体；
b.应用交叉运算，基于父母产生新的种群；
c.应用变异运算，对新种群中的一些个体进行变异；
d.应用评估函数，计算新种群中每一个个体的适应度；
e.如果终止条件达到，那么返回最优解；否则回到2）；
虽然遗传算法的搜索效率较高，但是其时间复杂度也比较高，不适用于处理大型、复杂问题。因此，遗传算法常被用于优化目标比较清晰的问题，在SAT问题的求解中也可以采用遗传算法进行搜索。
三、局部搜索算法的平均时间复杂性
对于局部搜索算法，其时间复杂性会受到问题规模、算法的实现方式、求解目标的特性等因素的影响，因此难以给出统一而可靠的复杂性分析。
在当前常见的算法实现方式中，爬山算法的时间复杂度为O(nm)，其中n是解向量的规模，m是迭代次数；模拟退火算法的时间复杂度为O(kN)或O(kM)，其中k是迭代次数，N是解向量的规模，M是邻域大小；而遗传算法的时间复杂度为O(gN^2m)，其中N是种群规模，m是解向量规模，g是最大迭代次数。
在对这三种局部搜