《高级算法设计》课件 第4章 近似算法

高级算法设计与分析近似算法林海lin.hai@B站：foretmer目录概述旅行商问题子集和问题集合覆盖-整数规划斯坦纳最小树概述NPC问题该如何求解?如果规模很小，用指数运行时间算法对一些特殊的情况，如果有多项式时间可以解决，则设计多项式算法对用一般情况，则通过多项式时间的近似解法概述近似解的精确度C：某一算法解的代价C*：最优解的代价如果一个解达到此因子，则称算法C为ρ(n)近似算法概述近似模式：对于一个输入为n的实例，通常近似算法的因子为（1+ε）算法时间除了和n相关，和ε也相关如果对于任意一个ε>0，该算法都可以在输入规模为n的多项式时间内完成，称此模式为多项式时间近似模式显然此种模式下，当ε趋近于0时，算法逼近最优值，但可能算法的复杂度急剧增加，如时间复杂度为多项式时间近似模式中一种更好的模式称为完全多项式时间近似模式，其复杂度为：这种模式当ε减少时，运行时间不会指数增长，而是多项式增长旅行商问题旅行商问题为NPC问题定义：对于完全无向图G=（V，E），设c(A)为子集A的总代价三角不等式：旅行商问题满足三角不等式的旅行商问题生成最小生成树按对树进行先序的顺序访问节点上述算法中，生成最下生成树可以用Kruskal算法或者Prim算法，复杂度都为O(mlogn)。先序遍历的复杂度为O(n)，所以旅行商问题的近似算法复杂度为O(mlogn)

旅行商问题旅行商问题最优旅行线路（H*）的总代价的下限为最小生成树（T）边的总代价对T进行按先序往返（返回时会再次遍历节点）遍历（W），W刚好对所有的边遍历两次旅行商问题一般旅行商问题三角不等式不成立的条件下，ρ近似的旅行商问题是一个NPC问题，则定理自然成立旅行商问题如果图G存在一条哈密顿回路H，则G′必然存在一条代价为n的旅行商回路TSP(同H),此回路为ρ近似旅行商回路如果图G′存在一条ρ近似的旅行商回路TSPρ，则图G必然存在一条哈密顿回路H

子集和问题准确算法（指数时间复杂度）:得出集合S的所有子集，并计算所有子集的和优化在第i-1轮迭代中，计算(e1,e2,…,ei-1)所有的子集和在第i轮迭代中，计算(e1,

e2,…,ei)在相加的过程中，一旦子集和超过t，舍弃子集和问题子集和问题去除相近的元素：x可以被y代替例子子集和问题子集和问题子集和问题子集和问题子集和问题按这两种不同的情况讨论子集和问题子集和问题子集和问题所以：子集和问题子集和问题Ln必然包含0元素，可能包含1元素集合覆盖问题简单集合覆盖

集合覆盖问题：例子集合覆盖问题贪心算法集合覆盖问题算法第i次选择了子集Si加入到顶点覆盖集R，则其总代价+1在选取第i个子集Si时，假设ni个元素被Si首次覆盖，其中每个元素分配到的代价为：集合覆盖问题集合覆盖问题当近似算法选择了i个子集后，子集S中未被覆盖的元素的个数集合覆盖问题集合覆盖问题集合覆盖问题集合覆盖-整数规划带权重的集合覆盖：覆盖所有的元素，其权重总和最小设E={1,2,3,4,5,6,7,8}子集有:S1={1,2,3}w1=1S2={2,7,8}w2=2S3={4,5,6,7}w3=3S4={4,5,6,8}w4=4解:C={S1,S2,S3},C={S1,S2,S4}最优解：C={S1,S2,S3}集合覆盖-整数规划松弛集合覆盖-整数规划算法元素的最大频率f：设g表示包含某一元素的子集个数，则最大的g即元素的最大频率f在所有的LP最优解的子集中，选取xi（每个子集通过LP求解得出的值）的值大于1/f的子集作为IP的解集合覆盖-整数规划证明1：以上选取的子集包含了E中所有的元素集合覆盖-整数规划集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法集合覆盖-原始-对偶算法斯坦纳最小树斯坦纳最小树用最小生成树来近似斯坦纳树？斯坦纳最小树斯坦纳最小树：例子GRTMTGMTTST斯坦纳最小树：例子算法基于原图G，生成R的一个完全图GR，其中任意一条边的权重为原图G中的最短路径基于GR，生成最小生成树TMT

将TMT

中的边替换成原来的最短路径，得到图GMT

如果替换成最短路径后生成的图不是树，则需进一步生成最小生成树TST

斯坦纳最小树：例子斯坦纳最小树：例子斯坦纳最小树：例子W对TST按照先序往返(返回时会再次遍历节点)遍历斯坦纳最小树：例子GS