没有合适的资源?快使用搜索试试~ 我知道了~
网址:http://www.elsevier.nl/locate/entcs/volume61.html19页参数化的复杂性:主要思想与实际计算的Michael R.研究员1纽卡斯尔大学电气工程与计算机科学学院,UniversityDrive,Callaghan 2308,Australia1介绍近年来,复杂性分析的参数化框架和相应的算法设计方法的研究迅速发展这导致了最近的一系列调查,所有这些调查都是好的介绍性材料的来源[Ra97,Nie98,DF99,DFS99,A GN01,Gr01a,Gr01b]。也可以参考专著[DF98]。FPT算法的实现经验在[HGS 98,St00,AGN01]中描述。 在某些情况下,这些实现现在为众所周知的NP-困难问题提供了最佳的可用算法。本综述的第一部分试图总结参数化复杂性的主要思想,并对整个程序进行透视。调查的第二部分是关于描述的桥梁数学和实际的计算策略,和多项式时间近似算法。2参数化复杂性参数化复杂性的主要思想在这里被组织成两个讨论:基本的经验动机。停机问题的形式提供的视角。2.1经验动机:固定参数复杂性大多数自然的计算问题都是由各种信息组成的输入来定义的一个简单的例子是由许多图形问题提供的,这些图形问题被定义为具有由图形G = (V; E )和正整数 k组成的输入,例如(定义参见 [GJ79]),图形亏格,带宽,1电子邮件地址:mfellows@cs.newcastle.edu.auc2002年由Elsevier Science B出版。V.CC BY-NC-ND许可下的开放访问。2nk+1最小割线性排列,独立集,顶点覆盖和控制集。最后两个问题的定义顶点覆盖输入:图G =(V; E)和正整数k。问题:G是否有一个大小不超过k的顶点覆盖?(顶点覆盖是一组顶点V0V,使得对于每条边uv 2 E,u 2 V0或v 2 V0。支配集输入:图G =(V; E)和正整数k。问题:G是否有一个大小不超过k的控制集? (A支配set是顶点V0V的集合,使得对于某个v 2 V 0,8u 2 V:u 2 N[v]。虽然这两个问题都是NP完全的,但输入参数k以两种不同的方式对这两个问题的复杂性做出了贡献(i) 经过许多轮的改进,包括各种巧妙的想法,最著名的顶点覆盖算法运行时间为O(1:271 k + kn)[CKJ99]。 该算法已经实现,并且对于无限大小的n和高达约400的k是非常实用的[HGS 98,St00,DRST 01]。(ii) 最著名的支配集算法仍然只是尝试所有k-子集的蛮力算法。对于n个顶点的图,这种方法的运行时间为O(nk +1)。下表显示了这两种复杂性之间的对比。n 为50 n=100 n=150K = 2个6252,5005,625K = 3个15,625125,000421,875K = 5个390,6256,250,00031,640,625K =10个一比九1012九点八分1014三比七1016K =20个一比八1026九点五1031二比一1035之比2kn表1对于n和k的各种值。3为了形式化地说明顶点覆盖和支配集之间的区别,我们给出了以下基本定义。定义2.1参数化语言L是子集L. 如 果 L是一个参数化语言,并且(x; y)2 L,那么我们将把x作为主要部分,把y作为参数。参数可以是非数值的,也可以是各种信息的集合。4定义2.2参数化语言L是乘x参数易处理的,如果它可以在时间f(k)q(n)中确定是否(x; k)2L,其中jxj = n,q(n)是n中的多项式,并且f是函数(无限制)。定义2.3参数化语言L是加性x参数易处理的,如果它可以在时间f(k)+q(n; k)中确定是否(x; k)2L,其中jxj = n,q(n; k)是n和k中的多项式,并且f是函数(无限制)。作为练习,读者可能希望证明参数化语言是可加性xed参数易处理的,当且仅当它是可乘性xed参数易处理的。这强调了xed参数的易处理性如何干净地将计算困难隔离在参数的复杂性贡献中。参数自然产生的方式有很多,例如:数据库查询的大小。通常情况下,数据库的大小是巨大的,但经常查询是小的。如果n是关系数据库的大小,k是查询的大小,那么回答查询可以在O(nk)的时间内解决。已知该问题不太可能是FPT [DFT96、PY97]。逻辑表达式的嵌套深度。ML编译器工作得相当好。编译器必须解决的问题之一是检查类型声明的兼容性。这个问题对于确定性指数时间是完全的[HM 91],所以从经典复杂性理论的角度来看,情况似乎很可怕 这些实现在实践中运行良好,使用了以前被称为启发式的算法,因为|我们现在可以|ML类型检查问题通过FPT算法解决,运行时间为O(2 k n),其中n是程序的大小,k是类型声明的最大嵌套深度[LP85]。由于通常k <10,该算法显然是实用的.生物信息学多分子序列比对中的序列数。 通常,该参数在k的范围内50.问题时间复杂度为O(nk)。这是目前一个悬而未决的问题,是否这个问题是固定大小的字母F P T [BDFHW 95]。实际并行处理系统中处理机的数目。这通常在k 64的范围内。有没有一个实用而有趣的并行FPT理论?最近的两篇论文已经开始探索这一领域(从非常不同的角度)是[CDiI97]和[DRST01]。逻辑公式中的变量数,或逻辑公式中的步骤数。演绎过程近年来,人们对参数化复杂性在逻辑程序设计和人工智能中的应用进行了初步的研究,但仍有许多未被探索的地方。 是FPT来确定k步的解决方案是否足以证明一个公式是不满意的?运动规划问题的步数其中该描述5如果地形的大小为n(因此限制了每一步的移动选项的数量),我们可以在O(nk+1)的时间内解决这个问题。是否有重要类别的运动规划问题,是xed参数处理?对这个问题的探索几乎没有开始[CW95]。一局棋中走的步数。 这里通常的计算问题是确定参与人是否有获胜策略。虽然大多数这类问题都是经典的PSPACE-完全问题,但当通过获胜策略的移动次数进行参数化时,已知一些问题是FPT,而另一些问题可能不是FPT[ADF 95]。输入游戏描述的大小n通常决定了任何一步可能的移动数,因此有一个简单的O(nk)算法,它只是彻底检查了k步游戏树。 这可能是一个非常富有成果的领域,因为游戏被用来模拟许多不同的情况。下部结构的尺寸。复杂度类#P关注的是问题的解决方案的数量(例如,图中哈密尔顿回路的数目或完美匹配的数目)可以在多项式时间内计数。考虑是否可以在FPT时间内计数(或生成)小的子结构将是有趣的长度为k的电路或k匹配)。这一主题才刚刚开始探索[Ar00,Fe01]。一个\dual”参数。一个图有一个大小为k的独立集当且仅当它有一个大小为nk的顶点覆盖。许多问题都有这样一个自然的对偶形式,并且几乎是一个”普遍的规则“,首先由Raman指出,NP-hard问题的参数化复杂性具有互补的参数化复杂性(一个是FPT,另一个是W [1]-hard)[KR 00,AFMRRRS 01]。例如,nk支配集是FPT,n k图着色也是FPT。无关的参数。由于世界的原因,我们可能会遇到一个输入图G以及一个小的顶点集,这是G中的支配集,并需要计算最佳带宽布局。这个问题是否是FPT是开放的。这类问题最近开始在参数化复杂性文献中受到关注[Cai01]。隐藏结构与计算复杂度的相关性将在x2中进一步讨论。距离有保证的解决方案。Mahajan和Raman指出,对于许多问题,可以保证具有某个“中间”值(就n而言)的解决方案,然后将其参数化高于或低于保证值是有趣的[MR 99]。举一个简单的(开放的)例子,根据四色定理,一个平面图必须有一个大小至少为n=4的独立集。判定一个平面图是否有一个大小至少为n=4+ k的独立集是FPT问题的输入或输出中的“污垢”量。 例如,我们可能有一个图着色的应用程序,其中输入预计是2-可着色的,除了由于一些缺陷,输入实际上是6只有\“接近”2-可着色。 这将是感兴趣的,以确定是否可以适当地着色图,以这种方式,最多k个顶点接收第三种颜色。一些结果表明,问题可能是FPT[CS97],但这仍然是一个悬而未决的问题。一个问题的解决方案的“鲁棒性”,或者说与解决方案的距离。例如,给定边加权图中最小生成树问题的解决方案,我们可以询问解决方案的成本是否在边成本的所有增加下都是鲁棒的,其中参数是成本增加的总量。蔡雷真[Cai01]最近考虑了许多这类问题距离改进的解决方案。局部搜索是启发式算法设计的重要组成部分。其基本思想是保持当前的解决方案,并迭代移动到相邻的“更好”解决方案的过程。一个相邻的解决方案通常被定义为一个单一的步骤,根据一些小的编辑操作之间的解决方案。下面的问题对于这些情况来说是完全通用的,并且可能提供用于“加速”本地搜索的有价值的子例程:k-加速本地搜索输入:解决方案S,k。参数:k输出:最佳解决方案S0 即在S的k个编辑操作内。探索TSP的k-变化邻域是FPT吗?近似的好处。也许“处理NP完全性”[GJ79]的最重要的策略是多项式时间近似程序。近似的优度是一个直接相关的参数。更多关于X3很明显,现实世界中充满了由各种参数控制的具体问题,这些参数的范围很小或适中。如果我们能为这些问题设计出运行时间为2k n的算法,那么我们可能会有一些真正有用的东西。下面的定义为我们提供了一个地方,可以放置所有那些对于xed k”在多项式时间内可解的问题,而不需要对这个xed k”是否以指数结束进行定义2.4参数化语言L属于类XP(分片P),如果它可以在时间f(k)ng(k)中确定(x; k)2L是否是与n和k都无关的常数,其中jxj= n,f和g是无限制函数。FPT是否可能= XP?这是目前有答案的关于参数化复杂性的少数结构性问题之一[DF98]。定理2.5 FPT是XP的一个真子集.72.2停机问题:一个中心参考点对可计算性和有效可计算性的主要研究与停机问题的三种基本形式有关。(i) 停机问题输入:图灵机M.问:如果M在一个空的输入带上启动,它会停止吗?(ii) 非确定图灵机的多项式时间停机问题输入:一个不确定的图灵机M。问题:M是否可能在n步中达到一个停止状态,其中n是M的描述的长度(iii) 不确定图灵机的k步停机问题输入:一个不确定图灵机M和一个正整数k。(The可以在计算的任何步骤处进行的转换的数量是无限的,并且字母表的大小也是不受限制的参数:k问题:M是否可能在最多k步内达到停止状态停止问题的第一种形式对于研究这个问题很有用我的问题有算法吗?“停机问题的第二种形式已被证明是有用的近30多年来处理这个问题:有没有算法可以解决我的问题...比如排序和矩阵乘法“停机问题的第二种形式是平凡的NP-完全的,实际上本质上定义了复杂性类NP。对于一个具体的例子,为什么它是平凡的NP完全的,考虑3色问题的图,并注意它是多么容易减少到P时间NDTM停机问题。给定一个要确定3-可着色性的图G,我只需创建以下不确定性算法:第一阶段。(如果G有n个顶点,则这里有n行代码。)(1.1)颜色顶点1三种颜色之一非确定性。(1.2)颜色顶点2三种颜色之一非确定性。...(1.n)三种颜色之一的颜色顶点。第二阶段。检查颜色是否正确,如果正确,请停止。否则进入一个在夜间循环。很容易看出,上述非确定性算法有可能在m个步骤中停止(对于大小为m的适当填充的图灵机描述),当且仅当图G允许3-着色。将任何其他问题2NP简化为P-时间NDTM停止问题不再困难8而不是把问题属于NP的论点,稍微修改一下,把它简化成这种形式的停机问题。从这个意义上说,P时间NDTM停机问题本质上是NP的定义问题。P6 = NP的猜想在直觉上是非常有根据的。停机问题的第二种形式似乎需要指数时间,因为除了彻底探索可能的计算路径之外,我们似乎无法分析非结构化非确定性。除了20年来积累的习惯,这种具体的直觉是经典复杂性理论的基本参考点。当问题是:有没有算法可以解决我的问题...就像顶点覆盖一样“停止问题的第三种形式是讨论的基础。这个问题将越来越多地和不可避免地被要求为任何NP-难的问题,其中小参数范围是重要的应用。通过穷尽地探索可能的计算路径的n-分支,深度-k树,它在时间上是平凡可解的,并且我们在这里的直觉本质上与停止问题的第二种形式相同。|这是无法改善的。停机问题的第三种形式定义了参数化复杂性类W [1]。因此W [1]与NP非常强地相似,并且FPT 6= W [1]的猜想与P 6=NP的猜想一样合理。适当的减少概念如下。定义2.6从参数化语言L到参数化语言L的 是一种算法,它从由apai r(x;k),apa i r(x0;k0)such组成的输入计算:(i) (x;k)2L当且仅当(x0;k0)2L0,(ii) k0=g(k)是仅关于k的函数,并且(iii) 计算在时间f(k)n内完成,其中n = j × j是与n和k都无关的常数,并且f是任意函数。W [1]的硬度是参数化问题不太可能是FPT的工作标准。k-团问题是W[1]-完全的,并且经常为W [1]-困难性的证明提供一个方便的起点.参数化复杂性的主度序列是FPT美国[1]XP参数难处理性的结构理论仅仅是一个最基本的开端。 任何对这一领域感兴趣的人都应该把最近的工作Flum和Grohe作为一个基本的参考[FG01],以及在[DF98]中阐述的一些调查。93与实用计算和启发式的什么是实用计算?Karsten Weihe在《论实用与应用的区别》一文中对这一被忽视的问题作了发人深省、富有启发性(和有趣)的叙述。关键的问题是:实际的计算实现必须处理的实际输入是什么在考虑实际计算的“战争故事”时,例如Weihe报道的,我们很快被迫放弃真实输入(对于大多数问题)将占据我们数学建模的定义空间的想法。一般的规则是,真实的输入不是随机的,而是有很多隐藏的结构,这些结构可能没有熟悉的名称或概念,即使你知道隐藏的结构是什么。 Weihe描述了一个关于欧洲火车系统的问题。 考虑一个二分图G =(V; E),其中V被二分为两个集合S(车站)和T(列车),其中一条边表示列车t在车站s停靠。 相关的图是巨大的,大约有10,000个顶点。 问题是计算最小站数S0所以每一列火车都停在S0 的 一个 车站. 很容易看出,这是一个特殊情况下的命中集问题,因此是NP-完全的。此外,它也是W [1]-困难的,所以参数化复杂性程序的直接应用似乎也失败了。然而,以下两个归约规则可以应用于简化(预处理)问题的输入。在描述这些规则时,设N(s)表示在车站s停靠的列车集合,设N(t)表示车站集合 列车T在此停靠。(i) 如果N(s)N(s0),则删除s。(ii) 如果N(t)N(t0),则删除t0。这些简化规则的应用级联,在每一步都保留足够的信息以获得最优解。Weihe发现,值得注意的是,这两个简单的归约规则足够强大,可以将原始的巨大输入图“消化”成一个由大小不超过50的不相交组件组成的问题核。|小到足以允许问题通过蛮力来最佳地解决。请注意,在同一时间,我们在这里有一个多项式时间常数因子近似算法,让我们在一个50倍的最优的,比如说,O(n2)时间,只是通过采取所有的顶点在内核组件。Weihe的例子展示了一种普遍适用的应对困难问题的策略:智能预处理。不对NP难问题进行预处理是愚蠢的,即使下一阶段是模拟退火、神经网络、漫游蚂蚁、遗传、模因或厨房水槽。在10准确地说,这正是xed参数易处理性的全部意义。以下是FPT的等效定义[DFS 99]。定义3.1参数化语言L是可核化的,如果存在L到自身的参数化变换满足:(i) (x;k)in到(x0;k0)的变换的运行时间,其中 jx j=n,被限制在多项式q(n; k)(因此实际上这是L到其自身的多项式时间变换,经典地考虑,尽管具有参数简化的附加结构),(ii) k0k,以及(iii) j x0jh(k),其中h是任意函数。引理3.2参数化语言L是xed参数易处理的当且仅当它是可核化的。Weihe的例子看起来像一个FPT内核化,但是参数是什么呢作为一个思想实验,让我们定义一个二分图G的K(G)为G的一个分支的最大尺寸时,G是根据上述两个简单的约简规则。显然,尽管这看起来是人为的,但对于参数K(G),可以在FPT时间内最优地求解命中集我们可以将这个新的易处理的命中集参数化添加到已知的事实中,即命中集可以在FPT中针对参数树宽进行最优求解。为了说明预处理的强大功能,读者将很容易发现顶点覆盖的归约规则,该规则消除了所有度顶点1. 不那么容易的是证明所有度为3的顶点都可以被消除,留下一个最小度为4的图作为核。该预处理例程产生用于一般顶点覆盖问题的最佳已知的启发式算法(即,没有假设k是小的),并且在顶点覆盖的最著名的FPT算法中也起着核心作用。我们在Weihe的火车问题中看到一个问题的例子,其中自然输入分布(火车系统的图)占据有限的参数范围,但相关参数根本不明显。一个计算过程的输入(例如,Weihe的火车问题)通常是另一个过程(火车系统的建设和运营)的输出,受计算和其他可行性约束的支配。我们可能会合理地接受这样的观点,即真实的计算世界涉及隐藏的结构参数的巨大商业。看起来FPT的定义允许太多的病理学,因为参数函数f(k)可能是任意可怕的。例如,有一个FPT算法用于断点系统发育问题,其中自然参数k取为包含解的(Steiner)树的总成本(The问题的定义对这个讨论并不重要。)在实践中,这通常以k 50为界。该FPT算法的运行时间为f(k)n2,其中f(k)=(k!)3或以上。人们可能11我怀疑这不是一个非常有用的算法。但事实上,我们只是报告了对已经实施的算法的事后分析,该算法经常使用,并且被正确地认为是最先进的[MWBWY00,CJMRWWW00]。这样的例子似乎并不罕见。目前使用的许多“启发式”算法都是针对自然参数和相关参数的FPT算法那些设计FPT算法的人应该记住,他们的f(k)只是他们能够证明的最好的关于最坏情况的分析,并且他们的算法实际上可能比悲观分析表明的更有用,在现实的输入上,特别是如果涉及任何非平凡的核化4一些研究前沿在本节中,我们讨论了参数化复杂性的一些当前研究方向。4.1近似的复杂性在多项式时间近似算法的广泛研究领域中,重点集中在以下概念上:多项式时间常数因子近似算法。多项式时间近似方案。参数化复杂性和多项式时间近似程序之间的联系实际上是非常深入和迅速发展的其中一个原因是,当人们考虑近似方案时,有一个参数立即盯着你的眼睛:近似的好。为了说明可能发生的情况,由于Arora[Ar96],欧几里得TSP的第一个P -时间近似方案在时间O(n35=3)的最优因子(1+)因此,对于20%的误差,时间复杂度为O(n)。参数-在所有的计算理论中,k = 1是最重要和最明显的。我们能从指数中得到k = 1吗? 是一个具体的问题,需要进一步澄清许多已知的P-时间近似方案。以下定义抓住了本质问题。定义4.1一个最优化问题有一个有效的P-时间逼近方案,如果它可以在时间f(k)nc上逼近最优的(1 +)优度,其中c是常数,k = 1=.下面的重要定理首先由Cristina Bazgan在她的硕士论文中证明(独立于Cesati和Trevisan)[Baz95,CT97]。定理4.2假设opt是一个优化问题,param是相应的参数化问题,其中参数是值12v1v2v3FOFFOFvn一个最优的解决方案。 那么param是如果opt有一个有效的PTAS,则xed参数可处理。应用Bazgan定理并不一定困难|我们将在此简述一个最近的例子。Khanna和Motwani以有趣的方式引入了三个平面他们的建议是,优化问题逻辑中的“隐藏平面结构”是允许PTAS开发的原因[KM 96]。他们给出了已知有PTAS的优化问题的例子,这些问题与图无关,但可以简化为这些平面逻辑问题。因此,平面逻辑问题的PTAS\解释”PTAS为这些其他问题。 这是他们的三个之一一般平面逻辑优化问题平面TMIN输入: 乘积和形式的布尔公式的集合,所有字面量为正,其中关联的二分图是平面的(该图对于每个公式都有一个顶点,对于每个变量都有一个顶点,如果变量出现在公式中,则在两个这样的顶点输出:最小权重的真值赋值(即, 最小数量的变量设置为真),满足所有公式。下面的定理是最近的联合工作与蔡,Juedes和Rosamond。定理4.3平面TMIN没有EPTAS,除非FPT = W [1]。证据我们表明,集团参数化约平面TMIN的参数是真值分配的重量由于Clique是W[1]-完全的,因此平面TMIN的参数化形式是W[1]-困难的。首先,让hG; ki是Clique的一个instance。 假设G有n个顶点。从G和k,我们将在f(k)个n个变量的块C将包含至多2f(k)个FOF,并且C的关联图将是平面的。此外,每个FOF中的每个最小项将包含最多4个变量。构造集合C,使得G有大小为k的团当且仅当C有权重f(k)满足赋值,且在每个n个变量的块中恰好有一个变量设置为真因此,时间复杂度为O(k)。为了保持C的关联图的平面性,我们确保每个n个变量的块最多出现在2个FOF中。如果保持这个条件,那么我们可以如下绘制每个n变量块13我们描述了两个阶段的建设。在第一阶段,我们使用k个n个变量的块和k(k1)=2+k个FOFs的集合C0。 在一个满足C 0的分配的w htk中,变量b i = [v i;1 ; v i;n ]的每个c h b l o c k中的恰好一个变量v i ; j将被设置为真。我们将此事件解释为\vertexj是大小为k的团中的第i个顶点。and The k-k-1 =2+ k FOF isused to determine the functions of the functions.“n如下 每1我k,设fi为FOFWv i;j. 这种FOF确保j=1bi中的至少一个变量被设置为真。每对1I
下载后可阅读完整内容,剩余1页未读,立即下载
cpongm
- 粉丝: 5
- 资源: 2万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
最新资源
- C++标准程序库:权威指南
- Java解惑:奇数判断误区与改进方法
- C++编程必读:20种设计模式详解与实战
- LM3S8962微控制器数据手册
- 51单片机C语言实战教程:从入门到精通
- Spring3.0权威指南:JavaEE6实战
- Win32多线程程序设计详解
- Lucene2.9.1开发全攻略:从环境配置到索引创建
- 内存虚拟硬盘技术:提升电脑速度的秘密武器
- Java操作数据库:保存与显示图片到数据库及页面
- ISO14001:2004环境管理体系要求详解
- ShopExV4.8二次开发详解
- 企业形象与产品推广一站式网站建设技术方案揭秘
- Shopex二次开发:触发器与控制器重定向技术详解
- FPGA开发实战指南:创新设计与进阶技巧
- ShopExV4.8二次开发入门:解决升级问题与功能扩展
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功