Java教程

算法设计学习笔记(八)NP与计算的难解性

本文主要是介绍算法设计学习笔记(八)NP与计算的难解性,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

  • 前言
  • 一、多项式时间归约
    • 1.1 第一个规约:独立集与顶点覆盖
    • 1.2 归约到更一般的情况:从顶点覆盖到集合覆盖
  • 二、使用零件的归约:可满足性问题
    • 2.1SAT和3-SAT
    • 2.2 将3-SAT归约到独立集
    • 2.3 归约的传递性
  • 三、有效证书和np的定义
    • 3.1 问题与算法
    • 3.2 有效证书
    • 3.3 NP:一个问题类
  • 四、NP完全问题
    • 4.1 电路可满足性:第一个NP完全问题
    • 4.2 证明更多的问题是NP完全的
    • 4.3 证明新NP完全问题的通用策略
  • 五、排序问题
    • 5.1 巡回售货员问题
    • 5.2 哈密尔顿问题
    • 5.3 证明哈密尔顿问题是NP完全的
    • 5.4 证明巡回售货员是NP完全的
    • 5.5 推广:哈密顿路径问题
  • 六、划分问题
    • 6.1 三维匹配问题
    • 6.2 证明三维匹配是NP完全的
  • 七、图着色
    • 7.1 图着色问题
    • 7.2 图着色问题的计算复杂性
    • 7.3 证明三着色问题是NP完全的
    • 7.4 四色问题的猜想
  • 八、数值问题
    • 8.1 子集和问题
    • 8.2 证明子集和问题是NP完全的
    • 8.3 推广:某些调度问题的难度
    • 8.3 说明:有多项式界限数值的子集和
  • 九、co-NP以及NP的不对称性
    • 9.1 好的特性
  • 十、难问题的部分分类
    • 10.1 包装问题
    • 10.2 覆盖问题
    • 10.3 划分问题
    • 10.4 排序问题
    • 10.5 数值问题
    • 10.6 约束满足问题


前言

本文是对于算法设计的学习笔记,如有错误,请不吝赐教。


NP完全问题:NP完全性意味着:在计算上实际是难的,虽然我们不能证明它。

一、多项式时间归约

在这里插入图片描述
Y多项式时间可归约到X(或者X至少像Y一样的难)
在这里插入图片描述

1.1 第一个规约:独立集与顶点覆盖

在这里我们回顾独立集的定义:在图G=(V,E)中,如果顶点集合V中的任意两点间都没有边,那么称V是独立的。
独立集问题就是在图G中寻找一个最大的独立集。
为了方便研究,我们将问题修改为:
给定图G和数K,问G中是否包含大小至少为k的独立集。

顶点覆盖(没有已知的有效算法):给定图G=(V,E),顶点S属于V,如果每一条边e至有一个定点在S中,我们称S是一个顶点覆盖。
顶点覆盖问题:给定图G和数k,G中是否包含大小至少为k的顶点覆盖。

在这里插入图片描述

补充证明:假设S是一个独立集,考虑任意一边(u,v),可知u,v必有一个在V-S中,所以可知V-S是一个顶点覆盖。

由此我们可以得到一个这两个问题的归约。
在这里插入图片描述

补充证明:假设有一个解顶点覆盖的黑盒子,那么通过问黑盒子G是否有大小至多为n-k的顶点覆盖,那么就能确定G是否有大小为k的独立集。

反之亦然
在这里插入图片描述
由此我们知道了以上两个问题的相对困难水平。

1.2 归约到更一般的情况:从顶点覆盖到集合覆盖

独立集和顶点覆盖是两种不同类型的问题。
独立集可以看做包装问题:装入尽可能多的顶点,要从服从一些限制条件(边)
顶点覆盖可以看做一个覆盖问题:用尽可能少的顶点覆盖图中所有的边。

顶点覆盖是特殊的覆盖问题,而集合覆盖是更为一般的覆盖问题。在集合覆盖中,试图用一组较小的组合覆盖一个任意的对象集合。
覆盖问题的具体描述如下:

在这里插入图片描述
在这里插入图片描述
具体我们可以这样做:
我们对每个顶点v,设Sv是图中所有与i关联的边,把sv加入到集合覆盖的实例中。
我们可知如果U能被s1,s2,,,sn中的至多k个覆盖,当且仅当G有大小至多为k的定点覆盖。(如果s1,s2,sl是l<=k的覆盖U的集合,那么G中的每一条边都关联到i1,i2。。。il顶点,所以其中i1,i2,i3是G中大小为l<=k的顶点覆盖。反之亦然)
在这里插入图片描述
而对于独立集而言,独立集的自然推广是关于任意集合的包装问题。
具体的集合包装问题定义如下:
在这里插入图片描述
在这里插入图片描述

二、使用零件的归约:可满足性问题

2.1SAT和3-SAT

在这里插入图片描述
在这里插入图片描述
举例如下:

在这里插入图片描述
可满足问题(SAT):
在这里插入图片描述
如果所有的字句都包含3个项,那么这个问题被称作三元可满足性(3-SAT)

2.2 将3-SAT归约到独立集

在这里插入图片描述
在这里插入图片描述
具体证明如下:
两个项冲突:一个项等于变量xi,另一个等于他的否定xi!
在这里插入图片描述
归约具体过程见p327

2.3 归约的传递性

在这里插入图片描述
在这里插入图片描述

三、有效证书和np的定义

3.1 问题与算法

我们可以认为一个计算问题的输入被编码为有穷的二进制串s。串s的长度记作|s|,把判定问题X等同于对它的答案为yes的串组成的集合。判定问题的算法那A接受输入串s并返回yes或者no,这个返回这记作As,如果对于所有的串s,As=yes,当且仅当s属于X,那么就称A解问题X。
而如果存在多项式P,使得对于每个输入s,算法A都有在至多OP步内终止,那么称A有多项式运行时间。

3.2 有效证书

在这里插入图片描述
在这里插入图片描述

有效验证程序B:
在这里插入图片描述
我们可以人为有效验证程序并不打算亲自去判断输入S是否属于X,而愿意去有效的评估所提交的s属于X的证据t。

3.3 NP:一个问题类

定义Np是所有存在有效验证程序的问题的集合。
在这里插入图片描述

补充:在这里插入图片描述

在这里插入图片描述
我们目前相信p!=Np

补充:p问题是在多项式时间内可解的问题。
Np问题:问题只能通过验证给定的猜测是否正确来求解。所谓多项式:验证猜测可在多项式时间内完成。且问题只能通过验证猜测来解,而不能直接求解。

四、NP完全问题

Np中最难的问题:
1)X属于NP
2)对于所有的Y属于np,由Y<=px 即np中的每个问题都能够归约到X
我们称这样的X是NP完全问题。
在这里插入图片描述

4.1 电路可满足性:第一个NP完全问题

我们定义电路K是一个带标号的有向无圈图。
K中的源节点的标号为常数0,1或者不同的变量名,这被看做是电路的输入
其他节点都标有布尔运算
有唯一一个不带离开边的节点,他表示输出即电路计算的结果。

如下如图所示:
在这里插入图片描述
电路可满足性问题如下:
给定一个电路,需要确定是否存在对输入的赋值使得输出值为1

在这里插入图片描述
具体证明如下:
在这里插入图片描述
例如:
在这里插入图片描述

4.2 证明更多的问题是NP完全的

在这里插入图片描述
在这里插入图片描述
对于上述结论的证明,我们可以通过归约电路可满足性来进行。
在这里插入图片描述
如果Sat中的只有一个项t的子句,我们可以考虑用在这里插入图片描述
方式来完成,其中z1=z2=0
在这里插入图片描述

4.3 证明新NP完全问题的通用策略

在这里插入图片描述
在这里插入图片描述
后者的归约可能会多次请求黑盒子(Karp归约,Cook归约)

五、排序问题

5.1 巡回售货员问题

问题:有一位巡回售货员,他必须访问n个城市,分别记作v1,v2。。。vn,售货员从他居住的城市v1出发,想找一条旅行路线,即访问所有的城市最后回到家的顺序,他的目标是整个旅行路线的距离尽可能的小。
在实际应用中,旅行者问题运用在许多场合(规划人工机械臂有效动作,io请求,n个模块的执行顺序等)

5.2 哈密尔顿问题

给定一个有向图G=V,E,如果G中的圈C恰好经过每个顶点一次,则称圈C是一个哈密顿图。即它构成一条经过所有顶点的,没有重复的路线。

5.3 证明哈密尔顿问题是NP完全的

在这里插入图片描述

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

5.4 证明巡回售货员是NP完全的

在这里插入图片描述
通过将哈密尔顿归约到巡回售货员得到上述结论。

5.5 推广:哈密顿路径问题

哈密顿圈的一个变种是不需要回到出发点。
我们同样也可以证明哈密顿路径是NP完全的。(同样采用3-SAT的归约或者是哈密顿圈归约到哈密顿路径上)

六、划分问题

6.1 三维匹配问题

三维匹配问题可以看做是二部图匹配问题的难解形式。
在这里插入图片描述
满足上述条件的有序三元组集合叫做一个完美的三维匹配。
(三维匹配同时是集合覆盖和集合包装的特殊情况)

6.2 证明三维匹配是NP完全的

在这里插入图片描述
我们可以容易证明三维匹配是NP的。(可以在多项式时间内验证解)
(设计一些零件表示对每个变量的真值赋值的独立选择,然后添加一些零件表示字句强加的约束。)

在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
具体证明见P342

七、图着色

7.1 图着色问题

给定一个无向图G,我们对G中的每一个节点分配一种颜色,使得如果(u,v)是一条边,则分配给u,v不同的颜色,目标是使用很少的几种颜色就做到这一点。
如果G有一个k-着色,那么称它是k-可着色的图。
相关应用:
在这里插入图片描述

7.2 图着色问题的计算复杂性

在这里插入图片描述

而往上的三着色等问题会更加复杂。

7.3 证明三着色问题是NP完全的

在这里插入图片描述
考虑字句在这里插入图片描述

在这里插入图片描述
具体证明见P345
在这里插入图片描述

7.4 四色问题的猜想

四色猜想是对于区域数的归纳。

八、数值问题

使用非常大的整数表示问题的编码。

8.1 子集和问题

这类问题的基本问题是子集和问题。
表述如下:
在这里插入图片描述
当数w较大时,该问题就变得非常复杂。

8.2 证明子集和问题是NP完全的

我们将三维匹配问题归约到子集和问题。(组合选择问题)
具体证明见P348

8.3 推广:某些调度问题的难度

子集和的难度可以用来给出某些调度问题的难度,包括一些不明显含有数值加法的调度问题在内。
比如带开发时间和截止时间的调度问题:

在这里插入图片描述
证明见P349

8.3 说明:有多项式界限数值的子集和

在这里插入图片描述
比如分支聚合问题不是np完全的。
在这里插入图片描述
在这里插入图片描述

九、co-NP以及NP的不对称性

在这里插入图片描述

在这里插入图片描述

9.1 好的特性

在这里插入图片描述

十、难问题的部分分类

10.1 包装问题

在这里插入图片描述

10.2 覆盖问题

在这里插入图片描述

10.3 划分问题

在这里插入图片描述

10.4 排序问题

在这里插入图片描述

10.5 数值问题

在这里插入图片描述
在这里插入图片描述

10.6 约束满足问题

在这里插入图片描述

这篇关于算法设计学习笔记(八)NP与计算的难解性的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!