可满足性问题(Satisfiability Problem,简称SAT Problem)是众多NP完全问题的“种子”,它是一类问题的难度标准,很多NP完全问题最终都可以转化为可满足性问题的求解。参数化的可满足性问题是重要的NP难问题,人们对其各类约束子问题包括参数化MAX-SAT问题做了大量的研究,并对一直被列为开放性难题的参数化Almost2-SAT问题(简称2-ASAT)提出了固定参数可解(Fixed ParameterizedTractable,简称FPT)的参数算法。本文首先对可满足性问题及其各类约束子问题的主要算法进行综述以对算法利用的主要技术和研究现状有一个系统的了解。最近提出的参数化2-ASAT问题的固定参数可解算法证明了该问题是FPT的,算法主要运用迭代压缩和分支技术进行求解。本文通过对给定的2-CNF表达式F中同一路由上的相邻子句进行组合分析,细化分支处理,对参数化的带单个字符的2-ASAT问题(2-ASLASAT问题)提出了一个运行时间为O~*(5~k)的确定型参数算法,从而可用于参数化Almost 2-SAT问题的求解。参数化的具有完美匹配的图上的点覆盖问题(简称VC-PM问题)和参数化Almost 2-SAT问题是FPT等价的。本文通过分析给定图G中的完美匹配和点覆盖集的关系将问题转化为求解图G的一个至多包含k个匹配点对的点覆盖,提出了一个确定型参数算法,且当k=0时,如果图G存在一个大小等于|G|/2的点覆盖,本文给出了一个多项式时间的求解算法。本文最后对参数化Almost 2-SAT问题和参数化VC-PM问题算法的研究工作进行了总结,并阐述了将来对该问题进一步研究的一些工作。