优化1: 求解顶点覆盖问题和度量斯坦纳树问题的近似算法
1. 概述我们将学习组合优化问题的传统算法. 这些算法是无数应用程序中出现的算法类型, 从数十亿美元的操作到日常的计算任务. 它们可能被航空公司用来规划与定价他们的航班; 可能被大公司用来决定在仓库中囤积什么货物, 在哪个仓库囤积货物; 可能被运输公司用来决定配送卡车的路线; 被奈飞用来决定推荐你什么电影; 被GPS导航器用来规划行车路线等等.
我们要研究的一些问题是NP-hard, 如此我们不太可能设计出精确高效的算法. 对于这类问题, 我们将研究在最坏情况下高效 (worst-case efficient), 但是输出结果可以是次优 (sub-optimal) 的算法. 我们将能够证明最优解 (optimal solution) 和解的代价 (solution cost) 之间的比率的最坏情况界限 (bound). 拥有可证明的输出解质量保证 (provable guarantee) 的次优算法被称作 近似算法 (approximation algorithm).
内容如下:
[*]近似算法的简单例子. 我们将研究 顶点覆盖问题 (Vertex Cover), 集合覆盖问题 (Set Cover), 斯坦纳树问题 (Steiner Tree) 和 旅行推销员问题 (Travelling salesman problem). 这些算法和他们的分析相对简单, 但是他们引入了不少关键的概念, 包括获得最优解代价上限的重要性.
[*]线性规划 Linear Programming. 线性规划是实数上的优化问题, 我们希望优化一组实变量的线性函数, 服从这些变量的线性不等式系统. 例如:
https://www.zhihu.com/equation?tex=%5Cbegin%7Balign%2A%7D+%26%5Ctext%7Bmaximize%7D+%5Cquad+x_1+%2B+x_2+%2B+x_3%26+%5C%5C+%26%5Ctext%7Bsubject+to%3A%7D+%5C%5C+%26+2+x_1+%2B+x2+%5Cleq+2%26+%5C%5C+%26+x_2+%2B+2x_3+%5Cleq+1%26+%5Cend%7Balign%2A%7D
上面线性规划的最优解是, 比如 https://www.zhihu.com/equation?tex=x_1+%3D+0.5%2C+x_2+%3D+1%2C+x3+%3D+0, 那么我们就有代价为1.5. 一种证明它是最优解的方法是把两个线性约束相加，这告诉我们在每个容许的解中我们都有:
https://www.zhihu.com/equation?tex=2+x_1+%2B+2+x_2+%2B+2+x_3+%5Cleq+3
也就是 https://www.zhihu.com/equation?tex=x_1+%2B+x_2+%2B+x_3+%5Cleq+1.5. 我们能够通过对不等式组求和来验证解的最优性是线性规划的 对偶性 (duality) 的一个特例. 线性规划是基于实数值变量的优化问题, 而组合优化问题是基于 有限个离散解 的问题. 那我们为什么还要研究线性规划问题呢? 这是因为:
[*]线性规划问题可在多项式时间内解出, 在实际中这是很高效的
[*]我们即将研究的所有的组合优化问题都可以被写成线性规划, 只是有一个额外条件: 变量全是 整数值
这导致两个应用:
[*]如果我们对一个问题采用积分线性规划公式, 我们移除完整性要求, 我们将其作为实数上的线性规划以高效地求解, 并且我们足够幸运以至于最优解恰巧有整数值, 那么我们就得到了我们组合优化问题的最优解. 事实上, 对于一些问题, 可以证明每一个输入都会发生这种情况
[*]如果我们对一个问题采用积分线性规划公式, 我们移除完整性要求, 我们将其作为实数上的线性规划以高效地求解,我们发现解带有小数值, 但是然后我们能够 "四舍五入" 小数值, 使其变成整数, 同时也不会怎么改变解的代价, 那么我们就有了一个高效的 近似算法
接下来的内容有:
[*]通过线性规划的近似算法. 我们将给出各种例子, 可以通过 "四舍五入" 线性规划的小数最优值来设计近似算法
[*]流和匹配问题 (Flows and Matchings) 的 精确算法 (exact algorithm). 我们讲研究一些最巧妙并实用的优化算法, 这些算法会找到最优解
[*]线性规划, 流和匹配问题. 我们将展示通过线性规划, 流和匹配问题可以被最优地求解. 理解背后的原理会帮助我们理解线性规划对偶性理论
[*]在线算法 (online algorithm). 在线算法将输入作为流 (stream) 接受, 并且在任意给定时间点, 它都可以仅基于部分已知信息做出决策. 我们将研究两种典型的在线设置: 分页 (paging) 通常是分层存储器中的数据传输, 和投资.
2. 顶点覆盖问题
2.1. 定义
给定一无向图 https://www.zhihu.com/equation?tex=%5Cmathcal+G+%3D+%7B%28V%2C+E%29%7D, 顶点覆盖指的是顶点的一个子集使得对于每条边都有少一个端点或者是的一个元素. 比如 https://www.zhihu.com/equation?tex=V 就是一个可行解, 因为它包含了所有边. 而在最小顶点覆盖问题中, 我们的输入是一个图, 目标是找到一个子集包含尽可能少的顶点.
最小顶点覆盖问题与 最大独立集问题 (maximum independent set) 非常相关. 在一个图中, 一个 独立集 指的是顶点的子集 https://www.zhihu.com/equation?tex=I+%5Csubseteq+V 使得 https://www.zhihu.com/equation?tex=I 中 不存在 边同时有和为端点. 最大独立集问题的目标为找到最大可能的独立集.
不难发现, 在图中, 当且仅当一个集合的补集 https://www.zhihu.com/equation?tex=V+-+C 是一个独立集, 则为顶点覆盖集. 如此, 从精确算法的角度出发, 这两个问题是等价的: 若是图的最优顶点覆盖集, 则 https://www.zhihu.com/equation?tex=V+-C 是图的最优独立集, 反之亦然. 但是从近似算法的角度出发, 这两个问题并 不等价. 接下来我们将介绍一个线性计算时间的2-approximate算法来求解最小顶点覆盖问题. 顾名思义, 2-approximate算法最差也能找到2倍于最优集合大小的次优集合. 但是对于独立集问题, 却 不存在常数因子 (constant-factor), 多项式时间 (polynomial-time) 的近似算法. 要弄清楚为什么没有矛盾, 以及近似的概念是怎么高度依赖于代价函数的, 我们假设有一个图有个节点, 其中最优顶点覆盖集的大小为 https://www.zhihu.com/equation?tex=0.9n , 并且假设我们的算法找到了一个大小为 https://www.zhihu.com/equation?tex=n+-+1 的顶点覆盖集. 然后算法找到一个仅比最优解大 11% 左右的解, 这还不赖. 但是! 从独立集小大的角度来说, 我们的图最优独立集的大小为 https://www.zhihu.com/equation?tex=0.1n ( https://www.zhihu.com/equation?tex=0.9+n 的补集), 而我们的算法只找到大小为1的独立集, 这是非常糟糕的.
2.2. 算法
算法很简单:
[*]输入: 图
[*]
[*]while ( 存在一条边使得并且):
[*]https://www.zhihu.com/equation?tex=C+%3A%3D+C+~%5Ccup~+%5C%7Bu%2C+v%5C%7D
[*]返回
首先初始化我们的集合为空集, 然后当它因为没有覆盖一些边而不能成为一个顶点覆盖集, 我们就添加这条边的 两个 端点到集合中. 当我们结束 while 循环时, 返回的是解. 为了分析这个近似算法, 我们令 opt 为最小顶点覆盖集的顶点个数, 则我们可以观察到:
[*]若 https://www.zhihu.com/equation?tex=M+%5Csubseteq+E 是一个匹配 (matching), 也就是一个没有共同端点的边集, 那么我们必有 opt https://www.zhihu.com/equation?tex=%5Cgeq+%7CM%7C, 因为内的每条边都必须使用不同的顶点来覆盖
[*]在 while 循环内考虑的边集会形成匹配, 因为若和是在 while 循环内考虑的两条边, 且是先被考虑的那一条, 则当正被考虑的时候, 集合已经包含和, 因此 https://www.zhihu.com/equation?tex=u%2C+v%2C+u%27%2C+v%27 都是不同的
[*]若我们令表示在 while 循环考虑的边集, 令 https://www.zhihu.com/equation?tex=C_%7Bout%7D 为算法输出的集合, 则我们有 https://www.zhihu.com/equation?tex=%7CC_%7Bout%7D%7C+%3D+2+%5Ccdot+%7CM%7C+%5Cleq+2+%5Ccdot+%5Ctextit%7Bopt%7D
正如我们之前所讨论的那样, 这个算法有点不自然. 每次我们找到一条边满足搜索条件, 则两个端点和都会被添加到中, 即使只添加其中一个端点就足以覆盖 . 有点矫枉过正了? 如此, 让我们考虑下面的替代算法:
[*]输入: 图
[*]
[*]while ( 存在一条边使得并且):
[*]https://www.zhihu.com/equation?tex=C+%3A%3D+C+~%5Ccup~+%5C%7Bu%5C%7D
[*]返回
如果我们的图结构是 "星形", 那么上面这个算法就有问题了. 很明显最优解是选到中心顶点1, 然而上面的算法可能选择所有的顶点 (除了中心顶点1).
另一种替代算法是 贪心算法 (greedy algorithm):
[*]输入: 图
[*]
[*]while (不是一个顶点覆盖集 ):
[*]令为最没有被覆盖的边上的顶点
[*]https://www.zhihu.com/equation?tex=C+%3A%3D+C+%5Ccup+%5C%7B+u+%5C%7D
[*]返回
上述贪心算法的效果也很差, 对于每个 , 我们可以构建一个图有个顶点, 其中最优解的代价大概在 https://www.zhihu.com/equation?tex=n+%2F+%5Ctext%7Bln%7D+%28n%29, 但是贪心算法找到的解的代价大概为 https://www.zhihu.com/equation?tex=n+-+n%2F%5Ctext%7Bln%7D%28n%29, 所以它不能达到最优解的 常数因子的近似.
3. 度量斯坦纳树问题
在斯坦纳树问题 (Steiner Tree problem) 中, 给定 必要点集 (a set of required points) https://www.zhihu.com/equation?tex=R 和 可选点集 (a set of optional points) https://www.zhihu.com/equation?tex=S, 以及距离函数 https://www.zhihu.com/equation?tex=d%3A+%28R+%5Ccup+S%29+%5Ctimes+%28R+%5Ccup+S%29+%5Cto+%5Cmathbb+R_%7B%5Cgeq+0%7D. 距离函数就是我们所说的 度量 (metric), 对于每两点 https://www.zhihu.com/equation?tex=x%2C+y 我们都有 https://www.zhihu.com/equation?tex=d%28x%2C+y%29+%3D+d%28y%2C+x%29, 并且对于每三个点 https://www.zhihu.com/equation?tex=x%2C+y%2C+z 我们都有三角不等式:
https://www.zhihu.com/equation?tex=d%28x%2Cy%29+%5Cleq+d%28x%2C+z%29+%2B+d%28z%2C+y%29
我们的目标是找到 覆盖 (span) 所有必要点, 并有可能使用一些可选点的树 https://www.zhihu.com/equation?tex=%5Cmathcal+T+%3D+%28V%2C+E%29, 也就是 https://www.zhihu.com/equation?tex=R+%5Csubseteq+V+%5Csubseteq+%5C%7BR+%5Ccup+S%5C%7D, 使得树的总长度 https://www.zhihu.com/equation?tex=%5Csum_%7B%28x%2C+y%29+%5Cin+E%7D+d%28x%2C+y%29 最小.
该问题与 最小生成树 (minimum spanning tree) 问题非常相似, 最小生成树问题有精确算法, 可以多项式 (事实上接近线性) 时间内跑出结果. 在最小生成树问题中, 已知一张加权图, 我们可以将其视为一点集和一距离函数 (可能不满足三角不等式), 并且我们想要找到包含所有顶点的最小总距离的树. 不同之处在于, 最小斯坦纳树问题只需要覆盖所有顶点的子集, 而其他的顶点旨在对构建更短总距离的树有帮助时, 才被包含进解中.
我们考虑如下近似算法: 在必要点集上运行一最小生成树算法, 也就是找到最佳可能的, 不使用可选点的树. 接下来的课程中我们将证明这个算法可以取得2近似的因子.
<hr/>原文链接
页:
[1]