第1章绪论
顶点覆盖问题是著名的组合优化问题（combinatorial optimization problem），具有重要的理论研究意义和实际应用价值。本书围绕顶点覆盖中几个关键子问题，即*小加权顶点覆盖（minimumweighted vertex cover，MWVC）问题、泛化顶点覆盖（generalized vertex cover，GVC）问题和*小分区顶点覆盖（minimum partition vertex cover，P-MVC）问题的求解算法展开研究。在本章中，首先介绍本书的研究背景和意义，然后介绍相关问题的国内外研究现状，随后介绍本书的主要研究内容和贡献，*后概要地呈现本书的结构安排。
1.1研究背景和意义
组合优化是计算机科学与运筹学的一个重要分支，它通过对数学方法的研究去寻找离散事件的*优分组、编排、筛选或次序等，其目标是在问题的可行解集合中寻找*优解。组合优化问题属于*优化问题的一类。一般来说，*优化问题被分为两类：一类是连续变量的问题，另一类是离散变量的问题。其中具有离散变量的优化问题又被称为组合优化问题，组合优化问题一般是在有限集合中寻找一个对象，较典型的是一个整数、一个集合、一个排列或者一个图，使这个对象成为满足给定约束条件的*优解[1]。组合优化问题所研究的问题涉及众多领域，例如信息技术、交通运输、通信网络、经济管理、航天航空等[2-4]。接下来给出组合优化问题的形式化定义。
定义1.1：（组合优化问题）给定一个组合优化问题实例（S，X，f），其中X=(x1，x2， ，xn)表示问题的解空间，表示问题的可行解空间，f为问题的目标函数，f（xi.）表示解xi对应的目标函数值，组合优化问题要在满足给定的约束条件下找到目标函数的*优值（*大值或者*小值），即寻找一个可行解，使得.
组合优化问题的变量是离散的，导致其数学模型中的约束函数和目标函数在可行域中也是离散的。现实世界中的很多问题本质上是离散事件而不是连续事件，因此很多问题都可以归结为组合优化问题，例如旅行商问题[5-8]、背包问题[9-11]和图着色问题[12-15]等。这些问题在理论上大多属于NP难问题，求解此类问题的算法主要分为两类：精确算法和启发式算法。精确算法通过枚举搜索空间中的所有可行解来寻找*优解，这样可以保证解的*优性，经典的精确算法主要有动态规划法[16]、分支限界法[17]和割平面法[18]。但是随着问题规模的增大，计算所需时间会呈指数增长，精确算法对问题的求解就变得越来越困难，当问题规模增大到一定程度时，精确算法对问题的求解几乎变得不可能。而现实生活中的问题通常规模很大，为了在合理时间内给出问题的*优解或次优解，启发式算法应运而生。常见的启发式算法有局部搜索算法[19]、松弛方法[20]、禁忌搜索算法[21]和进化算法[22]等。
本书研究的顶点覆盖问题是经典的组合优化问题，其关键子问题，即*小顶点覆盖问题、*小加权顶点覆盖问题、泛化顶点覆盖问题和*小分区顶点覆盖问题在现实世界中都有着广泛的应用。
*小顶点覆盖问题是在一个无向图中寻找具有*小基数的顶点子集，使得图中每条边至少有一个端点在该顶点子集中。下面阐述*小顶点覆盖问题的几个代表性应用。
（1）计划在城市交通路口安装监视设备，对每条道路的交通流量进行实时监控。决策者希望选择某些路口，并在这些路口安装监视设备来监视该城市的每条道路，使得总的监视设备数*少[23]。很容易看出，城市的路口与道路可表示成一个无向图，各个路口表示无向图中的顶点，每条道路表示无向图中的一条边，那么该问题就可以用*小顶点覆盖问题来描述。
（2）在网络中的节点上安装控制器，实现对每条链接上数据的监控。决策者希望选择某些节点来安装控制器，使得控制器的数量*少[24]。在该问题中，网络可以看成一个无向图，其中顶点表示网络的节点，边表示网络中的链接，此问题就可以建模为*小顶点覆盖问题。
*小加权顶点覆盖问题是*小顶点覆盖问题的扩展，该问题是在一个顶点加权图中寻找一个顶点覆盖，使得该覆盖中顶点的权重和*小。该问题的具体应用如下。
（1）同样是计划在城市交通路口安装监视设备，决策者已知在每个路口安装监视设备的成本及运营和维护的费用，决策者希望选择某些路口，并在这些路口安装监视设备来监视该城市的每条道路，使得总的安装成本与运营和维护的费用*少[23]。此时路口监视设备的成本、运营和维护的费用等表示图中顶点的权值，那么，如果用*小顶点覆盖问题来描述该问题，只能求得*少监视设备的个数，而不能保证安装成本与运营和维护的费用*少。上述问题可以用*小加权顶点覆盖问题来描述。
（2）地图标注问题是在地图中标记地理位置和兴趣点以供用户使用，地图标记涉及地图中标签的选择和放置，其中一个限制是两个标签不应该相互重叠。消除标签冲突和*大化显示标签重要性的问题可以建模为*大加权独立集问题，它等价于寻找一个具有*小权值的顶点覆盖[25]。具体地说，每个标签都可以被看作是一个顶点，每个顶点根据它的重要性被分配一个权值，如果两个顶点相互重叠，那么它们之间就会有一条边。
泛化顶点覆盖问题也是*小顶点覆盖问题的扩展问题，给定一个无向图G＝（Vt，Eg），其中每个顶点v对应一个权值c（v），每条边e对应三个权值wi（e）（i=0，1，2）分别表示有i个端点在候选解中的边权值，目标是找到一个顶点子集使得顶点权重和以及边的权重和*小。该问题的具体应用如下。
（1）网络升级问题中，已知一个无向图，每个顶点的升级成本是c(v)，对于每条边e，wi(e)表示e的升级成本，其中i表示e有几个端点升级，其目标是找一个升级的顶点子集，使得升级的顶点和边的成本*小[26]。该问题可以表示为泛化顶点覆盖问题，其中升级顶点表示候选解中的顶点，未升级的点表示未在候选解中的顶点。
（2）预算受限的网络升级问题是泛化顶点覆盖问题的一个应用扩展，已知一个无向图，每个顶点，目标是找*小花费的升级顶点子的升级成本是 集，满足从网络中获得的*小生成树的权重和小于一个已知的阈值[27]。
*小分区顶点覆盖问题是将无向图中的边划分为若干个不相交的分区，目标是找到一个顶点子集，使得该子集至少覆盖每个分区中确定的边数。当分区的个数为1时，*小分区顶点覆盖问题规约为*小部分顶点覆盖问题，因此*小分区顶点覆盖有着更广泛的应用。下面我们给出了*小部分顶点覆盖问题的具体应用。
（1）传统上，在研究设施选址问题时，假设所有的客户都将得到服务。这个问题的一个重大缺点是，一些非常遥远的客户，称为离群值，可能很大程度上使得*终的解决方案无法实施。可以将各种设施选址问题（k中心、k中值、无能力设施选址等）推广到只为特定比例的客户提供服务，此时该问题就可以建模为*小部分顶点覆盖问题[28]。
（2）在各种系统中，图常常被用来建模风险管理。特别地，Caskurlu等在文献[29]中考虑了一个系统，其本质上代表了一个三边图。此模型的目标是将系统中的风险降低到预定义的风险阈值水平以下。该风险管理系统的主要目标可以表述为二部图上的部分顶点覆盖问题[30]。
1.2相关研究工作
顶点覆盖问题的几个关键子问题，如*小顶点覆盖问题、*小加权顶点覆盖问题、泛化顶点覆盖问题和*小分区顶点覆盖问题都是NP难组合优化问题。这些问题不但描述很简单，而且有很强的工程代表性，但不存在一个算法能够在多项式时间内找到问题的*优解。由于“组合爆炸”的存在，随着问题规模的增大，寻找*优解的精确算法所需的时间和空间就会呈指数增长。正是这些问题的代表性和难解性激起了学者对组合优化理论及求解算法的研究兴趣。下面介绍顶点覆盖问题的几个关键子问题的国内外研究现状和相关工作。
1.2.1*小顶点覆盖问题的研究现状
给定一个无向图，*小顶点覆盖（minimum vertex cover，MVC）问题是寻找一个含有*小基数的顶点子集使得图中每条边至少有一个端点在该顶点子集中。*小顶点覆盖问题有两个等价问题，即*大独立集（maximum independent set，MIS）问题和*大团（maximum clique，MC）问题。MVC问题及其等价问题不仅有重要的理论研究意义，而且在实际问题中的很多领域都有重要的应用，如网络安全、超大规模集成电路、调度问题、金融网络、生物信息学等领域。MVC问题是著名的NP难组合优化问题，它的判定版本是Karp提出的21个NP完全问题之一。要在多项式时间内找到近似比是1.3606的解是NP难的[34]，目前*好的*小顶点覆盖问题的近似算法才能达到2－o.1.的近似比[35-36]。对精确算法的研究主要集中在固定参数化算法上，如文献[37]～[42]中的算法。近几年，陈吉珍等[43]根据加权分治技术设计出一个分支降阶递归算法来求解*小顶点覆盖问题，并通过加权分治技术分析得出该算法的时间复杂度为O(1.255n)。Akiba等[44]提出了基于理论技术的分支约简算法求解*小顶点覆盖问题，Wang等[45]提出了一种基于分支定界的精确算法求解*小顶点覆盖问题，该算法中提出了两个新的下界来帮助简化搜索空间。虽然这些研究在理论上取得了巨大的进展，但理论与实践之间仍存在着巨大的差距。因此，对于大规模的困难求解的实例，研究人员通常采用启发式算法在合理的时间内找到一个可接受的解。
近年来，很多启发式算法被提出来用于求解*小顶点覆盖问题。Khuri等[46]提出了一种进化方法求解该问题。Chen等[47]提出了蚁群优化算法求解*小顶点覆盖问题。Xu等[48]提出了一种有效的模拟退火算法求解*小顶点覆盖问题。该算法为每个顶点定义了一个接受函数，这可以帮助算法找到问题的*优解或次优解。Richter等[49]提出了一个随机局部搜索算法求解*小顶点覆盖问题，该算法命名为随机边覆盖（coveredges randomly，COVER）算法，相关论文在德国人工智能2007年会议上发表，并成为当时竞争*佳论文的三篇论文之一。Cai等[50]设计了求解MVC问题的边加权局部搜索（edge weighting local search，EWLS）算法，在该算法中提出了部分顶点覆盖和边加权技术，并对于挑战实例frb100-40求出了更小的顶点覆盖，刷新了在该实例上自2007年创下的求解纪录。随后，Cai等[51]提出了一个新的局部搜索策略，即格局检测（configuration checking，CC），用于处理局部搜索中的循环问题。Cai等使用这个策略改进EWLS算法，得到一个新的算法，称为边加权格局检测（edge weighting con guration checking，EWCC）算法。Ugurlu[52]设计了一种快速启发式算法，即隔离算法（isolationalgorithm，IA），用于求解*小顶点覆盖问题。Cai等[53]提出了两个新策略——两阶段交换和带遗忘的边加权，并使用这两个策略设计了一个新的*小顶点覆盖问题局部搜索算法，该算法被称为NuMVC。NuMVC算法当时在大量权威数据集上的应用效果都大幅度地优于已有的启发式算法。NuMVC可以看作是*小顶点覆盖问题启发式算法的一个突破。Fang等[32]首次结合边加权和顶点加权策略应用于*小顶点覆盖问题中，提出了一种新的局部搜索算法点权边权局部搜索（vertex weight and edge weight based local search，VEWLS）算法。随后，Cai等[54]将顶点加权策略与NuMVC算法相结合，形成了一种面向*小顶点覆盖的两种加权的局部搜索（twoweighting local search for minimum vertexcover，TwMVC）算法。之后，Cai等[55-56]又提出了一种面向*小顶点覆盖的简
展开
