大数据

当前位置:首页 > 大数据

《算法导论》第三十五章

《算法导论》第三十五章 近似算法

许多具有实际意义的问题都是NP完全问题。我们不知道如何在多项式时间内求得最优解。但是,这些问题通常十分重要,我们不能因此而放弃对它们的求解。即使一个问题是NP完全的,也有其解决方法。解决NP完全问题至少有三种方法:1)如果实际输入数据规模较小,则用指数级运行时间的算法就能很好地解决问题;2)对于一些能在多项式时间内解决的特殊情况,可以把它们单独列出来求解;3)可以寻找一些能够在多项式时间内得到近似最优解(near-optimalsolution)的方法(最坏情况或平均情况)。在实际应用中,近似最优解一般都能满足要求。返回近似最优解的算法就称为近似算法(approximation algorithm)。本章主要介绍几个解决NP完全问题的多项式时间近似算法。

近似算法的性能比

假定我们在求解一个最优化问题,该问题的每个可能解都有正的代价,我们希望找出一个近似最优解。根据所要解决的问题,最优解可以定义成具有最大可能代价的解或具有最小可能代价的解。也就是说,该问题可能是最大化问题,也可能是最小化问题。

如果对规模为n 的任意输人,近似算法所产生的近似解的代价C与最优解的代价C"只差一个因子p(n):

QQ截图20220815161249.png

(35.1)

则称该近似算法有近似比p(n)。如果一个算法的近似比达到p(n),则称该算法为p(n)近似算法。近似比和pn)近似算法的定义对求最大化和最小化问题都适用。对于一个最大化的问题,C与C满足0<C<C”,比值C”/C表示最优解代价大于近似解代价的倍数。类似地,对于一个最小化的问题,C与C"满足0<C'≤C,比值C/C表示近似解的代价大于最优解的代价的倍数。因为我们假定所有解的代价都是正的,故前面定义的比值都是良定义的。一个近似算法的近似比不会小于1,因为C/C'<1蕴涵着C/C>1。于是,一个1近似算法9产生的解是最优解,而一个近似比较大的近似算法可能会返回和最优解差很多的解。

对于很多问题,已经设计出具有较小的固定近似比的多项式时间近似算法。然而,对于另一些问题,在其已知的最佳多项式时间近似算法中,近似比是输入规模n的函数,随着n 的变化而变化。35.3节讨论的集合覆盖问题就属于这类问题。

一些NP完全问题可以采用特定的多项式时间近似算法求解,这些算法通过消耗更多的计算时间,可以得到不断缩小的近似比。也就是说,可以用更多的计算时间换取更小的近似比。35.5节讨论的子集和问题就属于这类问题。这类问题非常重要,值得专门研究。

一个最优化问题的近似模式(approximation scheme)就是这样一种近似算法,它的输人除了该问题的实例外,还有一个值e>0,使得对任何固定的é,该模式是一个(1十e)近似算法。对一个近似模式来说,如果对任何固定的e>0,该模式都以其输入实例规模n的多项式时间运行,则称此模式为多项式时间近似模式

随着e的减小,多项式时间近似模式的运行时间可能会迅速增长。例如,一个多项式时间近似模式的运行时间复杂度可能达到O(n)。在理想情况下,如果e按一个常数因子减小,为了获得预期的近似效果,所增加的运行时间不应超过一个常数因子(尽管这两个常数因子不一定相同)。

对一个近似模式来说,如果其运行时间表达式既为1/e的多项式,又为输入实例规模n的多项式,则称其为完全多项式时间近似模式。例如,近似模式的运行时间可能是O((1/e)2n3)。对于这样的模式,e的任意常数倍减少可以引起运行时间相应常数倍的增加。


本章概要

本章的前4节介绍一些解决NP完全问题的多项式时间近似算法的例子,第5节给出一个完全多项式时间近似模式。35.1节以对顶点覆盖问题的研究开始。顶点覆盖问题是一个NP完全的最小化问题,其近似算法的近似比为2。35.2节研究了旅行商问题的特例,其代价函数要求满足三角不等式,给出了一个近似比为2的近似算法。这一节还证明了如果代价函数不满足三角不等式,则对任意常数p≥1,不存在p近似算法,除非P=NP。35.3节说明对集合覆盖问题,如何使用贪心方法设计一个有效的近似算法来获得一-个覆盖,其代价在最差情况下比最优代价大对数倍。35.4节给出另外两个近似算法。首先研究3-CNF可满足性问题的最优化形式,并给出一个简单的随机化算法,它给出的解具有预期的近似比8/7。接着,分析顶点覆盖问题的一个带权值的变形,并说明如何利用线性规划方法设计一个2近似算法。最后,35.5节给出子集和问题的一个完全多项式时间的近似模式。


相关内容

文章评论

表情

共 0 条评论,查看全部
  • 这篇文章还没有收到评论,赶紧来抢沙发吧~