参数化可满足性题的研究.pdf

摘要 Problem，简称SATProblem)是众 可满足性问题(Satisfiability 多NP完全问题的“种子’’，它是一类问题的难度标准，很多NP完全 问题最终都可以转化为可满足性问题的求解。参数化的可满足性问题 是重要的NP难问题，人们对其各类约束子问题包括参数化MAX—SAT 问题做了大量的研究，并对一直被列为开放性难题的参数化Almost Parameterized 2．SAT问题(简称2．ASAT)提出了固定参数可解(Fixed Tractable，简称即D的参数算法。 本文首先对可满足性问题及其各类约束子问题的主要算法进行 综述以对算法利用的主要技术和研究现状有一个系统的了解。最近提 出的参数化2-ASAT问题的固定参数可解算法证明了该问题是FPT 的，算法主要运用迭代压缩和分支技术进行求解。本文通过对给定的 2一CNF表达式F中同一路由上的相邻子句进行组合分析，细化分支处 出了一个运行时间为O’(5勺的确定型参数算法，从而可用于参数化 Almost 2．SAT问题的求解。 参数化的具有完美匹配的图上的点覆盖问题(简称VC．PM问题) 和参数化Almost2-SAT问题是即r等价的。本文通过分析给定图G 中的完美匹配和点覆盖集的关系将问题转化为求解图G的一个至多 包含k个匹配点对的点覆盖，提出了一个确定型参数算法，且当k=0 时，如果图G存在一个大小等于ICl／2的点覆盖，本文给出了一个多 项式时间的求解算法。 本文最后对参数化Almost2．SAT问题和参数化VC．PM问题算法 的研究工作进行了总结，并阐述了将来对该问题进一步研究的一些工 作。 关键词Almost2-SAT问题，VC—PM问题，参数化算法 ABSTRACT Satisfiability as afundamentalanda Problem(shortSAT)is problem hardnessstandardofSO can finally manyNP—Completeproblems，which transformedintothesettlementofSAT SAT all has hasformed l(indofNPhard there problem important problem，and in of SAT beenaremarkablelineofresearchthe studyparameterized fixed as tractable(shortFPn problem．Recently,aparameterized for Almost2一SAT as parameterized problem(short2-ASAT) algorithm hasbeen whichhasbeen forseveral proposed open