算法设计与分析 np完全问题

《算法设计与分析 np完全问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、NP完全问题研究P=NP的问题有两条基本思路：1．证明NP类中的某些问题是难解的，从而得到NP¹P。但是要证明这一点几乎同证明P=NP一样困难。2．考察NP类中问题之间的关系，从中找到一些具有特殊性质的、与P类问题显著不同的问题。沿着这一路线人们已经证明了在NP类中存在被称为NP完全的子类，简称NPC问题，并由此发展了一套著名的NP完全理论。本节简要先介绍NP完全性理论。为此，首先给出各语言之间的多项式变换的概念。定义1所谓从一个语言到另一个语言的多项式变换是指满足下面两个条件的函数，(1)存在计算的一个多项式时间DTM程序；(2)对于所有的有：当且仅当。用表示存在一个从语言

2、到语言的多项式变换。相应地，对于判定问题，设e1和e2是相应的编码策略。若，则记为。也可以从问题的层次来叙述：由判定问题到判定问题的多项式变换是满足下列条件的函数，(1)可由一个多项式时间的确定性算法来计算；(2)对于所有的有：当且仅当。定义2称一个语言（判定问题）为NP完全的（NPC），如果，且对于所有别的语言（判定问题）均有。按照定义2，要证明问题是NP完全的，需要证明所有的NP问题均能够经多项式变换变成。这几乎是很难做到的。如果NP完全问题比较多，我们也不能对每一个这样的问题都这样验证。为此我们讨论一些NPC问题的有用的性质。性质1如果，则意味着。性质2如果，则。由性质

3、1，2，不能推出下列结论，定理2设是NP完全的，如果，则。定理3如果，则.定理3是证明NP完全问题的基础。但这需要一个NPC问题作为源问题。Cook首先给出这样问题--可满足性问题。可满足性问题是数理逻辑中一个重要问题，它定义在布尔变量之上。给定布尔变量集，上的一个真值分配是指一个映射。上的一个子句C就是由一些布尔变量（或它们的“否”）通过逻辑“或”连接起来的布尔表达式。若存在对于布尔变量集的一个真值分配，使得该子句取值为真，则说该子句被满足。子句的集合说是可满足的，如果存在的一个真值分配，使得集合中的每个子句的取值均为真。可满足性问题可描述如下：例给定布尔变量之集以及上子句

4、的一个集合C。问是否存在的一个真值分配，使得C是可满足的。Cook定理可满足性问题是NP完全问题。从Cook的开创性工作至今，人们已经发现并证明了数千个NPC问题（如，0/1背包问题和Hamilton回路问题），总结出证明NP完全性的几种方法，并建立了如何分析、进而近似求解NP完全问题的方法等一系列理论结果。以下列出几个典型的NPC问题：²三维匹配问题3DM(3DimensionalMatching)例：给定三个互不相交的、均含有个元素的集合，取。问：包含一个匹配吗？即是说，是否存在一个子集，使得，且中任意两个三元组都没有相同的分量。²三元精确覆盖问题X3C(ExactCov

5、erby3-sets)例：给定有限集合，以及的三元子集族。问：含有的一个精确覆盖吗？即是说，是否存在一个子族，使得的每个元素恰好只出现在的一个三元子集中。注意到，如果令，，则三元匹配问题就转化为三元精确覆盖问题。又因为三元匹配问题是NP完全问题，所以，由三元匹配问题是NPC问题，可以知道，三元精确覆盖问题也是NPC问题。²顶点覆盖问题VC（VertexCover）例：给定一个图G(V,E)和一个正整数K£

6、V

7、.问：是否存在G的一个顶点数不超过K的覆盖？即是否存在一个顶点子集V/ÍV,

8、V/

9、£K，使得对于每一条边{u,v}ÎE，u与v中至少有一个属于V/.²Hamilton

10、回路问题HC（HamiltonianCircuit）例：已知一个图G(V,E)。问：G含有一个Hamilton回路吗？G的Hamilton回路是指包含图G的所有顶点的简单回路，即是G的顶点的一个排序：[v1,v2,¼,vn]，其中n=

11、V

12、，使得对所有的i:1£i£n,{vi,vi+1}ÎE，{vn,v1}ÎE.²划分问题例已知一个有限集合A及对于每个的一个权值。问问是否存在A的一个子集，使得？²三元可满足性问题3SAT例子给定布尔变量的一个有限集合U及定义于其上的字句集,其中问题是否存在U之上的一个真赋值，使得C中所有的子句均被满足？