计算机算法基础 第2版 课件 第15章 近似算法

第15

章

近似算法1问题定义

2顶点复盖问题 5货郎担向题

8集合复盖问题

16MAX-3-SAT问题

25加权的顶点复盖问题 29子集和问题 33鸿沟定理和不可近似性

462如果一个问题是个NPC问题，很可能不存在多项式的算法，而在实际工作中人们又经常碰到NPC的问题而且必须要解决，怎么办呢？找一个快速的近似算法(Approximationalgorithm)或者一个启发式算法(Heuristicalgorithm)成为解决问题的最重要手段。这两者的区别在于前者保证计算结果与最佳解之间的差别不超过一个范围，而后者不能定量地给予保证，它的实际效果往往通过仿真(simulation)实验予以证实。这一章，我们只讨论近似算法。NP难的优化型问题的解一般对应一个目标值C并要求这个值最大，或最小，或最长，或最短，等等。我们可以把它们分为两大类，一类是要求目标值C最大，另一类是要求目标值C最小，分别称为最大化(maximization)问题和最小化(minimization)问题。1. 问题定义3

4

5计算图G(V,E)的顶点复盖的一个简单的近似算法是：任取一条边，(u,v)

E，把点u和v加入集合S中。把被顶点u和v复盖的边从图G中刪去。如果图G中不再有边，那说明所有的边已被S中点所复盖，否则，在剩下的边中重复步(1)(2)直到图中不再有边为止。Approx-Vertex-Cover(G(V,E))S

；

//集合S初始为空

while

E

selectanedge(u,v)

E

//任选一条边(u,v)

S

S

{u,v} //把u

和v加入集合S

E

E–{(x,y)|x

{u,v}ory

{u,v}}

//刪除与u

或v关联的边endwhilereturn

SEnd2.

顶点复盖问题6例

(a)

图Gabefdcgh(b)

选(a,e)，S={a,e}。虚线是刪除的边。abefdcgh(c)

选(c,f)，S={a,e,c,f}。abefdcgh(d)

选(d,h)，S={a,e,c,f,d,h}。abefdcgh(f)

最小复盖是5个点，Sopt={a,b,f,g,d}。abefdcgh(e)

近似解S={a,e,c,f,d,h}。abefdcgh7定理15.1

算法Approx-Vertex-Cover是一个2-近似算法。证明：当算法结束时，图中所有边都因与集合S中某个点关联而被删去，因而S是一个顶点复盖。设算法一共选了k条边，那么这个解S的目标值为C

=

2k。再考虑最佳解C*。我们注意到，在近似算法每次选取的边(u,v)中，任何最佳解必须至少包含顶点u或v。又因为近似算法所选取的边都有不同的顶点，所以任何最佳解必须包含集合S中的至少k个顶点。因而有C/C*

2k/k=2。

8我们可证明，对一般的货郎担问题，不存在有常数倍近似度的近似算法。但是，对于特殊的一类货郎担问题有很好的近似算法。下面先讨论这一特殊类货郎担问题，然后再讨论一般的货郎担问题。满足三角不等式关系的货郎担问题加权图G中，如果任意三个顶点u,v,w

V之间的边满足关系w(w,u)

w(u,v)

+w(v,w)，那么称这个图满足三角不等式。定义15.4

满足三角不等式的货郎担问题定义如下：给定一个没有负权值的完全图G(V,E)和一个正数k，假设图G满足三角不等式，判断G是否含有一条货郎担回路使得它的总权值小于等于k？定理15.2

满足三角不等式关系的货郎担问题是个NP-难问题。证明：

我们把一般的货郎担问题多项式归约为这个满足三角不等式关系的货郎担问题。(接下页)3.

货郎担问题9证明(继续1)：假设一般的货郎担问题的一个特例是一个没有负权值的完全图G(V,E)和正数k。现在，我们由此构造一个满足三角不等式的图G’(V’,E’)和正数k’。设|V|=n，这个构造步骤如下：Construct-Triangle-TSP(G(V,E))G’(V’,E’)

G(V,E) //复制M

max{w(u,v)|w(u,v)

E} //E中最大的边的权值Mforeach(u,v)

E’ w’(u,v)

w(u,v)+Mendfork’

k+nMEnd这显然是个多项式算法，并且G’满足三角不等式，这是因为：任取图G’三点，u,v,w，我们有：w’(w,u)=w(w,u)+M

M+M

(w(u,v)+M)+(w(v,w)+M)=w’(u,v)+w’(v,w)。(接下页)10

11有2-近似度的货郎担问题的算法2-Approx-Triangle-TSP(G(V,E) //G满足三角不等式取任一顶点

r

V用Prim算法获得G的一棵以r为根的最小支撑树T从r开始，对T做DFS搜索，并把顶点按发现时刻顺序排序假设<v1,v2,…,vn>是DFS得到的顶点序列，其中v1=r输出货郎担回路:C=<v1,v2,…,vn,v1>End算法2-Approx-Triangle-TSP的近似度为2的证明让我们沿着下面的路径走一遍。从点r开始，假设当前的栈顶是点u，如果DFS下一步操作是向堆栈压入一个点v，那么我们从u走到v。如果是弹出u，回溯到它父亲w，那么我们就从u走到w。总之，我们的路径是从当前栈顶走到下一个栈顶。DFS完成时，堆栈为空，路径结束。(接下页)12算法2-Approx-Triangle-TSP的近似度为2的证明(继续1)考虑T中任一条边(a,b)，a是b的父亲。边(a,b)被DFS访问两次。第一次，由点a发现顶点b，向堆栈压入b，我们的路径经过(a,b)一次。第二次，是在弹出点b时，栈顶又回到点a，我们的路径又经过边(b,a)一次。下图(15-2)显示，这条路径正好是沿着T的轮廓线的回路C’。这里，轮廓线是经过T中每条边的两侧各一次的一条连续的回路。从顶点r开始，这条回路经过的顶点序列称为轮廓线序列。radbcehgf(a)一棵支撑树Tradbcehgf(b)

轮廓线:<r,a,b,a,c,a,r,d,e,f,e,g,e,h,e,d,r>13算法2-Approx-Triangle-TSP的近似度为2的证明(继续2)因为算法输出的顶点序列C是按照顶点被压入堆栈的顺序，记录的顶点序列，所以它是轮廓线序列的一个子序列。由三角不等式关系可知，这个子序列形成的回路C的总长小于等于轮廓线C’的总长。又因为轮廓线C’的总长正好是树T中所有边权值总和的2倍，我们有W(C)

W(C’)=2W(T)。因为图G的最小货郎担回路C*包含G的一个支撑树，它的总权值大于等于最小支撑树T的总权值，所以我们有： W(C)

2W(T)

2W(C*)。因此算法Approx-Triangle-TSP有2-近似度。证毕。显然，算法Approx-Triangle-TSP的时间复杂度是O(n2)。14

15Hamilton-Based-on-A

(继续)：4 如果W(C)=n，则C是图G的一条哈密尔顿回路，否则原图G没有哈密尔顿回路。End上面这个算法的正确性解释如下。如果|C|=n，那么C上每条边权值必须等于1。因为权值等于1的边必定是原图G中的边，所以C也是G里的一条哈密尔顿回路。反之，如果|C|>n，那么，C必定含有一条不在原图G中的边，因此它的权值至少是|C|

(n-1)+(

n+1)=(

+1)n>

n。这时，我们可断定G’中不存在一条总权值是n的货郎担回路，否则，这个实例的近似度为|C|/n>

，这与算法A的近似度矛盾。所以原图G没有哈密尔顿回路。因为如果P

NP，哈密尔顿回路问题没有多项式算法，因此算法A不可能存在。定理15.3证毕。

16

4.

集合复盖问题17

18复杂度解释(继续)又因为每选一个集合，至少可以复盖U中一个元素，所以最多只要循环m次。当然，循环次数也不会超过n次，所以有复杂度O(mn

Min(m,n))下面定理给出近似度。

19证明(继续1)现在，让我们把每个集合Si对应的代价1平分到被它第一次复盖的元素上去，也就是被Si复盖但未被S1,S2,…,Si-1

复盖的元素上去。这样，每个元素x

U

都被赋予一个代价c(x)，并有c(U)=|C|=h。看一个例子。假设有F={S1,S2,S3,S4,S5}，其中，S1={a,b,c},S2={a,d,e},S3={b,e,f},S4={c,d,g},S5={a,d,f}。U

=

{a,b,c,d,e,f,g}。算法依次选取集合以及各元素代价如下：第1次，选S1={a,b,c},代价c(a)=c(b)=c(c)=1/3，更新U={d,e,f,g}第2次，选S2={a,d,e},新复盖元素有代价c(d)=c(e)=1/2，U={f,g}第3次，选S3={b,e,f},新复盖元素有代价c(f)=1，U

={g}第4次，选S4={c,d,g},新复盖元素有代价c(g)=1，U

=

。上例中，算法产生的复盖是C={S1,S2,S3,S4}。

(接下页)20

21证明(继续

3)让我们定义一个集合序列，P0

=S，P1

=S–S1，P2

=S–(S1

S2)，…，Ph

=S-(S1

S2

…

Sh)。集合Pi(1

i

h)中元素是

S中还没有被

S1

S2

…

Si所复盖的元素。注意，这里的

S是最优解C*中的一个集合，而S1，S2，…，Si

是我们算法所选取的集合。记ui

=|Pi|，即Pi

中元素个数。因为算法每选一个集合

Si只会减少

S中未被复盖的元素。因此有u0

u1

u2

…

uh

=0。不失一般性，可假设uh

是序列中第一个0。(接下页)22

23

24

25

5. MAX-3-SAT问题26我们假定

含n个变量，x1,x2,…,xn,并且每个变量xi和它的非

xi不同时出现在一个子句中，因为这样的子句可被任何一组赋值满足，不须考虑。下面给出一个非常简单的随机算法来解这个MAX-3-SAT问题。Randomized-MAX-3-SAT(

)for

i

1to

n v

Randomnumber(0or1) //产生0或1的随机数，各占50%机率

if

v=1

then

xi

1

xi

0

else

xi

0

xi

1

endifendforEnd显然，这是个多项式算法。下面的定理证明它有很好的近似度。27

28

29

6. 加权的顶点复盖问题30

31线性规划解(继续2)：显然，任一个0-1整数规划的可行解(包括最佳解)也是变化后实数型的线性规划的一个可行解。可行解是指满足约束条件的解。所以，线性规划的最佳解可作为0-1整数规划最佳解的一个下界。下面算法显示如何用线性规划来得出原问题的一个近似解。Approx-Min-Weight-VC(G,w)C

//顶点复盖初始为空求出上述线性规划的最佳解

x(v) //x(v)表示向量(x(v1),x(v2),…,x(vn))foreachv

V ifx(v)

1/2 thenC

C

{v} endifendforreturn

CEnd32

33在第14章我们已知子集和问题是个NPC问题。这一节我们讨论它的近似解，并通过它进一步理解近似机制和完全多项式近似机制的概念和设计方法。我们先定义一个与之关联的优化型问题。

7. 子集和问题34一个保证最优解的指数型算法设S={x1,x2,…,xn}，这个指数型算法的思路就是穷举法，它遍历所有可能的子集及其子集和。从空集开始，先检查{x1}的子集，然后遍历{x1,x2}的子集，再遍历所有{x1,x2,x3}的子集，等等，直至所有{x1,x2,…,xn}的子集。为简化记号，如果x表示一个整数，我们用S+x表示把集合S中每个数字加上x后的集合，即S+x={s+x|s

S}。为了突出思路，下面的算法只给出子集和的值，而不记录子集中具体是那几个数。当需要实现算法时，读者可自己插入这一工作。在后面的例子中，我们会介绍如何记录具体数字的方法。遍历过程中，如发现有子集和大于目标值

t者，则丢弃该子集。算法如下:(见下页)35Exact-Subset-Sum(S,t)n

|S|L0

{0} //初始，集合L0只含一个子集，即空集，其和为0for

i

1to

n

Li

Li-1

(Li-1+xi)

//含所有不同的子集和，删除重复的和

剔除Li中所有大于t的数字

//大于t的子集和不可能是解endforreturn

Ln

中最大数End归纳法可证，Li

包含{x1,x2,…,xi}的所有不大于t的子集和。算法结束时，Ln

包含S的所有不大于t的子集和。Ln

中最大值必是最优解。因为Li+1的元素可能是Li的两倍，这是指数型算法。下面例子中，我们在Li

中数字x后面加上+号或者-号。x+表示x是由Li-1

中某个数，加上xi所得；而x-表示x是原Li-1中一个数。36例15.3

设S={1,4,5,7}和t

=14。演示算法Exact-Subset-Sum逐步产生的集合Li

(1

i

4)，并找出最佳解。解：L0

{0}L1

{0-,1+} (1+表示该数字含x1=1)L2

{0-,1-,4+,5+} (+表示该数字含x2=4)L3

{0-,1-,4-,5-,6+,9+,10+} (+表示含x3，另外，5+删除)L4

{0-,1-,4-,5-,6-,9-,10-,7+,8+,11+,12+,13+}

(16+,17+刪除)13是最佳子集和。根据+、-号，我们可以把对应子集找到:从L4中13+知该子集含x4=7。

13-7=6。从L3

中

6+知该子集含x3=5。6–5=1。从L2

中1-知该子集不含x2。从L1

中1+知该子集含x1=1。1–1

=0，搜索结束。子集为{1,5,7}。37子集和问题的一个完全多项式近似机制改进指数型算法的主要思路是简化Li。如果Li中两个数字很接近，则去掉一个。这可能会影响解的近似度，但让它在可控范围内。我们用一个修整参数

来控制，0<

<1。假设

L含排好序的m个数字，y1

y2

…

ym。保留y1，从y2开始，遵循以下规则：设当前保留的最大数是x，而下一个数是

y，如果y

(1+

)x，则刪除y

(称y被x修整)，否则保留y。例15.4用修整参数

=0.1修整序列，(1+

)

=1.1。

L

={10,11,12,15,20,21,22,23,24,29}。解：保留10。11

1.1

10,刪除11。12>1.1

10,保留12。15>1.1

12,保留15。20>1.1

15,保留20。21<1.1

20,刪除21。22

1.1

20,刪除22。23>1.1

20,保留23。24<1.1

23,刪除24。29>1.1

23,保留29。刪除后的集合为L’={10,12,15,20,23,29}。38给定排好序的序列L={y1,y2,…,ym}，用修整参数

对L进行修整的过程可用下面伪码实现。Trim(L,

)m

|L|L’

{y1} //始终保留y1last

y1 //扫描到目前为止，最后一个被保留的数字for

i

2to

m

if

yi

>last

(1+

)

then

L’

L’

{yi} //把yi

加到L’中，放在最后

last

yi

endifendforreturn

L’End算法Trim的复杂度是O(|L|)。39下面是子集和的一个完全多项式近似机制Approx-Subset-Sum(S,t,

)n

|S|L0

{0}for

i

1to

n

Li

Li-1

(Li-1+xi) //需要删除重复的子集和

把Li中子集和排序

//这一行和上一行可用合并算法同时完成

Li

Trim(Li,

/2n)

删除Li

中大于t的子集和endforreturn

Ln

中最大数z*End下面证明上面的算法是一个完全多项式近似机制。我们定义P0={0}，Pi

=Pi-1

(Pi-1+x)

(1

i

n)。注意，Pi

包含了集合{x1,x2,…,xi}

的所有可能的子集和，没有任何删除。显然Li

是Pi

的子集。40

41

42

43

44

45

46以上讨论发现，有些NPC的优化型问题可以有常数倍近似度的多项式算法，但是，有些优化型问题却不存在有常数倍近似度的多项式算法。有没有规律可循呢。下面要介绍的鸿沟定理可帮助我们作判断。优化型问题有两类，一类是极小问题，另一类是极大问题。极小问题是希望目标值达到最小，而极大问题是希望目标值达到最大。例如顶点复盖问题是个极小问题，而图的团的问题是个极大向题。对这两类问题，鸿沟定理的描述不同，但是是对称的。8. 鸿沟定理和不可近似性47定理15.10(极小问题的鸿沟定理)假设问题A是个已知的判断型NPC问题，而问题B是个极小问题。如果问题A的任一个实例

可在多项式时间内转化为问题B的一个实例

，并且有:实例

的解是yes，记为A(

)=1，当且仅当实例

有解并且最小目标值w

W，这里，

W可以是一个正常数，也可以是一个与n=|

|有关的正函数;实例

的解是no，记为A(

)=0，当且仅当实例

有解并且最小目标值w

kW，这里k>1是一个正的常数;那么，只要P

NP，就不存在有近似度小于k的问题B的多项式算法。让我们称这样的多项式转化为多项式鸿沟归约。证明：我们注意到，问题B的判断型问题可以这样描述：给定问题B的实例

和期待值W，判断

是否有目标值w

W的解。(接下页)48证明(继续1)：如果存在定理中描述的多项式转化，那么这个转化满足的第(1)条就已证明了问题B的判断型问题也是个NPC问题。如果这个转化还满足(2)，那么，只要P

NP，就不存在有近似度小于k的问题B的多项式算法。所以多项式鸿沟归约要比一般NPC问题的多项式归约要更强。我们用反证法证明，只要P

NP，就不存在有近似度小于k的问题B的多项式算法。为此，让我们假设有近似度小于k的近似算法B*，它在多项式时间内对任一实例

进行运算后得到一个目标值为Z的解。并满足Z/w<k，这里，w是最佳解的目标值。我们证明这不可能，因为，如果是这样，那么，我们可以得到问题A的多项式判定算法如下：(接下页)49证明(继续2)：Algorithm-for-A(

)对问题A的一个实例

进行多项式鸿沟归约，得到问题B的实例

用多项式近似算法B*对实例

进行运算后得到一个目标值为Z的解如果Z<

kW，那么输出A(

)=1(表示yes)，否则A(

)=0(表示no)End这个判断算法是正确的。这是因为，如果Z

<

kW，那么就有：最小值w

Z

<

kW。所以不可能有w

kW，根据多项式鸿沟归约第(2)条，不可能有A(

)=0，所以必然有A(

)=1。反之，如果Z

kW，因为算法B*的近似度小于k，必有Z/w<k，也就是wk>Z。因此有wk>Z

kW，即w>W。根据多项式鸿沟归约的第(1)条，不可能有A(

)=1，所以必定有A(

)=0。这样一来，问题A便可以在多项式时间内被判定，与P

NP矛盾。

50定理15.11(极大问题的鸿沟定理)假设问题A是个已知的判断型NPC问题，而问题B是个极大问题。如果问题A的任一个实例

可在多项式时间内转化为问题B的一个实例

，并且有:实例

的解是yes，即A(

)=1，当且仅当实例

有解并且最大目标值w

W，实例

的解是no，即A(

)=0，当且仅当实例

有解并且最大目标值w

W/k，这里k>1是一个正的常数，那么，只要P

NP，就不存在有近似度小于k的问题B的多项式算法。这样的多项式转化称为多项式鸿沟归约。证明：留给读者。

下面让我们看一个例子，即任务均匀分配问题。51任务均匀分配问题设S={t1，t2，…，tn}是n个任务的集合，这里，tk(1

k

n)是个正整数，它既代表第k个任务，也代表该任务需要的工作量是tk小时。现有

m个工人，而每个工人能够干的工作是这n个任务的一个子集，分别用S1,S2,…,Sm代表。假设每个任务至少有一个工人会干，而每个工人也至少会干其中一个任务。问题：

把这n个任务分配给这m个工人干并使工作量尽量均匀，具体说，就是使得一个工人能分配到的最多工作量