近似算法 东南大学计算机学院 方效林

本章内容 近似算法的基本概念 顶点覆盖问题 集合覆盖问题 旅行商问题 子集和问题 随机和线性规划

近似算法的基本概念 实际应用中很多问题都是NP-完全问题 求解NP-完全问题很难 若NP-完全问题输入规模很小，可指数级穷举搜索 否则，用多项式算法近似

近似算法的基本概念 近似算法 近似算法的时间复杂度分析 近似算法的近似度(近似解与优化解的差距) 能够给出一个优化问题的近似优化解的算法 主要解决优化问题(最大化、最小化) 近似算法的时间复杂度分析 分析方法与传统算法一致 近似算法的近似度(近似解与优化解的差距) Ratio Bound 相对误差

近似算法的基本概念 Ratio Bound 设A是一个优化问题的近似解，A的Ratio Bound为𝑩(𝒏)，则 𝐦𝐚𝐱 𝑨 𝑶𝑷𝑻 , 𝑶𝑷𝑻 𝑨 ≤𝑩(𝒏) 若问题是最大化问题，则𝐦𝐚𝐱 𝑨 𝑶𝑷𝑻 , 𝑶𝑷𝑻 𝑨 = 𝑶𝑷𝑻 𝑨 若问题是最小化问题，则𝐦𝐚𝐱 𝑨 𝑶𝑷𝑻 , 𝑶𝑷𝑻 𝑨 = 𝑨 𝑶𝑷𝑻 Ratio Bound越大，近似解越坏 A近似解代价，OPT最优解代价

近似算法的基本概念 相对误差 相对误差界 设A是一个优化问题的近似解，A的相对误差为 |𝑨−𝑶𝑷𝑻| 𝑶𝑷𝑻 |𝑨−𝑶𝑷𝑻| 𝑶𝑷𝑻 ≤𝜺(𝒏) A近似解代价，OPT最优解代价

近似算法的基本概念 相对误差与Ratio Bound关系 只要求出了Ratio Bound，就求出了相对误差 𝜺 𝒏 ≤𝑩 𝒏 −𝟏 对于最小化问题 𝜺 𝒏 = |𝑨−𝑶𝑷𝑻| 𝑶𝑷𝑻 = 𝑨−𝑶𝑷𝑻 𝑶𝑷𝑻 = 𝑨 𝑶𝑷𝑻 −𝟏=𝑩 𝒏 −𝟏 对于最大化问题 𝜺 𝒏 = |𝑨−𝑶𝑷𝑻| 𝑶𝑷𝑻 = 𝑶𝑷𝑻−𝑨 𝑶𝑷𝑻 = 𝑶𝑷𝑻 𝑨 −𝟏 𝑶𝑷𝑻 𝑨 = 𝑩(𝒏)−𝟏 𝑩(𝒏) ≤𝑩(𝒏)−𝟏 只要求出了Ratio Bound，就求出了相对误差 A近似解代价，OPT最优解代价

顶点覆盖问题 顶点覆盖是NP-完全问题 输入：无向图 𝑮=(𝑽,𝑬) 输出：𝑨⊆𝑽，满足 ∀ 𝒖,𝒗 ∈𝑬，其中 𝒖∈𝑨或者𝒗∈𝑨 且|𝑨|大小最小 顶点覆盖是NP-完全问题

顶点覆盖问题 近似算法A的基本思想 b b c c d d b c d a e e f f g g a e f g 随机选一条边(u,v)，删除与u或v相连的边 重复，直到无边，将选中的边的端点作为结果 b b c c d d b c d a e e f f g g a e f g 算法解{b,c,e,f,d,g} 最优解{b,c,d}

顶点覆盖问题 近似算法A性能分析 时间复杂度为O(|E|) Ratio Bound为2 令 𝑬 ′ 是选中的边的集合，若 (𝒖,𝒗)∈𝑬 ′ ，则与(𝒖,𝒗)相邻的边都被删除，因此 𝑬 ′ 中无相邻边 每次选择一条边，即每次有两个顶点加入近似解A， 𝑨 =𝟐| 𝑬 ′ | 设𝑶𝑷𝑻是最优解， 𝑶𝑷𝑻必须覆盖 𝑬 ′ ，由于 𝑬 ′ 中无邻接边，𝑶𝑷𝑻至少包含 𝑬 ′ 中每条边的一个顶点 𝑬 ′ ≤|𝑶𝑷𝑻|， 𝑨 =𝟐 𝑬 ′ ≤𝟐|𝑶𝑷𝑻|，即 |𝑨| |𝑶𝑷𝑻| ≤𝟐

集合覆盖问题 输入：有限集𝑼={𝟏,𝟐,…,𝒏}，子集合的集合𝑺={ 𝒔 𝟏 , 𝒔 𝟐 ,⋯, 𝒔 𝒎 }， 𝒔 𝒊 ⊆𝑼 输出： 𝑨⊆𝑺，满足 𝑼= ⋃ 𝒔∈𝑨 𝒔 且|𝑨|最小

集合覆盖问题 s1 s2 s3 s4 s5 s6 最优解{ 𝒔 𝟑 , 𝒔 𝟒 , 𝒔 𝟓 }

集合覆盖问题 近似算法A的基本思想 s3 s4 s5 s1 近似解{ 𝒔 𝟏 , 𝒔 𝟒 , 𝒔 𝟓 , 𝒔 𝟑 } s2 s6 每次迭代选择能覆盖最多未被覆盖元素的子集 s3 s4 s5 s1 近似解{ 𝒔 𝟏 , 𝒔 𝟒 , 𝒔 𝟓 , 𝒔 𝟑 } s2 s6

集合覆盖问题 近似算法A性能分析 时间复杂度 每次选能覆盖最多未被覆盖元素的子集 |𝑺|个子集，判断覆盖未被覆盖元素个数，一次选择要计算 𝑺 |𝑼|次 共选择 𝐦𝐢𝐧 { 𝑺 ,|𝑼|} 次 总计算复杂度 𝑺 |𝑼| 𝐦𝐢𝐧 { 𝑺 ,|𝑼|}

集合覆盖问题 近似算法A性能分析 Ratio Bound为 ln 𝒏 +𝟏 令𝑶𝑷𝑻为最优解，其每个元素平均覆盖代价为 |𝑶𝑷𝑻| 𝒏 算法A第一次迭代时，必然有一个集合s1，其平均代价 𝟏 𝒏 𝟏 ≤ |𝑶𝑷𝑻| 𝒏 ，不然𝑶𝑷𝑻不存在的 同理，设第i次迭代时剩余 𝒌 𝒊 个元素未被覆盖，对这 𝒌 𝒊 个元素覆盖最优解为 𝑶𝑷𝑻 𝒊 ，则必然存在一个集合s2， 𝟏 𝒏 𝒊 ≤ 𝑶𝑷𝑻 𝒊 𝒌 𝒊 ≤ 𝑶𝑷𝑻 𝒌 𝒊 。算法A的代价 𝟏 𝒏 𝟏 𝒏 𝟏 + 𝟏 𝒏 𝟐 𝒏 𝟐 +…+ 𝟏 𝒏 𝒊 𝒏 𝒊 ≤ 𝑶𝑷𝑻 𝒌 𝒊 𝒏 𝒊 ≤|𝑶𝑷𝑻| 𝒙=𝟏 ∞ 𝟏 𝒙 ≤|𝑶𝑷𝑻|( ln 𝒏 +𝟏) 剩下ki个元素最多需要OPT个集合覆盖，假设也是需要OPT个集合覆盖，则1/s<=OPT/ki。k1==n,k2==n-n1,k3==n-n1-n2…. 𝑛 𝟏 𝑘 𝟏 = 𝑛 𝟏 𝑛 𝑛 𝟐 𝑘 𝟐 = 𝑛 𝟐 𝑛− 𝑛 𝟏 𝑛 𝟑 𝑘 𝟑 = 𝑛 𝟑 𝑛− 𝑛 𝟏 − 𝑛 𝟐

旅行商问题(Hamilton环) 给定一个图，Hamilton环是包含图中每个顶点一次的简单环

旅行商问题(Hamilton环) 输入：完全无向图𝑮=(𝑽,𝑬)， 每条边(𝒂,𝒃)存在一个权值𝑪(𝒂,𝒃)， 边满足三角不等式𝑪 𝒂,𝒃 +𝑪 𝒃,𝒄 ≥𝑪(𝒂,𝒄) 输出：边权值和最小的Hamilton环

旅行商问题(Hamilton环) 近似算法A的基本思想 先构造最小生成树，先序遍历的顺序构造环 e e e a a a f f f b b c h h c c d g d g d g 构造最小生成树 先序遍历 近似解 最优解

旅行商问题(Hamilton环) 近似算法A性能分析 时间复杂度 构造最小生成树𝑶( |𝑽| 𝟐 ) 先序遍历𝑶(|𝑽|) 总时间复杂度𝑶( |𝑽| 𝟐 )

旅行商问题(Hamilton环) 近似算法A性能分析 Ratio Bound为2 令𝑶𝑷𝑻为最优解，路径权值和即代价为𝑪(𝑶𝑷𝑻) 𝑶𝑷𝑻环中删除一条边可得一棵生成树𝑻 ，代价𝑪(𝑻) 构造的最小生成树 𝑻 𝒎𝒊𝒏 ，𝑪 𝑻 𝒎𝒊𝒏 ≤𝑪 𝑻 ≤𝑪(𝑶𝑷𝑻) 先序遍历实际上对 𝑻 𝒎𝒊𝒏 中所有的边走了2次，即代价为𝟐𝑪 𝑻 𝒎𝒊𝒏 按先序遍历的节点第一次访问的顺序构造的Hamilton环为𝑨，是先序遍历2次访问满足三角不等式的简化 𝑪 𝑨 ≤𝟐𝑪 𝑻 𝒎𝒊𝒏 ≤𝟐𝑪(𝑶𝑷𝑻) b c b c a,b,a,c,a a,b,c,a

Max-3CNF(随机近似) 输入： 输出： n个布尔变量组成的m个析取范式的合取范式 对n个变量赋值，使m个析取范式为1的个数最多 ( 𝒙 𝟏 ∨ 𝒙 𝟐 ∨ 𝒙 𝟑 )∧( 𝒙 𝟏 ∨ 𝒙 𝟐 ∨ 𝒙 𝟑 )∧( 𝒙 𝟏 ∨ 𝒙 𝟐 ∨ 𝒙 𝟑 )

Max-3CNF(随机近似) 随机近似算法A Random-Max-3CNF(CNF) For 对于CNF中的每个变量x Do 随机地为x赋值: x =0的概率为1/2, x =1的概率为1/2;

Max-3CNF(随机近似) 随机近似算法A分析 随机近似比为8/7 第 i 个析取范式 𝒙 𝒊𝟏 ∨ 𝒙 𝒊𝟐 ∨ 𝒙 𝒊𝟑 ， n个变量随机赋0或1，m个析取范式 第 i 个析取范式 𝒙 𝒊𝟏 ∨ 𝒙 𝒊𝟐 ∨ 𝒙 𝒊𝟑 ， 其值为0的概率1/8 其值为1的概率1-1/8=7/8 3CNF中值为1的个数7m/8 最优解中值为1的个数为m，随机近似比8/7

顶点覆盖问题(线性规划) 输入：无向图 𝑮=(𝑽,𝑬)，顶点𝒗有权值𝝎(𝒗) 输出：𝑨⊆𝑽，满足 将问题换另一种描述 ∀ 𝒖,𝒗 ∈𝑬，其中 𝒖∈𝑨或者𝒗∈𝑨 且𝝎 𝑨 = 𝒗∈𝑨 𝝎(𝒗) 最小 将问题换另一种描述 假设𝑨为一个覆盖， 若𝒗∈𝑨，令𝒙 𝒗 =𝟏， 否则𝒙 𝒗 =𝟎 要覆盖所有的边，则对任意边∀ 𝒖,𝒗 ∈𝑬，需满足𝒙 𝒖 +𝒙 𝒗 ≥𝟏

顶点覆盖问题(线性规划) 问题可描述为一个0-1整数规划问题 整数规划是NP完全的 线性规划是多项式可解的 目标：最小化 𝒗∈𝑽 𝝎 𝒗 𝒙(𝒗) 约束： ∀ 𝒖,𝒗 ∈𝑬,𝒙 𝒖 +𝒙 𝒗 ≥𝟏，且𝒙 𝒗 ={𝟎,𝟏} 整数规划是NP完全的 线性规划是多项式可解的 可放宽限制条件，设𝒙 𝒗 取值可为浮点数，问题转换为线性规划问题 使用线性规划求解，得到线性最优解𝒙 𝒗 若𝒙 𝒗 ≥ 𝟏 𝟐 ，令𝒙 𝒗 =𝟏 否则令𝒙 𝒗 =𝟎

顶点覆盖问题(线性规划) 近似算法A Approx(G, w) C=0; 计算线性规划问题的最优解x; For each vV Do If x(v)1/2 Then C=C{v}; /*用四舍五入法把线性规划的解近似为0-1规划的解 */ 5. Return C.

顶点覆盖问题(线性规划) 近似算法A分析 A的近似比为2 ∀ 𝒖,𝒗 ∈𝑬,𝒙 𝒖 +𝒙 𝒗 ≥𝟏，故𝒙 𝒖 和𝒙 𝒗 至少有一个大于等于1/2，即 𝒖 或 𝒗 至少有一个在覆盖中 令线性规划最优解代价为 𝐳 𝐳= 𝒗∈𝑽 𝝎 𝒗 𝒙(𝒗) ≥ 𝒗∈𝑽,𝒙 𝒗 ≥𝟏/𝟐 𝝎 𝒗 𝒙(𝒗) ≥ 𝒗∈𝑽,𝒙 𝒗 ≥𝟏/𝟐 𝝎 𝒗 𝟏 𝟐 ≥ 𝒗∈𝑨 𝝎 𝒗 𝟏 𝟐 ≥ 𝟏 𝟐 𝝎 𝑨 因为𝑶𝑷𝑻是线性规划可能解, 故𝝎 𝑶𝑷𝑻 ≥𝐳≥ 𝟏 𝟐 𝝎 𝑨

子集和问题 输入 输出 给定正整数集合𝑺={ 𝒙 𝟏 , 𝒙 𝟐 ,⋯ 𝒙 𝒏 }和一个正整数𝑻 最大化 𝒙∈𝑨 𝒙 最大化 𝒙∈𝑨 𝒙 其中𝑨⊆𝑺，满足 𝒙∈𝑨 𝒙 ≤𝑻 𝑺= 𝟑,𝟒,𝟓,𝟕,𝟏𝟎 , 𝑻=𝟗 𝑨= 𝟒,𝟓 , 𝒙∈𝑨 𝒙 =9最大不超过𝑻的结果

子集和问题 穷举方法 时间复杂度是指数级的 给定正整数集合𝑺={ 𝒙 𝟏 , 𝒙 𝟐 ,⋯ 𝒙 𝒏 }和一个正整数𝑻 … 𝑷 𝟎 = 𝟎 𝑷 𝟏 = 𝟎, 𝒙 𝟏 𝑷 𝟐 = 𝟎, 𝒙 𝟏 , 𝒙 𝟐 , 𝒙 𝟏 + 𝒙 𝟐 𝑷 𝟑 ={𝟎, 𝒙 𝟏 , 𝒙 𝟐 , 𝒙 𝟏 + 𝒙 𝟐 , 𝒙 𝟑 , 𝒙 𝟏 + 𝒙 𝟑 , 𝒙 𝟐 + 𝒙 𝟑 , 𝒙 𝟏 + 𝒙 𝟐 + 𝒙 𝟑 } … 𝑷 𝒊 = 𝑷 𝒊−𝟏 ∪{ 𝑷 𝒊−𝟏 + 𝒙 𝒊 } 每步删除大于𝑻的结果 在 𝑷 𝒏 中找最大的即为最终结果 时间复杂度是指数级的

子集和问题 近似算法A 长度是指数级的 对穷举方法进行修改，减少 𝑷 𝒊 的长度 穷举法中： 𝑷 𝒊 = 𝑷 𝒊−𝟏 ∪{ 𝑷 𝒊−𝟏 + 𝒙 𝒊 } 给定一误差参数𝜹，每次将 𝑷 𝒊 中相差不超过𝜹的数只用一个表示 长度是指数级的 Trim(P, δ) m=P; L=P; last=P[0]; For i=2 To m Do If last*(1+δ) < P[i] Then P[i]加入到L末尾; last=P[i]; Return L P =〈10, 11, 12, 15, 20, 21, 22, 23, 24, 29〉 δ = 0.1 L =〈10, 12, 15, 20, 23, 29〉

子集和问题 近似算法A 长度是指数级的 对穷举方法进行修改，减少 𝑷 𝒊 的长度 穷举法中： 𝑷 𝒊 = 𝑷 𝒊−𝟏 ∪{ 𝑷 𝒊−𝟏 + 𝒙 𝒊 } 给定一误差参数𝜹，每次将 𝑷 𝒊 中相差不超过𝜹的数只用一个表示 长度是指数级的 Trim(P, δ) m=P; L=P; last=P[0]; For i=2 To m Do If last*(1+δ) < P[i] Then P[i]加入到L末尾; last=P[i]; Return L Approx(S, T, ) n=S; L0={0} For i=1 To n Do Li = Li-1 ∪ {Li-1+xi} Li =Trim(Li ,  /n) 从Li中删除大于T的元素; Return Ln中最大值.

子集和问题 近似算法A分析 时间复杂度，与修剪后 𝑳 𝒊 的长度相关，而 𝑳 𝒊 的长度是 𝟏 𝜺 的多项式 令修剪后的 𝑳 𝒊 ={𝟎, 𝒛 𝟏 , 𝒛 𝟐 ,⋯ 𝒛 𝒌 , 𝒛 𝒌+𝟏 } ，则有 𝒛 𝒊+𝟏 > 𝒛 𝒊 (𝟏+ 𝜺 𝒏 ) 假设 𝑳 𝒊 中𝒌+𝟐个元素， 𝑳 𝒊 𝟎 =𝟎， 𝑳 𝒊 𝟏 = 𝒛 𝟏 ， 𝑳 𝒊 𝟐 > 𝒛 𝟏 (𝟏+ 𝜺 𝒏 )， 𝑳 𝒊 𝟑 > 𝒛 𝟏 (𝟏+ 𝜺 𝒏 ) 𝟐 ， 𝑳 𝒊 𝟒 > 𝒛 𝟏 (𝟏+ 𝜺 𝒏 ) 𝟑 ，…， 𝑳 𝒊 𝒌+𝟏 > 𝒛 𝟏 (𝟏+ 𝜺 𝒏 ) 𝒌 ， ∵ 𝑳 𝒊 中所有元素都小于𝑻，∴ 𝒛 𝟏 (𝟏+ 𝜺 𝒏 ) 𝒌 ≤𝑻， ∵ 𝒛 𝟏 是正整数，∴ (𝟏+ 𝜺 𝒏 ) 𝒌 ≤𝑻，有 𝒌≤ log 𝟏+ 𝜺 𝒏 𝑻 = ln 𝑻 ln (𝟏+ 𝜺 𝒏 ) 𝑳 𝒊 =𝒌+𝟐≤𝟐+ ln 𝑻 ln (𝟏+ 𝜺 𝒏 ) ，∵ lim 𝒙→𝟎 ln (1+𝒙) 𝒙 =𝟏， ∴ 𝑳 𝒊 ≤𝟐+ 𝒏 ln 𝑻 𝜺

子集和问题 近似算法A分析 近似比为 𝟏+𝟐𝜺 令𝒚属于穷举法(修剪前)的 𝑷 𝒊 ， 𝒛属于修剪后的 𝑳 𝒊 令𝒚属于穷举法(修剪前)的 𝑷 𝒊 ， 𝒛属于修剪后的 𝑳 𝒊 对于 𝑷 𝒊 中任意𝒚，在 𝑳 𝒊 中存在𝒛，使得 𝒚 (𝟏+ 𝜺 𝒏 ) 𝒊 ≤𝒛≤𝒚 𝒊=𝟎时， 𝑷 𝒊 = 𝟎 ， 𝑳 𝒊 = 𝟎 ，显然成立 假设𝒊=𝒌时有 𝒚 (𝟏+ 𝜺 𝒏 ) 𝒌 ≤𝒛≤𝒚 现证当𝒊=𝒌+𝟏时也成立。 𝑷 𝒌+𝟏 = 𝑷 𝒌 ∪{ 𝑷 𝑘 + 𝒙 𝒌+𝟏 }， 𝒚 (𝟏+ 𝜺 𝒏 ) 𝒌 + 𝒙 𝒌+𝟏 ≤𝒛+ 𝒙 𝒌+𝟏 ≤𝒚+ 𝒙 𝒌+𝟏 ∵ 𝒚+ 𝒙 𝒌+𝟏 (𝟏+ 𝜺 𝒏 ) 𝒌+𝟏 < 𝒚 (𝟏+ 𝜺 𝒏 ) 𝒌 + 𝒙 𝒌+𝟏 ， ∴ 𝒚+ 𝒙 𝒌+𝟏 (𝟏+ 𝜺 𝒏 ) 𝒌+𝟏 ≤𝒛+ 𝒙 𝒌+𝟏 ≤𝒚+ 𝒙 𝒌+𝟏 ， 𝑷 𝒏 中最优解 𝒚 ∗ 满足 𝒚 ∗ (𝟏+ 𝜺 𝒏 ) 𝒏 ≤𝒛≤ 𝒚 ∗ ， 𝑳 𝒏 最优解 𝒛 ∗ 有 𝒚 ∗ 𝒛 ∗ ≤ 𝒚 ∗ 𝒛 ≤ 𝟏+ 𝜺 𝒏 𝒏 ≤ 𝒆 𝜺 ≤𝟏+𝟐𝜺，当𝜺<𝟏 𝒚 𝟏+ 𝜺 𝒏 𝒌 (𝟏− 1 𝟏+ 𝜺 𝒏 )+ 𝒙 𝒌+𝟏 (1− 1 𝟏+ 𝜺 𝒏 𝒌+𝟏 )>0 lim 𝒏→∞ 𝟏+ 𝟏 𝒏 𝒏 =𝒆

考虑这样一个应用问题，市场上销售的某型钢材的长度为1，现需要一些长度分别为 𝑎 1 , 𝑎 2 ,…, 𝑎 𝑁 的小钢条（ 𝑎 𝑖 ≤1, 1≤𝑖≤𝑁），问至少要买多少根钢条进行切割？请给出一个多项式时间算法，使得买的钢条尽可能少，并分析该算法的近似比。 给定n个任务以及两机器，每个任务所需的处理时间为p1, p2, … , pn。一个任务可由任一台机器执行，但不能拆开分配给多台机器执行。一台机器在一时间只能处理一个任务。求两台机器的最短最长执行时间。有一算法，它将这n个任务依次分配给这两机器。算法在分配一任务时，总是将任务分配给到目前为止分配了最少工作时间的机器。请给出该算法的近似比。