NP-hard概念

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


NP-hard问题

NP(Non-deterministic Polynomial)-hard problem

一、预备知识

1.多项式
多项式定义:就是一元 n n n次方式

2.时间复杂度
表明问题扩大后,程序需要的时间长度增长地有多快。
(1)多项式级的复杂度:eg. O ( 1 ) O(1) O(1), O ( l o g n ) O(log n) O(logn), O ( n a ) O(n^a ) O(na),时间复杂度为多项式的问题都很容易解出来.
(2)非多项式级的:eg. O ( a n ) O(a^n) O(an), O ( n ! ) O(n!) O(n!)

3.约化
一个问题A可以约化为B的含义是,可以用问题B的解法解决问题A。

二、基础概念

问题定义:

P问题:一个问题可以在多项式 ( O ( n k ) ) (O(n^k)) (O(nk))的时间复杂度内解决(简单的问题);
例如:n个数的排序问题(不超过 O ( n 2 ) O(n^2) O(n2)

NP问题: 一个问题的解可以在多项式的时间内被证实或证伪,即给出一个答案,可以很快地(在多项式时间内)验证这个答案是对的还是错的,但是不一定能在多项式时间求出正确的解;
例如: 背包客问题,任何一条路线方案都可以很快地被计算代价,但是无法在多项式时间内求出最优解。

NP-hard问题: 假设存在这样一个问题,
1)任意np问题都可以在多项式时间内约化为该问题;
2)解决了该问题就解决了NP问题;这个问题就是NP-hard问题;
为了解决问题A,先将问题A约化为另一个问题B , 解决问题B同时也间接解决了问题A。问题B就是一个NP-hard问题;
范围: 无多项式时间求解算法且不一定能在多项式时间内验证解的问题
例如,停机问题。

NPC问题:
理解一:如果存在一个问题可以在多项式时间内验证解的正确性,其他问题也可以约化为该问题,解决了该问题就解决了NP问题,该问题就是NPC问题。
理解二: 存在这样一个NP问题,所有的NP问题都可以约化成它。换句话说,只要解决了这个问题,那么所有的NP问题都解决了。
其定义要满足2个条件:
1) 首先它是一个NP问题;
2) 然后所有的NP问题都可以约化到它。

范围: NPC问题既是NP问题,也是NP-hard问题。
np-hard问题是什么,理论和算法,算法文章来源地址https://www.toymoban.com/news/detail-595671.html

到了这里,关于NP-hard概念的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

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

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

相关文章

  • 【简述】【图】P类问题、NP类问题、NP完全问题和NP难问题

    1. P类问题(Polynomial Problem)          P类问题 是指 一类能够用确定性算法在多项式时间内求解的判定问题 。其实,在非正式的定义中,我们可以把那些在多项式时间内求解的问题当作P类问题。 2. NP类问题(Non-deterministic Polynomial Problem)         NP类问题不是非P类问

    2024年02月09日
    浏览(41)
  • 基于组合优化的3D家居布局生成看千禧七大数学难题之NP问题

    本文探讨了运筹学和组合优化方法在3D家居布局生成中的应用,并调研了AI生成3D场景布局的最新方法。文中结合了家居家装业务的实际应用场景,从算法建模和计算复杂度的角度上阐述了室内设计的布局问题中存在的难点,以及如何用简化和近似的思想来建模3D布局生成问题

    2024年02月07日
    浏览(38)
  • numpy中的np.random.rand、np.random.randn、np.random.randint、np.random.uniform等用法

    随机数生成方法 1、np.random.rand(d0, d1, …, dn) np.random.rand(d0, d1, …, dn):生成一个指定形状的[0, 1)之间 均匀分布 的随机数数组。参数d0, d1, …, dn指定了生成的随机数数组的维度。 2、np.random.randn(d0, d1, …, dn) np.random.randn(d0, d1, …, dn):生成一个指定形状的**标准正态分布(**平均

    2024年02月09日
    浏览(46)
  • 详述numpy中的np.random.rand()、np.random.randn()、np.random.randint()、np.random.uniform()函数的用法

         目录  (一)np.random.rand()  (二)np.random.randn()  (三)np.random.randint(low,high,size,dtype)  (四)np.random.uniform(low,high,size)         引言:在机器学习还有深度学习中,经常会用到这几个函数,为了便于以后熟练使用,现在对这几个函数进行总结。        

    2023年04月08日
    浏览(46)
  • 【Python】np.maximum()和np.minimum()函数详解和示例

    本文通过函数原理和运行示例,对np.maximum()和np.minimum()函数进行详解,以帮助大家理解和使用。 更多Numpy函数详解和示例,可参考 【Python】Numpy库近50个常用函数详解和示例,可作为工具手册使用 np.maximum() 是 NumPy 库中的一个函数,用于比较两个或更多个数组元素,并返回每

    2024年01月24日
    浏览(41)
  • 【np.bincount】np.bincount()用在分割领域生成混淆矩阵

    混淆矩阵:Confusion Matrix,用于直观展示每个类别的预测情况,能从中计算准确率(Accuracy)、精度(Precision)、召回率(Recall)、交并比(IoU)。 混淆矩阵是 n*n 的矩阵(n是类别),对角线上的是正确预测的数量。 每一行之和是该类的真实样本数量,每一列之和是预测为该类的样本数量

    2023年04月10日
    浏览(51)
  • python中使用numpy包的向量矩阵相乘np.dot和np.matmul

    一直对np的线性运算不太清晰,正好上课讲到了,做一个笔记整个理解一下  在numpy中,一重方括号表示的是向量vector,vector没有行列的概念。二重方括号表示矩阵matrix,有行列。 代码显示如下: 即使[1,2,3]、[[1,2,3]]看起来内容一样 使用过程中也会有完全不一样的变化。下面

    2024年01月25日
    浏览(44)
  • np.random.randint

    np.random.randint 是 Numpy 库中的一个函数,用于生成随机整数。该函数的用法如下: np.random.randint(low, high=None, size=None, dtype=\\\'l\\\') 其中: low:生成的随机整数的下限(包含) high:生成的随机整数的上限(不包含) size:生成数组的形状 dtype:生成数组的数据类型 例如,以下代码生成一

    2024年02月04日
    浏览(40)
  • np.random.normal

    np.random.normal函数是numpy库中用于生成正态分布(也叫高斯分布)随机数的函数。 normal------正态 np.random.normal(loc=0.0, scale=1.0, size=None) 该函数有三个参数:loc, scale, size loc表示随机数的期望值(对应着整个分布的中心)。float ,loc=0说明这一个以Y轴为对称轴的正态分布 scale表示随机数

    2024年02月06日
    浏览(41)
  • np.argmin()函数

    各个参数意义: a :输入数组。 axis :可选参数,默认的是去展平数组,此外就是沿着特定的方向。 out :可选参数,如果被提供,那么结果就会被插入到这个数组中,注意该数组一定要有合适的形状和数据类型。 keepdims :可选参数, True 或者 False 。如果 keepdims 设置为 Fal

    2023年04月23日
    浏览(29)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包