NP-Hard?大白话学习P问题、NP问题、NP完全问题和NP难问题

这篇具有很好参考价值的文章主要介绍了NP-Hard?大白话学习P问题、NP问题、NP完全问题和NP难问题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

## 该笔记自用为主,记录一些日常学习过程中看到的不熟悉的知识和从未接触过的知识,用于回看和记录。其中有一些个人理解,如有错误请讨论指正。

前言

在讨论这一串问题之前,我们需要复习两个概念。

1.多项式和非多项式

多项式:NP-Hard?大白话学习P问题、NP问题、NP完全问题和NP难问题

非多项式:或者

2.时间复杂度

在计算机算法求解问题当中,经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小。时间复杂度则表示这个算法运行得到想要的解所需的计算工作量。这里探讨的是当输入值(也就是问题数目N,或者是待求解的问题)接近无穷时,算法所需工作量的变化快慢程度。

举例:冒泡排序。

在计算机当中,排序问题是最基础的,将输入按照大小或其他规则排好序,有利于后期运用数据进行其他运算。冒泡排序就是其中的一种排序算法。假设手上现在有n个无序的数(N个待排序的问题),利用冒泡排序对其进行排序,

①首先比较第1个数和第2个数,如果后者>前者,就对调他们的位置,否则不变

②接着比较第2个数和第3个数,如果后者>前者,就对调他们的位置,否则不变

③一直向下比较直到第n-1和第n个数比较完,第一轮结束。(这时候最大的数移动到了第n个数的位置)

④重复前三步,但是只比较到第n-1个数(将第二大的数移动到第n-1个数位置)

⑤持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

举个实例:5,4,3,2,1,对其进行排序,先是比较5跟4变成4,5,3,2,1,第一轮结束后变成43215,可以计算,当对其排序完正好要经过4+3+2+1=10次比较,当然这是最复杂的情况,即完全反序。可以知道对于n个数,至多要经过1+2+...+n-1即(n^2-n)/2次比较才能排好序。这个式子里n的最高次阶是2,可知道当n→∞时,一次性对其比较次数影响很小,所以我们把这个算法的时间复杂度比作:。取其最高次,可以看出,这是一个时间复杂度为多项式的表示方式。

另外一些穷举类的算法,所需时间长度成几何阶数上涨,这就是的指数级复杂度,甚至的阶乘级复杂度。它是非多项式级的,其复杂度计算机往往不能承受。

当我们在解决一个问题时,我们选择的算法通常都需要是多项式级的复杂度,非多项式级的复杂度需要的时间太多,往往会超时,除非是数据规模非常小。

正文

1、P问题
P问题:能够在多项式时间内被解决的问题。

比如说,给10个、20个、30个… 元素(问题)排序,复杂度是

2、NP问题
NP问题:能够在多项式时间内使用非确定性算法(non-deterministic)被解决的问题。

NP问题也可以指在多项式的时间里验证一个解的问题。另一个定义是,可以在多项式的时间里猜出一个解的问题。

简单来说就是,必须以非常规方法才能在多项式时间内解决的问题,就叫做NP问题。

举个例子:

我人品很好,在程序中需要枚举时,我可以一猜一个准。

现在某人拿到了一个求最短路径的问题,问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图,但怎么也算不出来,于是来问我:你看怎么选条路走得最少?

我说,我人品很好,肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线,说就这条吧。那人按我指的这条把权值加起来一看,嘿,神了,路径长度98,比100小。

于是答案出来了,存在比100小的路径。别人会问他这题怎么做出来的,他就可以说,因为我找到了一个比100 小的解。在这个题中,找一个解很困难,但验证一个解很容易。

验证一个解只需要O(n)的时间复杂度,也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么,只要我运气好,猜得准,我一定能在多项式的时间里解决这个问题。这就是NP问题。

3、NP-complete问题(即:NP完全问题)

NP-Complete 满足两个条件:

  • 首先它是一个NP问题
  • 所有的NP问题都可以约化(Reducible)到它,NPC问题目前没有多项式的有效算法,只能用指数级甚至阶乘级复杂度的搜索

约化:例如,求解一个一元一次方程 A AA 和求解一个一元二次方程 B BB,你若会求解 B BB ,你一定会求解 A AA。那么我们说,A 可以约化为 B。B BB 的时间复杂度高于或者等于 A AA的时间复杂度。

NP问题中最困难的问题称之为NP完全问题(NP-complete)。根据库克定理,任意一个NP完全问题如果能够在多项式时间内解决,则所有的NP问题都能在多项式时间内解决。

一般来说,非常规方法既可以解决P问题,也可以解决NP问题,所以,只有用非常规方法才能解决的问题,才能叫做NP完全问题。

示例:旅行商问题。就是一个NP完全问题,因为其开销不能在多项式时间内解决,而是一个非多项式时间复杂度的问题。

4、NP-Hard问题(即:NP难问题)
NP-Hard问题:和NP问题一样困难,或者更加困难的问题。

NP hard 满足 NPC 的第二条件,但不一定是 NP 问题。
因为它不一定是NP问题。即使 NPC 问题发现了多项式级的算法,NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上,由于 NP-Hard 放宽了限定条件,它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

anyway,感觉对于NP-C和NP-Hard还是有一点点混淆,等下次再遇见了再来理解并修改它。

其实还有点想纠结一下NPC的逻辑,但是,下次再说吧

以上四个问题他们之间的关系可以用下图来表示: 

参考链接:

到底什么是NP问题,NP hard问题,NP完全问题?

P问题、NP问题、NP完全问题和NP难问题

【释义】NP complete概念浅析(涵盖:P问题,NP问题,NP完全问题,NP难问题)文章来源地址https://www.toymoban.com/news/detail-484307.html

到了这里,关于NP-Hard?大白话学习P问题、NP问题、NP完全问题和NP难问题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 大白话解析LevelDB: VersionSet

    在 LevelDB 中, VersionSet 类是一个关键的内部组件,负责管理数据库的不同版本。这个类跟踪了所有的 SSTables(排序字符串表)和它们在数据库中的布局。每次对数据库进行修改时(如添加、删除数据),LevelDB 会创建一个新的 Version 对象,这个对象由 VersionSet 管理。 VersionSe

    2024年01月19日
    浏览(47)
  • 设计模式大白话——策略模式

    一、概述 ​ 从名字上来看,此设计模式的核心是 策略 二字,所谓策略,说白了就是能够针对不同的情况随机应变。接下来我将带你领略策略模式的魅力 二、场景举例 场景描述 ​ 现在有一个游戏,游戏中有各种各样的鸭子,有些鸭子是呱呱叫会用翅膀飞,有些鸭子是嘎嘎

    2024年02月16日
    浏览(44)
  • 用大白话举例子讲明白云计算

    前几天王坚院士在2023云栖大会上发表了关于云计算的演讲,听得我是热血沸腾,王院士称AI和云计算的结合是“云计算的第三次浪潮”,对此我深表认同。但是身边的很多朋友还不知道云计算是什么意思,有些人还认为百度云和百度云盘是一个东西,下面我用大白话举例说明

    2024年02月04日
    浏览(52)
  • 设计模式大白话——适配器模式

    ​ 适配器其实非常好理解,放到生活中来,我们身边处处都有这样的例子,最常见的是用的比较多的各种转接线(如:USB 转 Type-C),有了这个“适配器”,我们就能够将电脑和手机等设备相进行连接,而不需要改动电脑/手机的原有接口。 ​ 回到编程的世界中,假设我们的

    2024年02月10日
    浏览(48)
  • Lighting Network(闪电网络)大白话解析

    通道(Channel),通过在主网宣布通道建立,而后交易双方转至链下交易,把多次交易在链下完成,不占用主网资源,交易完成后在主网广播最终交易结果,无需更改主网机制即可实现吞吐量的提高。 “通道”是一个逻辑上的概念,实际使用过程中并没有“通道”,即使在数据传

    2024年02月04日
    浏览(44)
  • 用大白话举例子讲明白区块链

    什么是区块链?网上这么说: 区块链是一种分布式数据库技术,它以块的形式记录和存储交易数据,并使用密码学算法保证数据的安全性和不可篡改性。每个块都包含了前一个块的哈希值和自身的交易数据,形成了一个不断增长的链条。 区块链的特点包括: 分布式:区块链

    2024年02月04日
    浏览(57)
  • 大白话理解-微信小程序获取授权

    微信用户授权,才可以操作微信官方的某些接口。 简单来说就是:微信定义了很多接口,然后他们认为有一部分是涉及到用户使用安全的,所以把这一部分划分了出来,然后这一部分按照功能来拆开各种范围。于是有了scope列表的东西,scope翻译为中文是范围的意思。(定位属于

    2024年02月02日
    浏览(38)
  • React底层原理分析(简单大白话版本)

    react包 react-dom包 react-reconciler包 scheduler包 Fiber对象 diff算法 深度优先遍历  堆排序 链表,栈操作 react合成事件

    2024年01月20日
    浏览(47)
  • 用大白话来讲讲多线程的知识架构

    感觉多线程的知识又多又杂,自从接触java,就在一遍一遍捋脉络和深入学习。现在将这次的学习成果展示如下。 什么是多线程? 操作系统运行一个程序,就是一个线程。同时运行多个程序,就是多线程。即在同一时间,并行做多件事。 “并行”是相对于我们这些用户来说的

    2024年02月11日
    浏览(45)
  • 大白话说说Docker容器默认网络模型工作原理

    Docker的默认网络模型 —— 桥接模式(Bridge) 当你不做任何特殊设置时,Docker会使用一种叫做“桥接模式”的网络设置。这就像是给你的容器小房子安装了一个虚拟的桥接网络。这座桥连接着容器和你的电脑(宿主机),还能与外界通信。 虚拟网络桥 :想象一下,在你的电

    2024年02月21日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包