第11章近似算法资料.ppt

2019/9/22,Design and Analysis of Algorithm,1,存在的问题 迄今为止，所有的NP完全问题都还没有多项式时间算法 回溯法与分支限界等算法可以相对有效地解决这类问题，但算法的时间性能无法保证 近似算法 放弃求最优解，而用近似最优解代替最优解，以换取算法设计上的简化和时间复杂性的降低 但有些问题不适合用近似算法求解，对这些问题求近似最优解几乎和求最优解一样难第11章 近似算法,2019/9/22,Design and Analysis of Algorithm,2,近似算法的依据 输入数据本身就是近似的，如测量数据 很多问题的最优解，允许有一定程度的近似 采用近似算法可以在很短的时间内得到问题的解（特别是与指数时间相比较） 其思想是用近似最优解代替最优解，是在计算量和精确解间的一个折中 近似算法性能的两个重要指标 对于规模为n 的问题 算法能在多项式时间内完成 算法的近似解满足一定的精度，即近似最优解的近似程度,11.1 概 述,2019/9/22,Design and Analysis of Algorithm,3,近似算法的性能 近似比 若一个问题的最优值为c*，该问题的一个近似最优解的目标函数值为c，则近似算法的性能比可定义为： = 在通常情况下， 是问题输入规模n的一个函数ρ(n)，即： ≤ρ(n),11.1 概 述,2019/9/22,Design and Analysis of Algorithm,4,与近似比率相关的问题 对最小化问题，有：C≥C* 对最大化问题，有：C≤C* 近似算法 C 的近似比率 ρ(n) 总大于或等于1 近似算法的近似比率越小，则算法的性能越好 近似算法的近似比率越大，则算法的性能越差,2019/9/22,Design and Analysis of Algorithm,5,近似算法的相对误差与相对误差界ε(n) = 若对问题的输入规模n，有一函数ε(n)使得: ≤ε(n) 则称ε(n)为该近似算法的相对误差界。

近似比ρ(n)与相对误差ε(n)间关系 ρ(n)与ε(n)之间显然有如下关系： ε(n)≤ρ(n)-1,11.1 概 述,2019/9/22,Design and Analysis of Algorithm,6,第11章 近似算法,11.1 概 述,11.2 图问题中的近似法,11.3 组合问题中的近似法,*11.4 实验项目——TSP问题的近似法,2019/9/22,Design and Analysis of Algorithm,7,第11章 近似算法,11.2.1 顶点覆盖问题,11.2.2 TSP问题,2019/9/22,Design and Analysis of Algorithm,8,11.2.1 顶点覆盖问题,问题描述： 无向图G=(V,E)的顶点覆盖问题：指是它的顶点集V 的一个子集V’V，使得:若(u,v) 是G的一条边，则v∈V’ 或u∈V’顶点覆盖V’ 的大小是它所包含的顶点个数 |V’|VertexSet approxVertexCover ( Graph g ) { cset=； e1=g.e； while (e1 != ) { 从e1中任取一条边(u,v)； cset=cset∪{u,v}； 从e1 中删去与u 和v 相关联的所有边； } return c },cset用来存储顶点覆盖中的各顶点。

初始为空，不断从边集e1中选取一边(u,v)，将边的端点加入cset中，并将e1中已被u和v覆盖的边删去，直至cset已覆盖所有边即e1为空2019/9/22,Design and Analysis of Algorithm,9,图(a)～(e)说明了算法的运行过程及结果e)表示算法产生的近似最优顶点覆盖cset，它由顶点b,c,d,e,f,g所组成f)是图G的一个最小顶点覆盖，它只含有3个顶点：b,d和e算法approxVertexCover的性能比为211.2.1 顶点覆盖问题,2019/9/22,Design and Analysis of Algorithm,10,时间复杂性： cset可用数组来存储各顶点，则初始化cset需要执行n次，设图G含有n个顶点e条边，则算法的时间复杂性为O(n+e) 近似比 若用A表示算法在“从e1中任取一条边(u,v)”步骤中选取的边的集合，则A中任何两条边没公共顶点算法结束时，cset中的顶点数|V’|=2|A| 图G的任一顶点覆盖一定包含A中各边的至少一个端点，因此，若最小顶点覆盖为V*，则|V*|=|A|，即|V*|=|V’|/2，即(|V’|/|V*|)=2,11.2.1 顶点覆盖问题,2019/9/22,Design and Analysis of Algorithm,11,第11章 近似算法,11.2.1 顶点覆盖问题,11.2.2 TSP问题,2019/9/22,Design and Analysis of Algorithm,12,11.2.2 旅行售货员问题,问题描述： 给定一个完全无向图G=(V,E)，其每一边(u,v)∈E有一非负整数费用 c(u,v)。

要找出G 的最小费用哈密顿回路比如，费用函数c 往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质TSP 问题的一些特殊性质：,但是，可以设计一个近似算法，其近似比为2图11.2(a)给出了一个满足三角不等式的无向图，图中方格的边长为1求解TSP问题的近似算法首先采用Prim算法生成图的最小生成树T，如图(b)所示，图中粗线表示最小生成树中的边，然后对T进行深度优先遍历，经过的路线为a→b→c→b→h→b→a→d→e→f→e→g→e→d→a，得到遍历序列L=(a, b, c, h, d, e, f, g)，由序列L得到哈密顿回路，即近似最优解，如图(d)所示，其路径长度约为19.074，图(e)所示是(a)的最优解，其路径长度约为16.0842019/9/22,Design and Analysis of Algorithm,14,11.2.2 具有三角不等式性质的 旅行售货员问题举例,(b)表示找到的最小生成树T；(c)表示对T作深度优先遍历的次序；(d)表示L产生的哈密顿回路H； (e)是G的一个最小费用旅行售货员回路。

2019/9/22,Design and Analysis of Algorithm,15,11.2.2 具有三角不等式性质的 旅行售货员问题,对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法void approxTSP (Graph g) { (1)选择 G的任一顶点 r； (2)用 Prim 算法找出带权图 G 的一棵以r 为根的最小生成树 T； (3)对生成树T从顶点r出发进行深度优先遍历，得遍历序列 L； (4)将r 加到表 L 的末尾，按表 L 中顶点次序组成回路H，作为 计算结果返回； },当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍2019/9/22,Design and Analysis of Algorithm,16,时间复杂性： 算法的时间主要耗费在采用Prim算法构造最小生成树，因此，其时间复杂性为O(n2) 近似比 设最短哈密尔顿回路为H*，W(H*)是代价和；T是由Prim算法求得的最小生成树，W(T)是T的代价和；H是由算法得到的近似解，也是一个哈密尔顿回路，W(H)是H的代价和。

因哈密尔顿回路删去一条边可得G的一个生成树，故：W(T)≤W(H*)设算法中深度优先遍历生成树T得到的路线为R，则R中对于T的每条边都经过两次，故有：W(R)=2W(T)算法得到的近似解H是R删除若干中间点（非第一次出现的点）得到的，每删除一个顶点恰好是用三角形的一边取代另外两边如…c→b→h…，删b11.2.2 具有三角不等式性质的 旅行售货员问题,2019/9/22,Design and Analysis of Algorithm,17,近似比（续） 由三角不等式可知，这种取代不会增加总代价，所以有：W(H)≤W(R)从而得： W(H)≤2W(H*)由此可得算法的近似比为211.2.2 具有三角不等式性质的 旅行售货员问题,2019/9/22,Design and Analysis of Algorithm,18,11.2.2 一般的旅行售货员问题,在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NP换句话说，若P≠NP，则对任意常数ρ1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法2019/9/22,Design and Analysis of Algorithm,19,第11章 近似算法,11.1 概 述,11.2 图问题中的近似法,11.3 组合问题中的近似法,*11.4 实验项目——TSP问题的近似法,2019/9/22,Design and Analysis of Algorithm,20,11.3.1 装箱问题,装箱问题描述 给定n个物体u1,u2,…,un ，体积分别为s1,s2,…,sn ，容量为C的箱子b1,b2,…,bk ,…，满足 si≤ C, i=1,2,…,n。

要求物体不能分割，把所有物体装进箱子，使所装入的箱子尽可能少装箱问题的四种算法 First Fit（首次适宜FF）算法 把箱子按下标标记，所有的箱子初始化为空；按物体顺序装入箱子装入过程如下： 把第一个物体u1装入第一个箱子 如果b1还容纳得下第二个物体u2，继续把u2装入b1；,2019/9/22,Design and Analysis of Algorithm,21,11.3.1 装箱问题,否则，把u2 装入b2 一般地，为了装入物体 ui，先找出能容纳得下si 的下标最小的箱子 bk，再把物体ui 装入箱子bk， 重复这些步骤，直到把所有物体装入箱子为止FF 算法 算法12.3 装箱问题的首次适宜算法 输入：n 个物体的体积 s[], 箱子的容量 C 输出：装入箱子的个数 k ,每个箱子中装入的物体累计体积 b[],例如，有10个物品，其体积分别为S＝(4, 2, 7, 3, 5, 4, 2, 3, 6, 2)，若干个容量为10的箱子，采用首次适宜法得到的装箱结果如图11.3所示首次适宜法求解装箱问题的算法如下：,2019/9/22,Design and Analysis of Algorithm,23,11.3.1 装箱问题,2019/9/22,Design and Analysis of Algorithm,24,11.3.1 装箱问题,FF算法的分析 时间复杂性： O(n^2)时间。

近似比 假定，C为一个单位体积，si≤1,i=1,2,…,n 令FF(I)表示在实例 I 下，使用算法FF装入物体时，所使用的箱子总容量； 令OPT(I)为最优装入时所使用的箱子总容量 至多有一个非空的箱子所装的物体体积小于1/2否则，如果有两个以上的箱子所装的物体体积小于1/2，假设这两个箱子是 bi 及 bj，并且ij，装入 bi 及 bj中物体的体积均小于1/2,2019/9/22,Design and Analysis of Algorithm,25,11.3.1 装箱问题,按照算法的装入规则，必然把bj中的物体继续装入bi，而不会装入bj箱子 则装入箱子的物体如下图所示：,,: 为箱子中的空余体积 : 为箱子中装入的物体体积有:,,,2019/9/22,Design and Analysis of Algorith。