（计算机应用技术专业论文）参数化可满足性问题的研究.pdf

摘要 可满足性问题( s a t i s f i a b i l i t yp r o b l e m ，简称s a tp r o b l e m ) 是众 多n p 完全问题的“种子，它是一类问题的难度标准，很多n p 完全 问题最终都可以转化为可满足性问题的求解。参数化的可满足性问题 是重要的n p 难问题，人们对其各类约束子问题包括参数化m a x s a t 问题做了大量的研究，并对一直被列为开放性难题的参数化a l m o s t 2 s a t 问题( 简称2 a s a t ) 提出了固定参数可解( f i x e dp a r a m e t e r i z e d t r a c t a b l e ，简称即d 的参数算法。 本文首先对可满足性问题及其各类约束子问题的主要算法进行 综述以对算法利用的主要技术和研究现状有一个系统的了解。最近提 出的参数化2 - a s a t 问题的固定参数可解算法证明了该问题是f p t 的，算法主要运用迭代压缩和分支技术进行求解。本文通过对给定的 2 一c n f 表达式f 中同一路由上的相邻子句进行组合分析，细化分支处 理，对参数化的带单个字符的2 a s a t 问题( 2 a s l a s a t 问题) 提 出了一个运行时间为o ( 5 勺的确定型参数算法，从而可用于参数化 a l m o s t2 s a t 问题的求解。 参数化的具有完美匹配的图上的点覆盖问题( 简称v c p m 问题) 和参数化a l m o s t2 - s a t 问题是即r 等价的。本文通过分析给定图g 中的完美匹配和点覆盖集的关系将问题转化为求解图g 的一个至多 包含k 个匹配点对的点覆盖，提出了一个确定型参数算法，且当k = 0 时，如果图g 存在一个大小等于i c l 2 的点覆盖，本文给出了一个多 项式时间的求解算法。 本文最后对参数化a l m o s t2 s a t 问题和参数化v c p m 问题算法 的研究工作进行了总结，并阐述了将来对该问题进一步研究的一些工 作。 关键词a l m o s t2 - s a t 问题，v c p m 问题，参数化算法 a b s t ra c t s a t i s f i a b i l i t yp r o b l e m ( s h o r ta ss a t ) i saf u n d a m e n t a lp r o b l e ma n da h a r d n e s ss t a n d a r do fs om a n yn p c o m p l e t ep r o b l e m s ，w h i c hc a nf i n a l l y t r a n s f o r m e di n t ot h es e t t l e m e n to fs a tp r o b l e m p a r a m e t e r i z e ds a t p r o b l e mh a sf o r m e da l li m p o r t a n tl ( i n do fn ph a r dp r o b l e m ，a n dt h e r eh a s b e e nar e m a r k a b l el i n eo fr e s e a r c hi nt h es t u d yo fp a r a m e t e r i z e ds a t p r o b l e m r e c e n t l y , af i x e dp a r a m e t e r i z e dt r a c t a b l e ( s h o r ta sf p n a l g o r i t h mf o rp a r a m e t e r i z e da l m o s t2 一s a tp r o b l e m ( s h o r ta s2 - a s a t ) h a sb e e np r o p o s e dw h i c hh a sb e e no p e nf o rs e v e r a ly e a r s i nt h i sp a p e r , as u r v e yo fa l g o r i t h m sf o rs a tp r o b l e ma n di t s c o n s t r a i n e d s u b - p r o b l e m s i s f i r s t l yp r e s e n t e d t oe s t a b l i s ha c o m p r e h e n s i v eu n d e r s t a n d i n go ft e c h n i q u e su s e di nr e l e v a n ta l g o r i t h m s a n dt h er e s e a r c hs i t u a t i o n t e c h n i q u e su s e di nt h ef p ta l g o r i t h mf o r p a r a m e t e r i z e d2 - a s a tp r o b l e ma r ei t e r a t i v ec o m p r e s s i o na n db r a n c h i n t h i sp a p e r , w ea n a l y z et h ec o m b i n a t i o nb r a n c h e so fc o n s e c u t i v ec l a u s e si n aw a l kf o rag i v e n2 - c n ff o r m u l afi no r d e rt or e f i n et h eb r a n c hp r o c e s s ， a n dp r o p o s ead e t e r m i n e dp a r a m e t e r i z e da l g o r i t h mo fr u n n i n gt i m eo ( 5 勺 f o r2 一a s l a s a tp r o b l e m ，w h i c hi su s e f u lf o rt h es o l v e m e n to f p a r a m e t e r i z e d 2 一a s a tp r o b l e m p a r a m e t e r i z e dv e r t e xc o v e ri ng r a p h sw i t hp e r f e c tm a t c h i n g ( s h o r ta s v c p m ) i sf p t - e q u i v a l e n tt op a r a m e t e r i z e d2 一a s a tp r o b l e m w e a n a l y z et h er e l a t i o nb e t w e e nt h ep e r f e c tm a t c h i n ga n dt h ev e r t e xc o v e ri n t h eg r a p h ，t r a n s f o r mt h ep r o b l e mi n t os e a r c h i n gf o rav e r t e xc o v e r c o n t a i n i n ga tm o s tkm a t c h e dp a i r so fv e r t i c e s ，a n dp r o p o s ead e t e r m i n e d p a r a m e t e r i z e da l g o r i t h m f u r t h e r m o r e ，ap o l y n o m i a lt i m ea l g o r i t h mi s p r o p o s e dw h e nk = 0 f i n a l l y , t h i sp a p e rs u m su pt h ew h o l es t u d yw o r ko np a r a m e t e r i z e d 2 - a s a tp r o b l e ma n dp a r a m e t e r i z e dv c - p mp r o b l e ma n dd i s c u s st h e f u r t h e rw o r ko nt h ep r o b l e m s k e yw o r d s2 - a s a tp r o b l e m ，v c - p mp r o b l e m ，p a r a m e t e r i z e d a l g o r i t h m i i 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在在论文中作了明确的说 明。 作者签名：角坪 日期：邀年羔月丑日 关于学位论文使用授权说明 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文，允许学位论文被查阅和借阅；学校可以公布学位 论文的全部或部分内容，可以采用复印、缩印或其它手段保存学位论 文；学校可根据国家或湖南省有关部门规定送交学位论文。 r 、1 日期：2 丑，年月“日 硕士学位论文第一章绪论 第一章绪论 计算复杂性理论发源于二十世纪六十年代，以有多项式时间上界的图灵机为 基本计算模型而奠定了理论基础。在七十年代初，这门学科由于n f 完全问题的 发现而吸引了人们的注意。简单的说，如果一个问题无法在多项式时间内被确定 型图灵机解决，我们称它为难解问题。n i ) 完全问题就是一类直观上难解可是又 找不出方法来证明它们的确难解的计算问题。从数学的角度来说，这和其他有名 的数学问题一样，给予人们一个智力上的重大挑战，而更重要的是，随着信息科 学的发展，在无数与计算有关的学术领域里，n p 完全问题以各种不同形式层出 不穷，越来越多的应用领域里如数据库、管理系统、资源调度网络设计和路由算 法等都提出了许多n f 完全问题，因此设计可能的切实高效的算法来解决这些难 解问题无论是在理论上还是在实际应用中都有很重要的实际意义。 人们在七十年代开始对n f 完全问题的研究主要是横向发展，也就是以不同 的计算模型来分析难解问题的本质。这些新的计算模型包括平行计算模型、概率 计算模型、线路、判断树、平均复杂性、交互证明系统以及程式长度复杂性等等。 八十年代中期，对n f 完全问题的研究有了纵向的突破，发现了许多表面开来并 不相关的计算模型之间的刻划关系，从而解决了几个困扰多年的未解问题，并刺 激了其他领域的发展。 一般的计算机问题通常都存在有效的求解算法使得问题在计算机可以接受 的多项式时间和空间内解决。而对于n f 完全或n f 难问题，当问题的输入规模 不断增大时，求解算法的时间复杂度往往是以指数级增长，最终超出实际需求所 能接受的极限。为了获得快速高效的可行算法，研究人员从很多角度对算法的设 计进行了研究。参数计算和复杂性理论是理论计算机科学的一个分支，该理论的 基础在于这样一个经验：很多难解计算问题实际上跟一个小范围( 或不大范围) 变化的参数有关。参数计算与复杂性理论【1 】充分利用小参数这一特征，使得许多 理论上难解的计算问题在实际中有可能得到有效解决，成为解决这些难解问题的 一种很有前途的新方法。 本文将具体研究参数化的可满足性问题，这一类问题在硬件测试、人工智能、 计算机视觉等很多领域都有着重要的研究价值。 1 1 课题的研究背景 计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难 硕士学位论文第一章绪论 度的理论【l 】。算法是指完成一个任务所需要的具体步骤和方法。也就是说给定初 始状态或输入数据，经过计算机程序的有限次运算，能够得出所要求或期望的终 止状态或输出数据。作为一个抽象的理论，计算复杂度不是指算法在特定的计算 机上运行时所需的指令执行的时间或存取周期，而是指脱离具体的不同结构的计 算机而抽取出来的内在的复杂度。问题的计算复杂度可以利用求解此问题所需要 计算量的多少进行衡量。如果一个算法，它能在以输入规模为参变量的某个多项 式的时间内给出答案，则称它为多项式时间算法；如果一个算法，它能在以输入 规模为参变量的某个指数的时间内给出答案，则称它为指数时间算法。一般目前 将可以在多项式时间内可以求解的问题看作时易解的问题；将在指数时间内求解 的问题看作是难解的问题。 对于问题的计算复杂性分析一般需要利用某种计算机模型，包括定义该计算 模型中所用到的基本运算，因而人们提出了一个包括现代计算机关键特性的抽象 的计算模型图灵机，来衡量算法的复杂度。图灵机模型是最好理解的：即给 出固定的程式，模型按照程式和输入完全确定性地运行。但为了理解算法和这种 确定型图灵机的能力，人们又发展了许多其它各式各样的图灵机模型。其中最为 有名的是非确定型图灵机。这种计算模型，它在进行计算的时候，会自动选择最 优路径进行计算。通俗地说，它有预测能力。 基于图灵机模型，就引出了p 和n p 的概念和n p 完全理论。n p 完全理论 的主要研究方向是将所有的判定问题从计算复杂性的意义上进行分类以确定合 适的解决算法。大致分为以下几类【2 1 。 p 类问题：确定型图灵机在多项式表达的时间内解决的判定问题( 如果对于 一个问题的任何一个实例，算法只需要回答是和不是，这种问题称为判定问题。) 的集合为p 类问题。 n p 类问题：非确定型图灵机上在多项式时间内解决的判定问题的集合为n p 类问题。 显然，p _ c n p ，但是是否p = n p 仍是数学和计算机科学领域最重要的开放性 难题之一。研究人员普遍假设p n p ，f a c t o r i n g 问题就是n p 、p 中的一个，除此 之外，n p 问题还包括其他很多领域中的不存在多项式时间算法的重要的计算问 题。 n p 完全问题：如果判定问题7 t e n p ，并且对所有其他判定问题x e n p ，都 有多项式变换到顶记为兀冗) ，则称判定问题兀是n p 完全的。n p 完全问题是 n p 问题中“最难”的问题，也是最有可能不可解的问题，也就是说，即使只有一 个n p 问题不属于p ，那么所有的n p 完全问题都不属于p 。 n p 难问题：对于搜索问题兀，如果存在某个n p 完全问题可以多项式时间归 2 硕士学位论文 第一章绪论 约到它，那么称该搜索问题氕是n p 难。n p 难问题意味着，在p # n p 的假设下， 他们是不可能有多项式时间算法的，一旦确定某个问题乃是n p 难的，则表明它 至少与n p 完全问题的难解程度一样，但不一定恰好和n p 完全问题一样难解。 n p 完全性的研究有重要的理论意义。已经证明，只要有一个n p 完全问题属 于p ，则n p 中一切问题都属于p ，即如果有一个问题有多项式时间算法，那么 n p 类中所有问题也有多项式时间算法，就能推出n p = p 。反之，要否证n p = p ， 一个明显的方法，就是到n p 中去找一个不属于p 的问题。可满足性问题作为众多 n p 完全问题的“种子 ，是第一个被证明的n p 完全问题，很多n p 完全问题都 可以归约为s a t 问题的求解，在计算复杂度领域占据举足轻重的地位。 n p 完全性的研究在实践中有重要指导作用。在算法设计和分析过程中，如 果已证明某问题是n p 完全的，这就意味着面临的是一个难于处理的问题。对于 它，要找出一个在计算机上可行的( 即多项式时间的) 算法是十分困难的，甚至 可能根本找不到( 因为很可能有n p p ) 。然而，由于这些难解的计算问题在实际应 用中的重要性，人们提出了很多方法来解决这些难解问题，比如：多项式时间近 似算、法【3 1 、随机算法【4 】和启发式算、法【5 1 。但是没有一个方法能满足所有工业和应 用上的需求。 参数计算和复杂性理论是近来发展起来的理论计算机科学的一个分支【4 】。该 理论目的在于从实践上解决很多理论上难解的计算问题。该理论的基于这样一个 观察：很多难解的计算问题实际上跟一个小范围( 或不大范围) 变化的参数有关。 因此，如果能够充分利用这些小参数，许多理论上的难解问题就可以有效的在实 践上解决。比如，从参数计算与复杂性角度定义我们非常熟悉的一个n p 完全问 题：参数化的最大可满足性( p a r a m e t e r i z e dm a x i m u m s a t i s f i a b i l i wp r o b l e m ，简称 p a r a m e t e r i z e dm a x s a t ) 问题，即给定一个合取范式f 和一个整数k ，旧= m ，判 断是否存在组真值赋值至少满足，中的价子旬。在参数计算与复杂性理论中 j j ( 职嘲) 被看作是一个参数，利用参数k ，人们提出了实际有效的算法。另一方面， 参数计算和复杂性理论还提供了有力技术帮助我们为很多的难解问题寻找到可 靠的计算下界，因此也就解释了为什么一些理论上易解的问题如独立集问题实际 上却难以有效解决。 参数计算与复杂性理论主要研究的问题为判定问题，即只有“是 或者 “否 两种答案的问题。参数问题的定义如下： 定义1 - 1 1 6 j 设q 为一个固定大小的字母表，为非负整数集合，参数问题 q 是q 的一个子集。它的输入实例是一个二元组似d ，非负整数k 称为参 数。 3 硕士学位论文 第一章绪论 q 是一个判定问题，每一个实例只有“是 或“否 两种答案，答案为 “是”的实例称为真实例。 我们说算法彳解决参数问题q ，假如对于q 的每个输入实例“妨，算法 彳能够判断阮妨是否为q 的真实例。如果算法彳的计算复杂度由输入实例 大小m 及参数k 决定，我们称算法么为参数算法。 定义1 2 嘲固定参数可解：假设c 为常数，厂为任意函数，如果有一个算 法能够在j 埂k ) x l c 时间内判断输入实例是否为参数问题q 的真实例，则称q 为固 定参数可解( f i x e d - p a r a m e t e rt r a c t a b l e ，即丁) 。 即r 类包括所有的固定参数可解问题。许多n p 难问题，如顶点覆盖问题等， 都属于用叩类。对于大多数即r 类问题的参数算法，函数厂不会很大( 比如， 尺幼= 矿，d 1 ) 。因此，对于给定的小参数k ，参数算法的运行时间及助k l c 是可 接受的。例如参数化点覆盖问题和有向图反馈集问题( d f v s ) 都是f p t 的。 参数计算和复杂性理论在很多领域都有实际应用，如数据库系统、编程语言、 计算机网络、超大规模集成电路设计、并行分布式计算、生物计算和机器入学等。 所以除了理论上的研究，人们更感兴趣的是参数算法如何能够有效地解决实际的 计算问题，这也是参数计算与复杂性理论所面临的新的挑战。 1 2 课题的研究现状 参数化的a l m o s t2 - s a t 问题( 2 a s a t 问题) 的定义如下：给定一个2 c n f 表达式f ，判定是否可以删除至多k 个子句使得得到的表达式为可满足的? 2 c n f 表达式是一个合取范式，且每个子句包含的字符个数至多为2 个。多年来， a l m o s t2 。s a t 问题是否存在固定参数可解算法一直是参数复杂性领域的开放性 难题。m a h a j a n 和r a m a n 7 在1 9 9 7 年第一次提出a l m o s t2 一s a t 问题问题，之后 在2 0 0 7 年举行的d a g s t u h l 研讨会上f e l l o w s 再一次将其列入开放问题之列。i g o r r a z g o n 和b a r r yo s u l l i v a n 在文献【8 】中证明了a l m o s t2 - s a t 问题为固定参数可 解的，并给出了时间复杂度为0 ( 1 5 hk m 3 ) 的f p t 算法。 2 - a s a t 问题是一个最优化问题，即从给定的2 c n f 表达式中删除最少数目 的子句使得得到的表达式为可满足的。参数化2 - a s a t 问题引入了参数k ，即判 定是否可以从给定表达式中删除至多k 个子句使得所得表达式为可满足的。i g o r r a z g o n 和b a r r y0 s u l l i v a n i s 利用文献【9 】中图的二维划分问题的求解方法将 2 a s a t 问题转化为2 a s l a s a t 问题的求解，其定义如下：给定一个三元组限 厶n 其中f 为一个2 c n f 表达式，三是一个满足，的非矛盾字符集( 即三不同 时包含字符z 和一j ，且令中的字符均赋值为1 ，此时存在一个使得f 为真的赋 4 硕士学位论文 第一章绪论 值方案p ) ，z 为一个字符且，叠厶判定从表达式f 中删除最少数目的子句使得仁 u 日) 满足所得表达式。 具有完美匹配图上的点覆盖问题( v c - p m 问题) 从即r 的意义上来讲等价 于2 a s a t 问题的求解，文献【1 0 】通过分析m a x2 s a t 问题和v c p m 问题的转 化，给出了v c - p m 问题的近似算法，改进了稀疏图上的点覆盖问题的近似算法， 并指出如果v c p m 问题存在一个近似率小于2 的近似算法，那么一般图上的点 覆盖问题同样也存在近似率小于2 的近似算法。 1 3 课题的研究内容 本课题对参数化a l m o s t2 s a t 问题的f p t 算法以及参数化v c p m 问题的 参数算法进行了深入研究。 本文深入研究了可满足性问题及其约束子问题的求解算法，主要对参数化 a l m o s t2 s a t 问题的即r 算法进行了分析，希望通过研究给定的2 c n f 表达式 中位于同一路由上的相邻子句的结构关系，提出一种改进的即r 算法。 本文通过对图中的完美匹配边集和点覆盖集的关系进行分析，我们得到如下 结论：一个包含完美匹配m 的图g 存在一个大小至多为n 2 + k 的点覆盖c 当且 仅当c 中的匹配点对数目至多为k ，问题从而转化为肘中至多有k 条边的两个 端点都在点覆盖集c 中。基于这个结论，本文将结合分支技术对参数化v c p m 问题的参数算法进行研究，并且当具有完美匹配的图g 存在一个大小为1 6 1 2 的 最小点覆盖时，本文将利用扩展n t 算法【l l 】以设计一个多项式时间的求解算法。 1 4 论文组织 论文全文共分五章： 第一章，绪论。这一章先介绍了计算复杂性的相关理论背景，并分析和介绍 了参数化a l m o s t2 - s a t 问题和参数化v c p m 问题的研究现状，最后阐述了课题 的研究内容和意义。 第二章，可满足性问题的研究成果和求解技术。这一章首先介绍了可满足性 问题及其约束子问题的定义，然后详细介绍了可满足性问题及其某些约束子问题 的研究现状，重点对参数化的可满足性问题的即r 算法和所用技术做了一个详 细的综述，并提出了目前存在的问题。 第三章，关于参数化的a l m o s t2 - s a t 问题的改进的即r 算法。这一章对参 数化的a l m o s t2 s a t 问题的子问题2 一a s l a s a t 问题的参数算法f i n d c s ( f , l ，厶妨 5 硕士学位论文 第一章绪论 进行了描述，并对算法的正确性和时间复杂度给出了详细的证明。 第四章，关于参数化v c p m 问题的确定型参数算法。这一章对参数化 v c p m 问题的参数算法m h v c ( g , 妨及其调用的p h v c ( g ，肝) 算法进行了描述和 证明。 第五章，结束语。这一章总结了课题研究内容，并对将来进一步的工作提出 了建议与展望。 6 硕士学位论文第二章可满足性问题 第二章可满足性问题 在众多n p 完全问题中，有一个问题被称为其它问题的“种子”，就是可满足 性( s a t i s f i a b i l i t y ，简称s a t ) 问题。依据c o o k 定理，s a t 问题是n p 完全的。 s a t 问题在硬件测试、人工智能、计算机视觉等很多领域都有广泛应用，对 于自动电子设计( e d a ) 领域的电路设计、f p g a 路由、组合等式检测等问题的 研究尤其重要。s a t 问题受到人工智能领域的关注是由于该问题和推理与定理证 明有着直接联系。演绎推理和可满足性问题是互补的，即给定一组基本事实， 可以推理出一个判定a 当且仅当u 飞) 是不可满足的。尽管s a t 问题的求解复 杂度很高，但由于它在工业中有着重要的应用，因而对其高效算法的需求日益增 加。 作为第一个被证明了的n p 完全问题，长时间以来s a t 问题的求解算法得到 了人们的深入研究和不断改进，以期得到实际应用中可以接受的计算复杂度。 d o w n e y 和f e l l o w s 1 2 】提出了一种新的解决n p 完全问题的方法，即很多难解或无 法判定的问题通过引入参数可以得到时间复杂度为o f f ( k ) 栉1 的固定参数可解 ( f i x e d p a r a m e t e rt r a c t a b l e ，简称即d 算法。随着参数理论的产生，s a t 问题 及其各类约束子问题也再次成为研究的热点。近年来，大量文章都在对s a t 问 题，尤其是对合取范式可满足性( c n fs a t ) 问题中的最大可满足性( m a xs a t ) 问题的参数化算法做了大量研究，并根据一种更有意义的参数设定，提出了 a l m o s t2 s a t 问题，最近i g o rr a z g o n 和b a r r y0 s u l l i v a n 引证明了该问题是即r 的。 本章内容组织如下：第二节介绍了s a t 问题及其各种约束子问题的定义， 第三节对常规s a t 问题的求解算法和研究现状进行了介绍，第四节主要总结和 分析了m a x - s a t 问题和带权的m a x s a t 问题的研究进展及求解技术，第五节 重点分析和总结了参数化m a x s a t 问题和参数化a l m o s t2 - s a t 问题的参数算 法中最新的求解技术，最后介绍了s a t 相关问题算法研究的结论并对其研究前 景进行了展望。 2 1s a t 问题分类及其定义 可满足性问题的定义如下： 定义2 1 ( s a t i s f i a b i l i t y ，简称s a t ) 1 1 3 1 ：给定一组布尔变量y 和一组由y 组 7 硕士学位论文第二章可满足性问题 成的子句集合c ，判定是否存在一组满足c 中所有子句的真值赋值。 这是常规的可满足性问题，问题的求解难度很大，为了便于分析问题和设计 实际应用中有效可行的算法，人们从不同角度对s a t 问题设定了约束条件，从 而形成了下列约束子问题。 定义2 2 ( c n fs a t i s f i a b i l i t y ，简称c n fs a t ) 1 2 1 ：给定一个包含掰个子句 的合取范式，判定是否存在一种真值赋值尸使得，的取值为真，即，相对于尸 是可满足的。 由于c n fs a t 问题可在多项式时间内规约到3 - s a t 问题，所以c n f s a t 三二3 s a t 1 4 1 。 某些情况下人们对真值赋值p 中允许取值为1 的字符个数设定了限制条件， 此类问题称为带权的可满足性问题( w e i g h t e ds a t i s f i a b i l i t y ) ，定义如下： 定义2 3 ( w e i g h t e ds a t i s f i a b i l i t y ，简称w - s a t ) 1 f l ：给定一个布尔表达式x 和一个正整数k ，判定是否存在一种真值赋值p 使得x 取值为真，且尸的h a m m i n g 权值为k 。 尸的h a m m i n g 权值是指真值赋值p 中取值为1 的字符的个数。w - s a t 问题 是w s a t 完全的，是w s a i t 】类的核心问题【1 6 】。 若给定的布尔表达式为合取范式，则相应的带权问题定义如下： 定义2 4 ( w e i g h t e dc n fs a t i s f i a b i l i t y ，简称c n fw - s a t ) ：给定一个包含小 个子句的合取范式f ，一个正整数k ，判定是否存在一种h a m m i n g 权值为k 的真 值赋值p 使得，为真。 c n f w - s a t 问题是w 【2 】完全的【1 2 】【1 刀【1 8 1 。 由于问题中的各个子句包含的字符数各不相同，增加了问题的求解难度，为 了便于分析和求解，人们对子旬中包含的字符数增加了约束条件，称之为q c n f s a t 问题【1 5 】，如q = 3 时，即为3 - c n fs a t 问题。 定义2 5 ( g c n fs a t ) ：给定一个包含聊个子句的合取范式乃每个子句只 包含g 个字符，判定是否存在一种真值赋值使得，为真。 当问题中给定的合取范椰可满足时，需要求解一种真值赋卸使得尸i 芮足 f 中最多数目的子句，称之为最大可满足性问题( m a x i m u ms a t i s f i a b i l i t y ，简称 m a x - s a t ) 1 1 9 。 定义2 6 ( m a x i m u ms a t i s f i a b i l i t y ) ：给定一个包含m 个子句的合取范式n 一 组变量品判定是否存在一种真值赋值满足f 中最多数目的子旬。 在某些实际情形中，由于每个子旬所起的作用不同，因而对其分别赋以不同 的权值以描述其不被满足时的代价，此类问题称为带权的最大可满足性问题 ( w e i g h t e dm a x s a t ) 2 0 l 。 8 硕士学位论文第二章可满足性问题 定义2 7 ( w e i g h t e dm a x s a t ) ：给定一个包含聊个子句的合取范式f ，一组 变量咒每个子句赋予一个正权值，返回一组权值最小的满足f 中最多数目子句 的真值赋删返回不存在。 以上所述问题均为n p 完全的，人们都是通过设计相应的近似算法、启发式 算法进行求解，即便存在精确算法，其复杂度也都是以输入问题的规模m 为指 数( 朋为子句个数) ，当s 较大时，问题几乎是不可解的。为了得到有实际意义 的精确算法，人们将注意力转移至对参数化s a t 问题的研究。所谓参数化问题 是从原问题出发，从中找到一个较小的参数k ，使得算法的时间复杂度主要与k 有关。 参数化的带权q - c n fs a t 问题的定义如下： 定义2 8 ( 参数化的带权q c n fs a t ) 1 5 】：给定一个包含聊个子句的合取范 式f 和一个正整数k ，每个子句均只包含g 个字符，判定是否存在一种真值赋值 p 使得f 为真且p 的h a m m i n g 权值为k 。 当口2 时，通过独立集( i n d e p e n d e n ts e t ) 问题的规约可以证明参数化的带 权q - c n fs a t 问题是w 【1 】完全的【l 】【2 。 对于f 中只包含3 个字符的子句个数为k 的3 - c n fs a t 问题，即参数化 3 - c n fs a t 问题定义如下： 定义2 9 ( 参数化3 - c n fs a t ) 1 1 5 l ：给定一个包含m 个子句的合取范式凡 每个子句至多包含3 个字符，中只包含3 个字符的子句个数为k ，判定是否存 在一种真值赋值尸使得f 为真。 文献【2 2 】利用搜索树技术提出了一个固定参数可解算法，证明了参数化 3 - c n fs a t 问题是即确。 定义2 1 0 ( 参数化m a xs a t ) 2 3 】：给定一个包含历个子句的合取范式只一 组变i x , 和一个正整数k ，判定是否存在一种真值赋值至少满足f 中阶子句。 参数化m a xs a t 问题是即7 韵【2 3 】。 因为对于任一个含有m 个子句的合取范式，总能找到一个真值赋值p 使得尸 可以满足f 的至少m 2 个子句【2 3 】，所以当k ，否则，对问题实例恳眠s i ，幼进行求解。通过对 表达式，的转化最终可以将问题p 2 转化为问题2 - a s l a s a t 的求解，即给定一 个2 - c n f 表达式凡一个非矛盾字符集l ，s w r t ( f , 三) 为真，一个不属于的字 符，参数k ，求解c l a u s e ( f ) 的一个子集s 使得s w r t ( f 峪, 三u 册) 为真。利用分 支技术对2 - a s l a s a t 问题提出了一个复杂度为d ( 5 勺的参数算法，算法总的时 间复杂度为转化过程所需时间d l ( 3 七) 和2 - a s l a s a t 问题算法复杂度的乘积即 o * ( 1 5 k ) 。 2 5 本章小结 本章分别描述了s a t 问题及其各类约束子问题s a t 问题的定义，介绍了其 研究现状，并重点阐述和分析了参数化m a xs a t 问题和参数化2 一a s a t 问题的 f p t 算法和采用的相关技术。 参数化a l m o s t2 - s a t 问题的f p t 算法主要通过将原问题转化为参数化 2 - a s l a s a t 问题的求解，算法的复杂度主要源于该参数算法中搜索树中的叶子 节点数目，通过对同一路由上的相邻子旬的组合分析可以细化分支，进一步改进 算法复杂度。 参数化a l m o s t2 - s a t 问题从f p t 的意义上来讲等价于有完美匹配的图上的 点覆盖问题( v c - p m 问题) ，目前只存在相关的近似算法【1 0 】，利用核心化和分支 技术对参数化v c p m 问题进行求解有望得到相应的确定型参数算法，从而可以 用于2 - a s a t 问题的求解。 1 6 硕士学位论文第三章a l m o s t2 - s a t 问题的参数算法研究 第三章a l m o s t2 - s a t 问题的参数算法研究 a l m o s t2 - s a t 问题首先是在1 9 9 7 年由m a h a j a n 和r 锄觚【7 】提出的，之后在 2 0 0 7 年举行的d a g s t u h l 研讨会上f e l l o w s 再一次将其列入开放性难题之列。i g o r r a z g o n 和b a r r yo s u l l i v a n 在文献【8 】中证明了a l m o s t2 s a t 问题为固定参数可 解的，并给出了时间复杂度为o ( 1 5 七毒k 幸m 3 ) 的f p t 算法 s k h o t 和v r a m a n 6 7 指出a l m o s t2 一s a t 问题是广义上的图的二维划分问 题( g r a p hb i p a r t i z a t i o np r o b l e m ) ，文献【6 8 】对图的二维划分问题进行了求解，并 提出了一种新的求解技术迭代压缩，这种方法对参数算法的设计产生了重要 影响。目前无向图反馈顶点集( f v s ) 问题的最优算法【6 9 】与有向图反馈顶点集 ( d f v s ) 问题的f p t 算、法【7 0 】都采用了迭代压缩技术进行求解，其他基于迭代压缩技 术的相关研究结果可以参阅文献r 7 1 】。d m a r x 在文献 7 2 中首次提出了图的划分 问题，文章提出的求解技术可用于多顶点割集问题( m u l t i t e r m i n a lc u tp r o b l e m ) 和 更广义上的m u l t i c u t 问题的求解，但是对于m u l t i c u t 问题，还需要另外引入被分 割的顶点对的数目做为参数。j c h e l a ，y l i u 和s l u 【7 3 】针对多顶点割集问题提 出了第一个即丁算法，d f v s 问题的参数算法m 1 就是通过对其中的主要定理重新 构造得到的。文献【8 】在a l m o s t2 s a t 问题的求解算法中采用文献【7 3 】中主要定 理的证明方法，证明了在输入字符集中引入中立字符( n e u t r a ll i t e r a l ) 不会使得 求解的子句集合增大。参数化m a x - s a t 问题与2 a s a t 问题是互补的，问题的 定义如下：给定一个2 - c n f 表达式f ，判定是否存在一种真值赋值尸使得，至 少有k 个子旬取值为真? 目前参数化m a x s a t 问题最优的f p t 算法的时间复 杂度为0 ( 1 3 7 旧) 0 7 4 】，其中l ，i 为给定表达式，中子旬的数目。 2 a s a t 问题是最优化问题，即从给定的2 c n f 表达式中删除最少数目的子 句使得得到的表达式为可满足的。参数化2 - a s a t 问题引入了参数k ，即判定是 否可以从给定表达式中删除至多k 个子句使得所得表达式为可满足的。i g o r r a z g o n 和b a r r yo s u l l i v a n 8 】利用文献【9 】中图的二维划分问题的求解方法将 2 a s a t 问题转化为2 a s l a s a t 问题的求解，其定义如下：给定一个三元组 l ，乃，其中f 为一个2 c n f 表达式，三是一个满足f 的非矛盾字符集( 即不同 时包含字符z 和一，且令三中的字符均赋值为1 ，此时存在一个使得f 为真的赋 值方案p ) ，为一个字符且，叠厶判定从表达式f 中删除最少数目的子句使得 uf m 满足所得表达式。 因为同一路由上的相邻子句c o = ( 1 0 v - , 6 ) 、c l = ( 1 l v 2 ) 和c 2 = ( - z 2 v 6 ) 满足c i 的第二个字符与o l 的第一个字符互补，所以当对c l 中的某个字符进行赋值时， 1 7 硕士学位论文 第三章a l m o s t2 - s a t 问题的参数算法研究 c 0 和q 中相应的字符的值已经确定，所以我们通过对同一路由( w a l k ) 上的相 邻子句进行组合分析，细化分支，对2 - a s l a s a t 问题提出了一个确定型参数算 法。 3 1基本知识 定义3 1c n f 表达式：合取范式，2 - c n f 表达式中的每个子句均至多含有两 个变量。 这里我们对问题中的2 - c n f 表达式f 设定两个前提：首先假定f 中每个子 句均含有两个变量，如果某个子句只含一个变量，则可以将其表示为( t v 0 ，其 次假定给定表达式f 中的子句两两互不相同。 令，为一个2 - c n f 表达式，s 为一个子句集合，c 为一个子旬，三为一个字 符集合，v a r ( f ) 、v a t ( 回、v a r ( c ) 和v a r ( l ) 分别表示只s 、c 和中的字符所对 应的变量，对于单个字符，v a r ( 0 表示，对应的变量，c l a u s e ( f ) 表示f 中所有子 句的集合。 定义3 - 2 非矛盾字符集：如果字符集合不同时包含字符，和1 ，则称己为 非矛盾字符集。 如果对于子旬( ，lv 1 2 ) ，字符埔菊足卢j l 或l = 1 2 ，则称z 满足子句( 1 lv t 2 ) 。给定 一个2 - c n f 表达式，一个非矛盾字符集，如果v a t ( f ) = v a r ( l ) ，且，中的每 个子句至少包含中的一个字符，则称工为f 的真赋值。当，有至少一种真赋 值时，f 是可满足的。给定一个字符集，则吧为三中字符的非的集合，即如果 l = l l ，2 ，如) ，贝f i - l = - - 6 ，嘞，叱 。 表达式f 相对于为可满足的是指给定一个2 - c n f 表达式b 令三中字符 均赋值为l ，存在一种真值赋值p 使得f 取值为1 。文章中用s w r t ( e 三) 为真表 示f 相对于字符集三是可满足的，s w r t l ，d 为真表示f 相对于u d 为可 满足的。 定义3 3 路由( w a l k ) ：对于给定的2 c n f 表达式f ，路由w 是，中一个非 空子句序列w = ( a ，c q ) ，对于每个子句g ，c ：f 的第一个在w 中出现的字符 称为c ：f 相对于w 的第一个字符，另一个字符称为c i 相对于w 的第二个字符，对 于任意两个相邻子句，c i 的第二个字符与c a l 的第一个字符互补，w 中允许出现 重复子句。 给定一个路由w = ( c l ，q ) ，l l 为c l 的第一个字符，广为q 的第二个字符， 则称| l 为w 的第一个字符，广为w 的最后一个字符，w 是一条从，l 到广的路由。 如果1 1 厶则称w 是一条从二出发的路e h 我们将( c 0 ，c 1 ) 中的每个子句c i 1 8 硕士学位论文第三章a l m o s t2 - s a t 问题的参数算法研究 的第一个字符与第二个字符互换之后得到的路由用r e v e r s e ( w ) 表示。 定义3 _ 4 路径( p a t h ) ：路径是指f 中子句互不相同的路由。 我们举例说明一下上述的两个定义。给定一个路由w = 他v t 2 ) ，( - 1 2 vt 3 ) ，( - 1 3 vz 4 ) ，c 吨v 吗)