算法是计算机科学中最核心的内容,自从有计算机以来,它始终是这门学科的研究热点内容。就在计算机科学分支众多的今天,每个分支的基础还是算法的研究。合取范式最大可满足性问题(SA7)是算法中最经典的问题之一,也是最早被证明为NPC的问题。其它问题往往以SAT问题做为参照,通过规约等方法来证明是NP问题。NPC问题的算法复杂性是指数级的,当问题规模达到一定程度时,算法的效率不高,那么就很难在有限的时间里计算出结果,这就需要我们寻找一种快速的方法。局部搜索算法由爬山算法改进而来,在计算量和搜索的规模上都大幅度的减小,使其在NPC这类问题的研究中有了广泛的应用。局部搜索算法也有其局限性,就是把局部最优解做为全局最优解,而问题中往往全局最优解和局部最优解不想等,这就必须对设计出的局部搜索算法进行复杂性分析,分析其近似性能比。在本文中,主要是应用和设计局部搜索算法,分析近似性能比,做出了如下结果：1.列举了Max-SAT问题的几个常见的算法,并给出它们在算法执行中的最差实例,通过实验给出它们的实际表现情况,供读者参考对比分析它们的好坏。2.利用前人的思想,分析一位跳变+全体跳变这个算法解决Max-3-SAT问题,然后以此为基础设计算法来解决Max-4-SAT问题,希望能够将近似比由10/9降低到16/15,并通过实验验证设计出的算法的可行性。3.改变思想,提出了新的局部搜索算法,使其能够解决(?)Max NAE-3-SAT问题,证明其近似比为4/3；发现该算法可以修改应用到Max-k-SAT问题中,并且能够证明近似比为(2k)/(2k-1),并且证明也可以推广到Max-(k)-SAT问题上。