参数计算导论
第1章导引
第1章导引
城市A由三个城区B、C、D构成，由于城区B离市中心较远，其犯罪率比较高，经常有偷盗、抢劫等案件发生。为了创建文明城市，市政府决定对城区B加强治安管理，采取的措施是在某些交叉路口处安装监控设备实现对整个城区的道路实时监管。为了节约成本，市政府要求安装最少的监控设备实现对整个城区道路的监管。市政府决定对该项目进行公开招标，要求投标公司给出节约成本的具体解决方案。在投标这一天，三家公司对该项目抱有极大的兴趣，前来投标。市政府投标主持人说：“大家好，今天对城区B的交叉路口监控设备安装项目进行投标。我们市的城区B一共有n个交叉路口，请问在k个交叉路口安装监控设备能否实现整个城区的监管？请各公司的相关负责人讲述自己的解决方案，哪个方案能够节约成本，并且工期合理，将获得城区B的监控设备安装项目。”公司1的负责人说：“既然城区B一共有n个交叉路口，我们的策略是对任意k个交叉路口都试一下，确定在这k个交叉路口安装监控设备能否实现整个城区的监管。这样，一定能够找到成本最少的方案。”公司2的负责人说：“公司1提出的方案我们也考虑过，但是从n个交叉路口中把所有的k个交叉路口都试一遍，工期太长。我们的方案是，对于任意一条没有被监控的道路，在道路的两个路口处都装上监控设备。基于该策略，最后所有的道路都可以被监管。成本可能会增加一倍，但优点是工期很短。”公司3的负责人说：“我们观察到，要实现对城区B的监管，在城区B中安装监控设备的交叉路口数不超过60。我们的方案是，对于任意一条没有被监控的道路L，假设道路L的两个路口为a、b，要么在路口a安装一个监控设备，要么在路口b安装一个监控设备。找到所有的安装在k个交叉路口的可能性，确定在k个交叉路口安装监控设备能否实现整个城区的监管。如果存在k个交叉路口，使得在这些路口安装监控设备能实现整个城区的监管，那么我们的方案能够找到这k个交叉路口且成本最少。另外，我们方案的工期虽然比公司2的方案差，但比公司1的方案好许多倍。”市政府相关负责人听取了三个公司的汇报，考虑了工程的成本和工期，最终决定让公司3负责城区B的监控设备安装。
在上述事例中，如果将每条道路看成一条边，道路两端的交叉路口看成顶点，则城区B的交通道路可以抽象成一个图G=（V，E）。因此，在k个交叉路口安装监控设备能否实现对整个城区监管的问题就变成在图G中找k个点的集合V′，使得对于图G中的任意一条边e，至少e的一个端点被包含在V′中，即参数化点覆盖问题。
定义1.1参数化点覆盖问题。
输入：图G＝（V，E）和正整数k。
输出：一个大小不超过k的点覆盖，或返回G中不存在大小不超过k的点覆盖。
点覆盖问题是一个NP难问题，三个公司提出求解该问题的三种方案。公司1的方案事实上是对点覆盖问题的精确求解，可直接得到时间复杂度为O（nk）的算法，n为给定图的大小。很显然，O（nk）的算法是不能被人们接受的。公司2提出的方案是求解点覆盖问题的近似算法。假设点覆盖问题的解为C。该近似算法可得到一个大小为2|C|的点覆盖，很好地对点覆盖问题进行了近似求解。然而，该近似解并不能满足实际应用的精确性和成本的要求。公司3通过城区B的实际应用背景进行研究，发现城区B中安装监控设备的交叉路口数不超过60。基于这一参数特性，提出时间复杂度为O（2k＋kn）的参数算法，其中n是给定图的大小。不难看出，上述算法实现了对点覆盖问题的精确最优求解。基于对参数k的观察，该算法在人们可接受的时间内求解理论上根本不可能被求解的问题。为了进一步比较一般精确算法与参数算法，下面给出n，k取不同值时，nk与2kn两类算法复杂性之间的明显区别（用值nk-1/2k表示），如表1.1所示。
表1.1n，k为不同值时nk-1/2k的具体数值
参数n=50n=100n=150
k=262525005625
k=315 625125 000421 875
k=5390 6256 250 00031 640 625
k=101.9×10129.8×10143.7×1016
k=201.8×10269.5×10312.1×1035
由此可以看出，对于传统的难解问题，在理论上是根本不可能有效求解的。在实际应用中，可以根据实际应用背景引入某些参数对问题进行重新刻画，而所取参数在实际应用中只在一个小的范围内变化，通过充分利用小参数这一特殊性质，可快速解决相应的难解问题。这正是本书介绍的参数计算理论的基本思想。
下面给出其他例子分析参数计算方法的优越性和可用性。
例1.1二分图受约束点覆盖问题
在超大规模集成电路领域，随着VLSI技术的高度发展和阵列密度的增加，制造过程中缺陷出现的可能性也随之增加。另外，在产品处理阶段，由于集成密度的增大，处理器损坏的可能性也随之增高。为了应对上述问题，人们引入了容错技术。VLSI中容错技术对集成电路的发展有十分重要的意义和应用价值。现在较为常用的容错方法是在存储器内部集成备用行和备用列以替换阵列中有缺陷的行和列。假设用ku表示备用行的数目，用kl表示备用列的数目。上述容错问题可抽象为用ku个备用行和kl个备用列对一个大小为M×N的有缺陷阵列进行修复。
人们将上述问题转化为二分图受约束点覆盖问题。
定义1.2二分图受约束点覆盖问题。
输入：二分图G=（U，L，E）和正整数ku，kl。
输出：两个子集C1U，C2L，满足|C1|≤ku，|C2|≤kl，且使得E中每条边至少有一个端点在C1∪C2中，或返回不存在。
二分图受约束点覆盖问题已被证明是一个难解问题。为了解决该问题，人们提出各式各样的启发式算法和近似算法，但都不能满足实际应用的精确要求。
在超大规模集成电路的实际容错应用中，备用行和备用列的个数之和（ku+kl）通常小于40，该值远小于阵列中的行数和列数。于是，人们引入参数ku和kl对问题重新进行刻画，设计时间复杂度为O（1.182ku+kl）的参数算法，实现了对问题的有效求解。上述算法较好地解决了超大规模集成电路中的容错问题。
例1.2程序类型检测问题
程序类型检测问题是指给定一段ML程序P，问P中类型声明是否一致。该问题在程序设计等领域中有着重要的应用。从难解性的角度来说，该问题比大多数的难解问题（点覆盖、二分图受约束点覆盖等等）难。然而，人们观察到在计算机科学中，程序的嵌套深度一般不超过10。于是，人们以程序嵌套的深度为参数对问题重新进行刻画，使得对于长度为n，嵌套深度为k的程序，程序类型检测问题可在O（2k）时间内求解。可见，通过引入恰当的参数，可以在实际应用中解决一些理论上比难解问题更难的问题。
例1.3单体型组装问题
在生物信息计算中，单核苷酸多态性是一个物种中不同个体表型的主要遗传来源。识别SNP对基因的精确定位，了解基因功能对遗传病等疾病的诊断和药物研究有重要作用。
一个SNP位点指的是在一个物种基因组DNA序列中不同个体可能出现不同碱基的位置。在一条染色体SNP位点上的碱基序列叫做单体型。人类等二倍体生物的染色体是成对存在的，都有一对单体型。
单体型组装问题是指给定某个个体一组已测序的DNA片段数据，要求去掉最小数量的数据，以便发现一对单体型与剩下的数据兼容。
人们先前在此问题的研究中，已经意识到这个问题的难解性，并提出解决这一问题的启发式算法，但效果不好。后来，人们对真实的单体型已有数据进行了研究，发现用目前最流行的DNA直接测序法，一个长度1000bp的片段上的SNP位点数通常在10个以内。另外，片段数据的覆盖度通常在5左右。针对这些真实生物数据的特点，以SNP位点数和片段数据的覆盖度两个量作为参数对单体型组装问题进行建模得出一系列比原有算法快得多又准确的算法。
本书将从参数计算理论、参数算法设计和分析技术、参数算法实际应用等方面系统介绍参数计算的理论框架和技术框架。具体的，本书将对固定参数可解、固定参数不可解、核心化、迭代压缩、局部贪婪、彩色编码、随机参数化方法、分支界定、图分解、平面图参数算法、固定参数枚举、参数计算的应用等方面进行介绍，通过具体的例子阐述参数计算理论、方法的精髓和具体应用，旨在使读者能够全面系统的认识参数计算理论和技术，掌握相关技术的应用，从而有效求解各领域中的难解问题。
第2章参数计算简介
第2章参数计算简介
在计算机科学领域，NP难解理论为人们奠定了计算难解的界限，其将所有可计算问题，划分为“实际可计算问题”（P问题或易解问题）和“实际不可计算问题”（NP难问题或难解问题）。该理论在过去的近四十年中主导着人们在算法设计与分析中的研究。一旦一个计算问题被证明是NP难解的，这一问题就被认为是无法用现代计算机求解的问题，从而避免了人们为解决此类问题而付出大量而又没有希望的努力。参数计算理论对NP难解问题进行了重新划分，将难解问题分成固定参数可解问题和固定参数不可解问题。可以说，参数计算理论的提出重新指导了人们求解难解问题的思路和方法。本章将简要介绍NP完全理论的相关定义。然后，对参数计算理论中的固定参数可解、固定参数不可解框架、固定参数枚举等方面进行简要介绍。最后，对参数计算领域中常用的参数化方法进行简介。
2.1NP完全理论
实际工程应用中存在诸多计算优化问题，有些问题很容易求解，但有些问题却很难。例如，张三想驾车从A地到B地，从A到B有很多可选路线且中间经过很多城市，假设驾车的花费只跟路线的长度有关，为了节省费用，张三需要选择一条最短的路线。该问题就是著名的最短路径问题。张三很幸运，他能够在多项式时间内找到一条从A到B的最短线路。又如，李四想去n个不同的城市旅游，因为旅游费用有限，所以他想找到一个旅游路线既经过这n个城市，又费用最少。上述问题就是著名的旅行商问题。然而，李四不够幸运，他很难找到一个最省钱的策略。通过以上两个例子可以看出，最短路径问题和旅行商问题具有不同的难解性，前者可以在多项式时间内被求解，后者却无法利用现有的计算资源进行求解。NP完全理论［1］很好地对上述问题进行了分类：最短路径问题属于Ｐ问题，即多项式时间内可解问题，旅行商问题属于NP难解问题。
下面给出P、NP、NP完全、NP难的定义。
首先要说明的是，在NP完全理论框架内，考虑的问题形式都是判定性问题，即回答“是”或“否”的问题。对于上面给出的最短路径问题和旅行商问题，都是最优化问题，即寻找满足某一特性的最大或最小值。下面以旅行商问题为例具体说明最优化问题和判定性问题的差别。最优化形式的旅行商问题是给定完全图G=（V，E），其中每条边赋有一定的权值，寻找一条权值最小且包括图中所有点的圈。对于旅行商问题，其判定性形式是给定完全图G=（V，E），其中每条边赋有一定的权值，并给定参数K，问G中是否存在一条权值小于等于K且包括图中所有点的圈。可以看出，把最优化问题变成判定性，只需要引入一个与问题目标解相关的参数，然后问给定实例是否存在与引入参数相关的解。下面给出判定性问题的具体定义。
定义2.1（判定性问题）对于给定问题的每个输入实例，都存在某算法能给出Yes（是）或No（否）的判定性回答，则称该问题为判定性问题。如果某算法能对一个输入实例回答为Yes，那么这个输入实例就叫做Yes实例，反之叫做No实例。
如前所述，最短路径问题是多项式时间内可解的，其判定性问题是P问题。下面给出P问题的严格定义。
定义2.2（P）如果给定问题Q能在多项式时间被求解，则称判定性问题Q是P问题。
可以说，P问题就是能在多项式时间内被确定性计算模型，如图灵机解决的判定性问题，如单源最短路径、最小生成树和最大流问题等。
相对于P问题的定义，NP问题非正式定义为，目前来说不能在多项式时间内被确定性计算模型解决，但能在多项式时间内被迅速验证的问题，或者说这类问题能在多项式时间内被非确定性计算模型解决。具体定义如下［1］。
定义2.3（NP）如果一个判定性问题Q能被一个多项式时间算法A验证，且满足如下性质：
① 对于问题Q的Yes实例x，有一个长
展开
