1
第 9章 近似算法
2
第 9章 近似算法迄今为止，所有的 NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。
(1)只对问题的特殊实例求解
(2)用动态规划法或分支限界法求解
(3)用概率算法求解
(4)只求近似解
(5)用启发式方法求解本章主要讨论解 NP完全问题的 近似算法 。
3
9.1 近似算法的性能若一个最优化问题的最优值为 c*,求解该问题的一个近似算法求得的近似最优解相应的目标函数值为 c,则将该 近似算法的性能比 定义为?= 。在通常情况下，该性能比是问题输入规模 n的一个函数 ρ(n),即
≤ ρ(n) 。
cccc *,*m ax
cccc *,*m ax
该 近似算法的相对误差 定义为?= 。若对问题的输入规模 n,有一函数 ε(n) 使得 ≤ ε(n),则称
ε(n) 为该 近似算法的相对误差界 。近似算法的性能比
ρ(n) 与相对误差界 ε(n) 之间显然有如下关系：
ε(n)≤ρ(n) -1。
**ccc?
**ccc?
4
9.2 顶点覆盖问题的近似算法问题描述：无向图 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为空。
5
9.2 顶点覆盖问题的近似算法图 (a)～ (e)说明了算法的运行过程及结果。 (e)表示算法产生的近似最优顶点覆盖 cset，
它由顶点
b,c,d,e,f,g所组成。 (f)是图 G的一个最小顶点覆盖，
它只含有 3个顶点：
b,d和 e。
算法 approxVertexCover的性能比为 2。
6
9.3 旅行售货员问题近似算法问题描述：给定一个完全无向图 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就具有三角不等式性质。
旅行售货员问题的一些 特殊性质,
7
9.3.1 具有三角不等式性质的旅行售货员问题对于给定的无向图 G,可以利用找 图 G的最小生成树 的算法设计找近似最优的旅行售货员回路的算法。
void approxTSP (Graph g)
{
(1)选择 g的任一顶点 r；
(2)用 Prim算法找出带权图 g的一棵以 r为根的最小生成树 T；
(3)前序遍历树 T得到的顶点表 L；
(4)将 r加到表 L的末尾,按表 L中顶点次序组成回路 H,作为计算结果返回；
}
当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的 2倍。
8
9.3.1 具有三角不等式性质的旅行售货员问题举例
(b)表示找到的最小生成树 T； (c)表示对 T作前序遍历的次序； (d)表示 L产生的哈密顿回路 H；
(e)是 G的一个最小费用旅行售货员回路。
9
9.3.2 一般 的 旅行售货员问题在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解 TSP问题的多项式时间近似算法，除非 P=NP。 换句话说，若 P≠NP,
则对任意常数 ρ>1,不存在性能比为 ρ 的解旅行售货员问题的多项式时间近似算法。
10
9.4 集合覆盖问题的近似算法问题描述：给定一个完全无向图 G=(V,E),其每一边
(u,v)∈E 有一非负整数费用 c(u,v)。 要找出 G的最小费用哈密顿回路。
集合覆盖问题的一个实例〈 X,F〉 由一个有限集 X及 X
的一个子集族 F组成。子集族 F覆盖了有限集 X。 也就是说 X
中每一元素至少属于 F中的一个子集，即 X= 。对于 F中的一个子集 C?F,若 C中的 X的子集覆盖了 X,即 X=,则称 C覆盖了 X。 集合覆盖问题就是要找出 F中覆盖 X的最小子集 C*,使得
|C*|=min{|C||C?F且 C覆盖 X}
FS S?
CS S?
11
9.4 集合覆盖问题的近似算法集合覆盖问题举例：
用 12个黑点表示集合 X。
F={S1,S2,S3,S4,S
5,S6,},如图所示。
容易看出，对于这个例子，最小集合覆盖为：
C={S3,S4,S5,}。
12
9.4 集合覆盖问题的近似算法集合覆盖问题近似算法 —— 贪心算法算法的循环体最多执行 min{|X|,|F|}次。
而循环体内的计算显然可在 O(|X||F|)时间内完成。因此，算法的计算时间为 O(|X||F|min{|X|，
|F|})。 由此即知，该算法是一个多项式时间算法。
Set greedySetCover (X,F)
{
U=X；
C=?；
while (U !=?) {
选择 F中使 |S∩U| 最大的子集 S；
U=U-S；
C=C∪{S} ；
}
return C；
}
13
9.5 子集合问题的近似算法问题描述：设子集和问题的一个实例为〈 S,t〉。
其中,S={x1,x2,…,xn}是一个正整数的集合,t是一个正整数。子集和问题判定是否存在 S的一个子集
S1,使得 。tx
Sx
1
14
9.5.1 子集合问题的指数时间算法
int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1； i<=n； i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
删去 L[i]中超过 t的元素；
}
return max(L[n])；
}
算法以集合 S={x1，
x2,…,xn}和目标值 t作为输入。算法中用到将 2个有序表
L1和 L2合并成为一个新的有序表的算法
mergeLists(L1,L2)。
15
9.5.2 子集合问题的完全多项式时间近似格式基于算法 exactSubsetSum,通过对表 L[i]作适当的修整建立一个子集和问题的 完全多项式时间近似格式 。
在对表 L[i]进行修整时，用到一个修整参数 δ,0＜ δ ＜ 1。
用参数 δ 修整一个表 L是指从 L中删去尽可能多的元素，使得每一个从 L中删去的元素 y,都有一个修整后的表 L1中的元素 z满足 (1-δ)y≤z≤y 。 可以将 z看作是被删去元素 y在修整后的新表 L1中的代表。
举例,若 δ=0.1,且 L=〈 10,11,12,15,20,21,22,23,24,29〉，
则用 δ 对 L进行修整后得到 L1=〈 10,12,15,20,23,29〉。
其中被删去的数 11由 10来代表,21和 22由 20来代表,24由 23来代表。
16
9.5.2 子集合问题的完全多项式时间近似格式对有序表 L修整算法
List trim(L,δ)
{ int m=|L|；
L1=〈 L[1]〉 ；
int last=L[1]；
for (int i=2； i<=m； i++) {
if (last<(1-δ)*L[i]) {
将 L[i]加入表 L1的尾部；
last=L[i]；
}
return L1；
}
子集和问题近似格式
int approxSubsetSum(S,t,ε)
{ n=|S|；
L[0]=〈 0〉 ；
for (int i=1； i<=n； i++) {
L[i]=Merge-Lists(L[i-1],
L[i-1]+S[i])；
L[i]=Trim(L[i],ε/n)；
删去 L[i]中超过 t的元素；
}
return max(L[n])；
}
第 9章 近似算法
2
第 9章 近似算法迄今为止，所有的 NP完全问题都还没有多项式时间算法。对于这类问题，通常可采取以下几种解题策略。
(1)只对问题的特殊实例求解
(2)用动态规划法或分支限界法求解
(3)用概率算法求解
(4)只求近似解
(5)用启发式方法求解本章主要讨论解 NP完全问题的 近似算法 。
3
9.1 近似算法的性能若一个最优化问题的最优值为 c*,求解该问题的一个近似算法求得的近似最优解相应的目标函数值为 c,则将该 近似算法的性能比 定义为?= 。在通常情况下，该性能比是问题输入规模 n的一个函数 ρ(n),即
≤ ρ(n) 。
cccc *,*m ax
cccc *,*m ax
该 近似算法的相对误差 定义为?= 。若对问题的输入规模 n,有一函数 ε(n) 使得 ≤ ε(n),则称
ε(n) 为该 近似算法的相对误差界 。近似算法的性能比
ρ(n) 与相对误差界 ε(n) 之间显然有如下关系：
ε(n)≤ρ(n) -1。
**ccc?
**ccc?
4
9.2 顶点覆盖问题的近似算法问题描述：无向图 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为空。
5
9.2 顶点覆盖问题的近似算法图 (a)～ (e)说明了算法的运行过程及结果。 (e)表示算法产生的近似最优顶点覆盖 cset，
它由顶点
b,c,d,e,f,g所组成。 (f)是图 G的一个最小顶点覆盖，
它只含有 3个顶点：
b,d和 e。
算法 approxVertexCover的性能比为 2。
6
9.3 旅行售货员问题近似算法问题描述：给定一个完全无向图 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就具有三角不等式性质。
旅行售货员问题的一些 特殊性质,
7
9.3.1 具有三角不等式性质的旅行售货员问题对于给定的无向图 G,可以利用找 图 G的最小生成树 的算法设计找近似最优的旅行售货员回路的算法。
void approxTSP (Graph g)
{
(1)选择 g的任一顶点 r；
(2)用 Prim算法找出带权图 g的一棵以 r为根的最小生成树 T；
(3)前序遍历树 T得到的顶点表 L；
(4)将 r加到表 L的末尾,按表 L中顶点次序组成回路 H,作为计算结果返回；
}
当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的 2倍。
8
9.3.1 具有三角不等式性质的旅行售货员问题举例
(b)表示找到的最小生成树 T； (c)表示对 T作前序遍历的次序； (d)表示 L产生的哈密顿回路 H；
(e)是 G的一个最小费用旅行售货员回路。
9
9.3.2 一般 的 旅行售货员问题在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解 TSP问题的多项式时间近似算法，除非 P=NP。 换句话说，若 P≠NP,
则对任意常数 ρ>1,不存在性能比为 ρ 的解旅行售货员问题的多项式时间近似算法。
10
9.4 集合覆盖问题的近似算法问题描述：给定一个完全无向图 G=(V,E),其每一边
(u,v)∈E 有一非负整数费用 c(u,v)。 要找出 G的最小费用哈密顿回路。
集合覆盖问题的一个实例〈 X,F〉 由一个有限集 X及 X
的一个子集族 F组成。子集族 F覆盖了有限集 X。 也就是说 X
中每一元素至少属于 F中的一个子集，即 X= 。对于 F中的一个子集 C?F,若 C中的 X的子集覆盖了 X,即 X=,则称 C覆盖了 X。 集合覆盖问题就是要找出 F中覆盖 X的最小子集 C*,使得
|C*|=min{|C||C?F且 C覆盖 X}
FS S?
CS S?
11
9.4 集合覆盖问题的近似算法集合覆盖问题举例：
用 12个黑点表示集合 X。
F={S1,S2,S3,S4,S
5,S6,},如图所示。
容易看出，对于这个例子，最小集合覆盖为：
C={S3,S4,S5,}。
12
9.4 集合覆盖问题的近似算法集合覆盖问题近似算法 —— 贪心算法算法的循环体最多执行 min{|X|,|F|}次。
而循环体内的计算显然可在 O(|X||F|)时间内完成。因此，算法的计算时间为 O(|X||F|min{|X|，
|F|})。 由此即知，该算法是一个多项式时间算法。
Set greedySetCover (X,F)
{
U=X；
C=?；
while (U !=?) {
选择 F中使 |S∩U| 最大的子集 S；
U=U-S；
C=C∪{S} ；
}
return C；
}
13
9.5 子集合问题的近似算法问题描述：设子集和问题的一个实例为〈 S,t〉。
其中,S={x1,x2,…,xn}是一个正整数的集合,t是一个正整数。子集和问题判定是否存在 S的一个子集
S1,使得 。tx
Sx
1
14
9.5.1 子集合问题的指数时间算法
int exactSubsetSum (S,t)
{
int n=|S|；
L[0]={0}；
for (int i=1； i<=n； i++) {
L[i]=mergeLists(L[i-1],L[i-1]+S[i])；
删去 L[i]中超过 t的元素；
}
return max(L[n])；
}
算法以集合 S={x1，
x2,…,xn}和目标值 t作为输入。算法中用到将 2个有序表
L1和 L2合并成为一个新的有序表的算法
mergeLists(L1,L2)。
15
9.5.2 子集合问题的完全多项式时间近似格式基于算法 exactSubsetSum,通过对表 L[i]作适当的修整建立一个子集和问题的 完全多项式时间近似格式 。
在对表 L[i]进行修整时，用到一个修整参数 δ,0＜ δ ＜ 1。
用参数 δ 修整一个表 L是指从 L中删去尽可能多的元素，使得每一个从 L中删去的元素 y,都有一个修整后的表 L1中的元素 z满足 (1-δ)y≤z≤y 。 可以将 z看作是被删去元素 y在修整后的新表 L1中的代表。
举例,若 δ=0.1,且 L=〈 10,11,12,15,20,21,22,23,24,29〉，
则用 δ 对 L进行修整后得到 L1=〈 10,12,15,20,23,29〉。
其中被删去的数 11由 10来代表,21和 22由 20来代表,24由 23来代表。
16
9.5.2 子集合问题的完全多项式时间近似格式对有序表 L修整算法
List trim(L,δ)
{ int m=|L|；
L1=〈 L[1]〉 ；
int last=L[1]；
for (int i=2； i<=m； i++) {
if (last<(1-δ)*L[i]) {
将 L[i]加入表 L1的尾部；
last=L[i]；
}
return L1；
}
子集和问题近似格式
int approxSubsetSum(S,t,ε)
{ n=|S|；
L[0]=〈 0〉 ；
for (int i=1； i<=n； i++) {
L[i]=Merge-Lists(L[i-1],
L[i-1]+S[i])；
L[i]=Trim(L[i],ε/n)；
删去 L[i]中超过 t的元素；
}
return max(L[n])；
}
