tem*_*def 22 performance time-complexity np
有许多现实世界的问题,结果证明是NP- hard.如果我们假设P ≠ NP,则对于这些问题没有任何多项式时间算法.
如果您必须解决其中一个问题,您是否有希望能够有效地解决这些问题？或者你只是运气不好？
tem*_*def 71
如果问题是NP- hard,假设P ≠ NP,则没有算法
如果你绝对需要以上所有保证,那么你几乎没有运气.但是,如果你愿意解决问题的解决方案,放松一些这些限制,那么很可能仍然是希望!以下是一些需要考虑的选项.
如果问题是NP -hard且P ≠ NP,则意味着没有算法能够始终有效地在所有输入上产生完全正确的答案.但是,如果你不需要确切的答案怎么办？如果您只需要接近正确的答案怎么办？在某些情况下,您可以使用近似算法来对抗NP硬度.
例如,NP -hard问题的典型例子是旅行商问题.在此问题中,您将获得表示运输网络的完整图表作为输入.图中的每条边都有一个相关的权重.目标是找到一个循环,该循环通过图中的每个节点一次,并且具有最小总重量.在边权重满足三角不等式的情况下(即,从A点到B点的最佳路径始终遵循从A到B的直接链路),那么您可以返回一个成本最多为3的循环./2通过使用Christofides算法进行优化.
作为另一个例子,已知0/1背包问题是NP- hard.在这个问题中,你会得到一个包和一组具有不同权重和值的对象.目标是在不超过行李重量限制的情况下将物品的最大价值包装到行李中.尽管在最坏的情况下计算精确答案需要指数时间,但是可以在多项式时间内将正确答案逼近任意精度.(执行此操作的算法称为完全多项式时间近似方案或FPTAS).
不幸的是,我们确实对某些NP难问题的近似性有一些理论上的限制.前面提到的Christofides算法给出了TSP的3/2近似值,其中边缘服从三角形不等式,但有趣的是,有可能表明如果P ≠ NP,则没有TSP的多项式时间近似算法可以进入任何常数最佳因素.通常,你需要做一些研究,以便更多地了解哪些问题可以很好地近似,哪些问题不可能,因为许多NP难问题可以近似得很好,而很多问题都不能.似乎没有一个统一的主题.
在许多NP- hard问题中,像贪婪的算法这样的标准方法并不总能产生正确的答案,但通常在"合理"的输入上做得相当好.在许多情况下,用启发式方法攻击NP难问题是合理的.启发式的确切定义因上下文而异,但通常启发式是一种解决问题的方法,"通常"会以牺牲错误答案为代价来回馈好答案,或者是一种有用的经验法则.加速搜索,即使它可能并不总是以正确的方式引导搜索.
作为第一种启发式的例子,让我们看看图着色问题.在给定图表的情况下,该NP-硬问题要求找到在图中绘制节点所需的最小颜色数,使得没有边缘的端点是相同的颜色.对于许多其他方法来说,这是一个特别难以解决的问题(最着名的近似算法具有可怕的界限,并且不怀疑它具有参数化的有效算法).但是,图表着色有许多启发式方法,在实践中表现相当不错.存在许多贪婪的着色启发式方法,用于以合理的顺序为节点分配颜色,并且这些启发式方法在实践中通常做得很好.不幸的是,有时这些启发式方法会给出可怕的答案,但如果图形不是病态构建的,那么启发式算法通常可以正常工作.
作为第二种启发式的例子,查看SAT求解器是有帮助的.SAT,布尔可满足性问题,是第一个被证明是NP -hard的问题.问题是,给定一个命题公式(通常以联合正规形式编写),确定是否有一种方法可以为变量赋值,使整个公式的计算结果为真.在许多情况下,现代SAT求解器通过使用启发式方法指导他们搜索可能的变量赋值,在解决SAT方面非常擅长.一个着名的SAT求解算法DPLL基本上尝试所有可能的分配,以查看公式是否可满足,使用启发式方法来加速搜索.例如,如果它发现变量总是为true或总是为false,则DPLL将尝试在尝试其他变量之前将该变量赋值为强制值.DPLL还查找单元子句(只有一个文字的子句)并在尝试其他变量之前设置这些变量的值.这些启发式算法的净效果是DPLL在实践中最终会非常快,尽管已知它具有指数最坏情况的行为.
如果P ≠ NP,则在多项式时间内不能解决NP-硬问题.但是,在某些情况下,"多项式时间"的定义不一定与多项式时间的标准直觉相匹配.从形式上讲,多项式时间是指指定输入所需的位数的多项式,它并不总是与我们认为的输入同步.
例如,考虑设置分区问题.在这个问题中,你给出了一组数字,需要确定是否有办法将集合分成两个较小的集合,每个集合具有相同的总和.这个问题的天真解决方案在时间O(2 n)内运行,并且通过蛮力测试所有子集来工作.但是,通过动态编程,可以在时间O(nN)中解决此问题,其中n是集合中元素的数量,N是集合中的最大值.从技术上讲,运行时O(nN)不是多项式时间,因为数值N仅以log 2 N位写出,但假设N的数值不是太大,这是一个完全合理的运行时间.
该算法称为伪多项式时间算法,因为运行时O(nN)"看起来"像多项式,但从技术上讲,它是输入大小的指数.许多NP难题,特别是涉及数值的问题,允许假多项式时间算法,因此假设数值不是太大,很容易解决.
有关伪多项式时间的更多信息,请查看此早期有关伪多项式时间的Stack Overflow问题.
如果问题是NP -hard且P ≠ NP,则没有确定性算法可以在最坏情况多项式时间内解决该问题.但是,如果我们允许引入随机性的算法会发生什么？如果我们愿意接受能够给出期望值很好的答案的算法,那么我们通常可以在很短的时间内得到相对较好的NP问题答案.
例如,考虑最大切割问题.在这个问题中,您将获得一个无向图,并希望找到一种方法将图中的节点拆分为两个非空组A和B,并在组之间运行最大边数.这在计算物理学中有一些有趣的应用(不幸的是,我根本不理解它们,但你可以仔细阅读本文的一些细节).这个问题已知是NP- hard,但它有一个简单的随机近似算法.如果您只是将每个节点完全随机地投入到两个组中的一个中,那么您最终会得到一个预期的切割,该切割在最佳解决方案的50%之内.
回到SAT,许多现代SAT求解器使用一定程度的随机性来指导搜索令人满意的任务.该WalkSAT和GSAT算法,例如,通过拾取随机子句当前未满足,试图通过翻转某些变量的真值,以满足它的工作.这通常指导搜索到令人满意的分配,使这些算法在实践中很好地工作.
事实证明,使用随机算法解决NP难问题的能力存在许多开放的理论问题.如果你很好奇,请查看复杂性类BPP及其与NP关系的公开问题.
一些NP -hard问题涉及多个不同的输入.例如,长路径问题将图形和长度k作为输入,然后询问图形中是否存在长度为k的简单路径.该子集和问题发生在输入一组数字和一个目标数k,然后询问是否有这么的dds高达恰好有k个数字的一个子集.
有趣的是,在长路径问题的情况下,有一种算法(颜色编码算法),其运行时间为O((n 3 log n)·b k),其中n是节点数,k是长度请求的路径,b是一些常量.这个运行时在k中是指数的,但只是n中的多项式,即节点数.这意味着如果k是固定的并且事先已知,则算法的运行时间作为节点数的函数仅为O(n 3 log n),这是非常好的多项式.类似地,在子集求和问题的情况下,存在动态编程算法,其运行时间为O(nW),其中n是集合的元素的数量,W是这些元素的最大权重.如果W预先固定为某个常数,则该算法将在时间O(n)中运行,这意味着可以在线性时间内精确地求解子集和.
这两种算法都是参数化算法的例子,解决NP问题的算法,将问题的硬度分成两部分 - 一个"硬"部分依赖于问题的一些输入参数,一个"简单"部分根据输入的大小优雅地缩放.当所讨论的参数很小时,这些算法可用于找到NP -hard问题的精确解.例如,上面提到的颜色编码算法已经证明在计算生物学的实践中非常有用.
然而,一些问题被推测为没有任何好的参数化算法.例如,图形着色被怀疑没有任何有效的参数化算法.在存在参数化算法的情况下,它们通常非常有效,但您不能依赖它们来解决所有问题.
有关参数化算法的更多信息,请查看此早期的Stack Overflow问题.
指数时间算法不能很好地扩展 - 它们的运行时间接近宇宙的生命周期,输入小到100或200个元素.
如果你需要解决NP -hard问题怎么办,但是你知道输入相当小 - 比方说它的大小可能在50到70之间.标准的指数时间算法可能不会足够快来解决这些问题.如果你确实需要一个问题的确切解决方案,这里的其他方法不会削减它怎么办？
在某些情况下,NP - hard问题有"优化的"指数时间算法.这些算法的运行时是指数级的,但并不像天真的解决方案那样糟糕.例如,一个简单的指数时间算法用于3着色问题(给定一个图形,确定是否可以为每个三种颜色中的一种颜色着色,使得没有边缘的端点是相同颜色)可能会检查每种可能的着色方式图中的节点,测试它们中的任何一个是否为3色.有3种ñ方法可以做到这一点,所以在最坏的情况下,该算法的运行时间将是O(3 ñ ·聚(n))的一些小多项式poly(N).然而,使用更聪明的技巧和技术,可以开发一种在3时间内运行的可着色的算法(1.3289 n).这仍然是一个指数时间算法,但它是一个更快的指数时间算法.例如,3 19约为10 9,因此如果计算机每秒可以进行10亿次操作,它可以使用我们的初始强力算法(粗略地说)在一秒钟内解决具有多达19个节点的图中的3种可着色性.使用O((1.3289 n)时间指数算法,我们可以在大约一秒钟内解决多达约73个节点的实例.这是一个巨大的改进 - 我们已经增加了我们可以在一秒内处理的大小超过一个因素三个!
作为另一个着名的例子,考虑旅行商问题.对TSP有一个明显的O(n!·poly(n)) - 时间解决方案,它通过枚举节点的所有排列并测试这些排列产生的路径来工作.然而,通过使用类似于颜色编码算法所使用的动态编程算法,可以将运行时间改善为"仅"O(n 2 2 n).鉴于13!大约一十亿,天真的解决方案将让你在大约一秒钟内解决13节点图形的TSP.相比之下,DP解决方案可让您在大约一秒钟内解决28节点图形上的TSP问题.
这些快速指数时间算法通常可用于增加可在实践中精确求解的输入大小.当然,它们仍然以指数时间运行,因此这些方法通常对解决非常大的问题实例没有用.
如果您需要解决NP难问题,请不要绝望!有很多很好的选择可能会让你的棘手问题变得更加平易近人.上述技术中没有一种适用于所有情况,但通过使用这些方法的某些组合,即使面对NP-硬度,通常也可以取得进展.
希望这可以帮助!