算法设计与分析 NP完全问题_第1页
算法设计与分析 NP完全问题_第2页
算法设计与分析 NP完全问题_第3页
算法设计与分析 NP完全问题_第4页
全文预览已结束

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

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

2、 L1当且仅当fe L;。用L1氐L;表示存在一个从语言L1到语言L;的多项式变换。相应地,对于判定问题n ,n,设e和e是相应的编码策略。若Ln ,e X Ln ,e ,则记为1;1211;n 1 xn ;。也可以从问题的层次来叙述:由判定问题n1到判定问题n;的多项式变换是 满足下列条件的函数f : Dn T Dn,f可由一个多项式时间的确定性算法来计算;对于所有的le Dn有:IeDn当且仅当fe、;。定义2称一个语言L (判定问题n )为NP完全的(NPC ),如果L e NP (ne NP),且对于所有别的语言 Le NP (判定问题ne NP )均有 l x l (n x n)。按

3、照定义2,要证明问题n是NP完全的,需要证明所有的NP问题均能够 经多项式变换变成n。这几乎是很难做到的。如果NP完全问题比较多,我们也 不能对每一个这样的问题都这样验证。为此我们讨论一些NPC问题的有用的性 质。性质1如果L氐L,则L e P意味着Le P。性质2如果L x L而且L x L,则L泛L。由性质1, 2,不能推出下列结论,定理2设n是NP完全的,如果P。NP,则Ue NP P。定理 3 如果 L , L e NP,Lx L,则 Le NPC n L e NPC .定理3是证明NP完全问题的基础。但这需要一个NPC问题作为源问题Cook 首先给出这样问题一可满足性问题。可满足性问

4、题是数理逻辑中一个重要问题,它定义在布尔变量之上。给定 布尔变量集U = ,u2, ,um,U上的一个真值分配是指一个映射t: U T, F。U上的一个子句C就是由一些布尔变量(或它们的“否”)通过逻辑“或”连接起来的布尔表达式。若存在对于布尔变量集U的一个真值分配, 使得该子句取值为真,则说该子句被满足。子句的集合说是可满足的,如果存在 U的一个真值分配,使得集合中的每个子句的取值均为真。可满足性问题可描述 如下:例 给定布尔变量之集U以及U上子句的一个集合C。问是否存在U的一个真值分配,使得C是可满足的。Cook定理 可满足性问题是NP完全问题。从Cook的开创性工作至今,人们已经发现并证

5、明了数千个NPC问题(如, 0/1背包问题和Hamilton回路问题),总结出证明NP完全性的几种方法,并建 立了如何分析、进而近似求解NP完全问题的方法等一系列理论结果。以下列出几个典型的NPC问题:三维匹配问题 3DM(3 Dimensional Matching)例: 给定三个互不相交的、均含有q个元素的集合W,X,Y,取M c W x X x Y。问:M包含一个匹配吗?即是说,是否存在一个子集Mc M,使得I MI = q,且M中任意两个三元组都没有相同的分量。 三元精确覆盖问题X3C(Exact Cover by 3-sets)例:给定有限集合X, IXI = 3q,以及X的三元子集

6、族C。问:C含有X的一个精确覆盖吗?即是说,是否存在一个子族Cc C,使得X的每个元素恰好只出现在C的一个三元子集中。注意到,如果令 =W u X u Y , C = w,尤,ywe W,xe X,y e Y,则三元 匹配问题就转化为三元精确覆盖问题。又因为三元匹配问题是NP完全问题,所 以,由三元匹配问题是NPC问题,可以知道,三元精确覆盖问题也是NPC问题。顶点覆盖问题VC (Vertex Cover)例:给定一个图G(V,E)和一个正整数K|V|.问:是否存在G的一个顶点数不超过K的覆盖?即是否存在一个顶点子集V/c V,|V/| K,使得对于每一条边u,v eE,u与v中至少有一个属于V/.Hamilton 回路问题 HC (Hamiltonian Circuit)例:已知一个图G(V,E)。问:G含有一个Hamilton回路吗? G的Hamilton回路是指包含图G的所有 顶点的简单回路,即是G的顶点的一个排序:七勺,匕,其中n=|V|,使 得对所有的 i: 1 i n, ( v ,v eE,( v ,v eE.i i+1n 1划分问题例 已知一个有限集合A及对于每个a e A的一个权值s(a) e Z +。问问是否存在A的一个子集4C A,使得s(a) = s(a) ?aeAaeA

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论