我需要解决NP难题。有希望吗?

templatetypedef

这里有很多的变成是现实世界的问题NP难的如果我们假设PNP,则没有任何多项式时间算法可以解决这些问题。

如果您必须解决这些问题之一,那么是否有希望能够有效地做到这一点?还是只是运气不好?

templatetypedef

如果问题是NP难题,则在PNP的假设下,没有算法可以解决

  • 确定性的
  • 始终对所有输入完全正确,并且
  • 在所有可能的输入上均有效。

如果您绝对需要上述所有保证,那么您就很不幸了。但是,如果您愿意为缓解这些约束中的一些问题找到解决方案,那么仍然很有希望!这里有一些可供考虑的选择。

选项一:近似算法

如果问题是NP -hard并且PNP,则意味着没有一种算法可以始终有效地在所有输入上产生完全正确的答案。但是,如果您不需要确切的答案怎么办?如果您只需要接近正确的答案怎么办?在某些情况下,您可以使用近似算法来抵抗NP硬度。

例如,NP难题的一个典型示例旅行商问题在此问题中,将为您提供代表运输网络的完整图形作为输入。图中的每个边都有关联的权重。目标是找到一个循环,该循环恰好遍历图中的每个节点,并且总权重最小。如果边权重满足三角形不等式(也就是说,从点A到点B的最佳路线始终是遵循从点A到点B的直接链接),那么您可以找回一个成本最大为3的循环/ 2通过使用Christofides算法最优

作为另一个示例,已知0/1背包问题NP难题在此问题中,将为您提供一个袋子和一组具有不同权重和值的对象。目的是在不超过袋子重量限制的情况下,将最大的物品装进袋子。即使在最坏的情况下计算精确答案需要指数时间,也可以在多项式时间中以任意精度近似正确答案。(执行此操作的算法称为完全多项式时间近似方案或FPTAS)。

不幸的是,我们确实对某些NP难题的逼近度有一些理论上的限制前面提到的Christofides算法给出了TSP的3/2近似值,其中边服从三角形不等式,但是有趣的是,有可能表明,如果PNP,则TSP的多项式时间近似算法不会在任何常数内最佳因素。通常,您需要进行一些研究,以了解更多关于哪些问题可以很好地近似而哪些不能解决的问题,因为许多NP难题可以很好地近似而很多不能解决。似乎没有统一的主题。

选项二:启发式

在许多NP难题中,诸如贪婪算法之类的标准方法不一定总能得出正确的答案,但通常在“合理”的输入上做得相当好。在许多情况下,启发式方法解决NP难题是合理的启发式方法的确切定义因上下文而异,但是通常,启发式方法要么是解决问题的方法,但“经常”以有时会给出错误答案为代价来提供良好答案,或者是有助于解决问题的有用经验法则即使可能并不总是以正确的方式指导搜索,也可以加快搜索速度。

作为第一种启发式方法的示例,让我们看一下图形着色问题给定一个图形,NP难题要求找到绘制图形中的节点所需的最小颜色数,以使边缘的端点没有相同的颜色。事实证明,这是用许多其他方法解决的特别棘手的问题(最著名的逼近算法具有可怕的界限,并且不怀疑具有参数化的高效算法)。但是,有许多用于图形着色的启发式方法在实践中效果很好。许多贪婪的启发式着色存在用于以合理的顺序为节点分配颜色的方法,并且这些启发式方法在实践中通常做得很好。不幸的是,有时这些启发式方法会给出可怕的答案,但前提是该图不是从病理角度构造的,启发式方法通常可以正常工作。

作为第二种启发式方法的示例,查看SAT求解器会很有帮助。布尔可满足性问题SAT是第一个被证明是NP难的问题该问题要求给定一个命题公式(通常以合取正态形式编写),以确定是否存在一种将变量赋值的方法,以使整个公式的计算结果为true。在许多情况下,现代SAT求解器通过使用启发式方法来指导他们对可能的变量赋值的搜索,在解决SAT方面变得非常擅长。一种著名的SAT解决算法DPLL,基本上会使用启发式方法来加快搜索速度,从而尝试所有可能的赋值来查看公式是否令人满意。例如,如果发现某个变量始终为true或始终为false,则DPLL将尝试使用该变量的强制值,然后再尝试其他变量。DPLL还会找到单位子句(只有一个文字的子句),并在尝试其他变量之前设置这些变量的值。这些启发式方法的最终结果是,即使已知DPLL具有指数最坏情况的行为,其在实践中最终也会非常快。

选项三:伪多项式时间算法

如果PNP,则在多项式时间内无法解决NP难题。但是,在某些情况下,“多项式时间”的定义不一定符合多项式时间的标准直觉。从形式上来讲,多项式时间是指指定输入所需的位数的多项式,它并不总是与我们认为输入的内容保持同步。

例如,考虑设置分区问题在此问题中,将为您提供一组数字,并且需要确定是否有一种方法可以将该集合分为两个较小的集合,每个集合具有相同的总和。天真的解决方案在时间O(2 n)内运行,并且仅通过蛮力测试所有子集即可起作用。但是,通过动态编程,可以在时间O(nN)中解决此问题,其中n是集合中元素的数量,N是集合中的最大值。从技术上讲,运行时O(nN)不是多项式时间,因为数值N仅以对数2 N位写出,但是假设N的数值不太大,则这是一个非常合理的运行时。

该算法称为多项式时间算法,因为运行时O(nN)看起来像多项式,但从技术上讲,其输入大小是指数级的。许多NP难题,尤其是涉及数字的NP问题,都接受伪多项式时间算法,因此,假设数字值不太大,就很容易解决。

有关伪多项式时间的更多信息,请查看有关伪多项式时间的这个较早的Stack Overflow问题

选项四:随机算法

如果问题是NP- hard且PNP,则没有确定性算法可以在最坏情况的多项式时间内解决该问题。但是,如果我们允许引入随机性的算法会发生什么呢?如果我们愿意解决一个对期望值能够给出良好答案的算法,那么我们通常会在很短的时间内得到NP难题的相对较好的答案

例如,考虑最大割问题在此问题中,您将获得一个无向图,并希望找到一种方法将图中的节点分为两个非空组A和B,并使两个组之间的边数最大化。这在计算物理中有一些有趣的应用程序(不幸的是,我一点都不了解它们,但是您可以仔细阅读本文以获取关于此的一些详细信息)。已知此问题是NP困难的,但是有一个简单的随机近似算法。如果只是将每个节点完全随机地分成两组之一,那么最终得到的削减将在最佳解决方案的50%之内。

回到SAT,许多现代SAT求解器使用某种程度的随机性来指导寻找满意的作业。WalkSAT和GSAT算法,例如,通过选择当前未满足一个随机的条款,并试图通过翻转某些变量的真值,以满足它的工作。这通常会引导搜索朝着令人满意的任务方向发展,从而使这些算法在实践中运行良好。

事实证明,关于使用随机算法解决NP难题的能力存在很多开放的理论问题如果您感到好奇,请查看复杂性类BPP及其与NP关系的开放性问题

选项五:参数化算法

一些NP难题会吸收多个不同的输入。例如,长路径问题将一个图形和一个长度为k的输入作为输入,然后询问图形中是否存在一个长度为k的简单路径。子集和问题作为输入采用一组数字和一个目标数k,然后询问是否有这么的dds高达恰有k个数字的一个子集。

有趣的是,在长路径问题的情况下,有一种算法(颜色编码算法),其运行时间为O((n 3 log n)·b k),其中n是节点数,k是长度请求的路径,并且b是一些常数。该运行时间在k中是指数级的,但在节点数n中只是多项式。这意味着如果k是固定的并且事先已知,则算法的运行时间仅是节点数的函数,即O(n 3log n),这是一个很好的多项式。同样,在子集和问题的情况下,有一种动态编程算法,其运行时间为O(nW),其中n是集合中元素的数量,W是这些元素的最大权重。如果W预先固定为某个常数,则此算法将在时间O(n)上运行,这意味着可以在线性时间内精确求解子集和。

这两种算法都是参数化算法的示例,是用于解决NP难题的算法这些难题将问题的难度分为两部分-一个“难题”部分,该问题取决于问题的某些输入参数,而另一个“难题”部分与输入的大小适当地缩放。当所讨论的参数较小时,这些算法可用于找到NP难题的精确解例如,上面提到的颜色编码算法已被证明在计算生物学中非常有用。

但是,某些问题被推测为没有好的参数化算法。例如,怀疑图形着色没有任何有效的参数化算法。在存在参数化算法的情况下,它们通常非常有效,但是您不能依靠它们解决所有问题。

有关参数化算法的更多信息,请查看此先前的Stack Overflow问题

选项六:快速指数时间算法

指数时间算法的伸缩性不好-它们的运行时接近100或200个元素的输入的生命周期。

如果您需要解决NP难题,但您知道输入值相当小(例如,输入值可能在50到70之间),该怎么办。标准的指数时间算法可能不会足够快地解决这些问题。如果您确实确实需要确切解决问题的方法,而此处的其他方法不能解决问题,该怎么办?

在某些情况下,存在针对NP难题的“优化”指数时间算法这些算法的运行时间是指数的,但不像天真的解决方案那样指数。例如,针对3色问题的简单指数时间算法(给定一张图,确定是否可以为三种颜色中的一种着色节点,以使边缘的端点没有相同的颜色)可以检查每种可能的着色方式图中的节点,测试它们是否为3色。共有3 n种可能的方法,因此在最坏的情况下,该算法的运行时间为O(3 n·poly(n))用于一些小的多项式poly(n)。但是,使用更巧妙的技巧和技术,有可能开发出时间为O(1.3289 n)的3色性算法这仍然是一个指数时间算法,但是它是一个更快的指数时间算法。例如3 19约为10 9,因此,如果一台计算机每秒可以进行十亿次操作,则它可以使用我们最初的蛮力算法来(大致而言)求解在一秒钟内最多有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硬度,通常也可以取得进步

希望这可以帮助!

本文收集自互联网,转载请注明来源。

如有侵权,请联系 [email protected] 删除。

编辑于
0

我来说两句

0 条评论
登录 后参与评论

相关文章

8个难题可解决性规则对任何目标状态都有效吗?

如何解决我的代码来解决这个难题?(蟒蛇)

需要知道如何解决这个算法难题

早日解决/拒绝后我需要返回吗?

早日解决/拒绝后我需要返回吗?

我需要阻止用户编辑新闻HTML区域的任何人有解决方案吗?

当Resharp说“无法修改文档”时,我需要一个解决方法。有人知道为什么这样做以及如何解决吗?

我需要使用 underscore.js 旋转数组的矩阵元素。我有解决方案,但代码很大,我想缩短它吗?

解决8难题的BFS的Python实现需要很长时间才能找到解决方案

我想更新数据库中的 50000 条记录,需要 2 分钟,有人有更好的解决方案吗?

JBoss:如果我有 WildFly,我需要 Fuse 吗?

如果我有 Visual Studio,我需要 SSDT 吗?

序列覆盖-解决难题

解决Prolog中的难题

我正在连续执行 3 个 foreach 循环并且花费了很多时间?有没有更好的方法来解决这个难题?

我的dGPU(Nvidia GTX 880M)看起来已经死了,有希望吗?

删除一行后,我希望主键再次从 1 开始。所以有可能吗

有人可以帮我解决这个错误吗?

我创建了向导,我希望它始终位于中心位置,有人可以帮助我吗?

我需要帮助解决我的功能问题,我的所有答案都为零

我需要STUN吗?

我需要退订吗?

我需要显卡吗?

我需要bindActionCreators吗?

我需要评估吗?

我需要解决这个测验

我需要InlineDateFormat解决步骤

解决序言中的难题-生成具有约束的解决方案?

学术难题:没有自我加入的派生比例