算法设计与分析第11章近似算法.ppt

第十一章 近似算法 1 2 3 4 概述 图问题中的近似算法 组合问题中的近似算法 小 结 概 述——设计思想 近似算法是解决难解问题的一种有效策略，其基本思想是放弃求最优解，用近似最优解代替最优解，以换取算法设计上的简化和时间复杂性的降低。 近似算法找到的可能不是一个最优解，但它总会为待求解的问题提供一个解。为了具有实用性，近似算法必须能够给出算法所产生的解与最优解之间的差别，以保证任意一个实例的近似最优解与最优解之间相差的程度。显然，这个差别越小，近似算法越具有实用性。 一个简单的例子—求π的近似值 【问题】请用正多边形逼近法求π的近似值。 【想法】?用圆内接正多边形的边长和半径之间的关系，不断将边数翻倍并求出边长，重复这一过程，正多边形的边长就逐渐逼近圆的周长，只要圆内接正多边形的边数足够多，就可以求得所需精度的π值。 一个简单的例子—求π的近似值 简单起见，设单位圆的半径是1，则单位圆的圆周长是2×π，设单位圆内接正i边形的边长为2b，边数加倍后正2i边形的边长为x，则： 问题描述：无向图G=(V, E)的顶点覆盖是顶点集V的一个子集V ?V，使得若(u, v)是G的一条边，则v∈V或u∈V。顶点覆盖问题是求出图G中的最小顶点覆盖，即含有顶点数最少的顶点覆盖。 图问题中的近似算法—顶点覆盖问题 采用策略：初始时边集E=E，顶点集V={ }，每次从边集E中任取一条边(u, v)，把顶点u和v加入到顶点集V中，再把与u和v顶点相邻接的所有边从边集E中删除，重复上述过程，直到边集E为空，最后得到的顶点集V是无向图的一个顶点覆盖。由于每次把尽量多的相邻边从边集E中删除，可以期望V中的顶点数尽量少，但不能保证V中的顶点数最少。 顶点覆盖问题是一个NP难问题，目前尚未找到一个多项式时间算法。虽然要找到图G的一个最小顶点覆盖很困难，但要找到图G的一个近似最小覆盖却很容易。 顶点覆盖问题——想法 顶点覆盖问题——实例 a b c e d f g a b c e d f g a b c e d f g (a) 一个无向图 (b) V ={a, b} (c) V ={a, b, c, f} 删除与a或b相关联的边 删除与c或f相关联的边 a b c e d f g a b c e d f g a b c e d f g (d) V ={a, b, c, f, d, e} (e) 近似最小顶点覆盖 (f) 最小顶点覆盖 删除与d或e相关联的边 V ={a, b, c, f, d, e} V ={a, b, c, e} 顶点覆盖问题——算法 1. 初始化：x[n] = {0}; 2. E = E； 3. 循环直到E为空 3.1 从E中任取一条边(u, v)； 3.2 将顶点u和v加入顶点覆盖中：x[u] = 1; x[v] = 1; 3.3 从E中删去与u和v相关联的所有边； 图问题中的近似算法—TSP问题 问题描述：TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次然后回到出发城市，并要求所走的路程最短。 TSP问题——想法 如果无向图G=(V, E)的顶点在一个平面上，边(i, j)∈E的代价cij均为非负整数，且两个顶点之间的距离为欧几里德距离，则对图G的任意3个顶点i, j, k∈V，显然满足如下三角不等式：cij+cjk≥cik TSP问题——实例 a d b c h f e g a d b c h f e g (d) 由遍历序列产生哈密顿回路 (e) TSP问题的最优解 2 a d b c h f e g a d b c h f e g a d b c h f e g 1 3 4 5 6 7 8 (a) 图G的顶点 (b) 生成最小生成树T (c) 对T进行深度优先遍历 TSP问题——算法 1. 在图中任选一个顶点v； 2. 采用Prim算法生成以顶点v为根结点的最小生成树T； 3. 对生成树T从顶点v出发进行深度优先遍历，得到遍历序列L； 4. 根据L得到图G的哈密顿回路； 组合问题中的近似算法—装箱问题 问题描述：设有n个物品和若干个容量为C的箱子，n个物品的体积分别为{s1, s2, …, sn}，且有si≤C（1≤i≤n），装箱问题把所有物品分别装入箱子，求占用箱子数最少的装箱方案。 装箱问题——想法 大多数装箱