计算机算法基础 第2版 习题及答案 第15章 .docx

PAGE12

第15章 近似算法

找出一类图的例子说明近似算法Approx-Vertex-Cover始终得不到它的最佳解。

解： 有奇数个顶点的一根直线就是这类图的例子。如下图所示，设这根线的顶点数为2k+1，那么最佳解是k个不相邻的顶点。但是近似算法Approx-Vertex-Cover每次取两个相邻点，也就是取一系列的边，而且所取的相邻的两条边中间最多可间隔一个点，所以取最少边的做法是，如下图所示，从一头开始，取第2条边。然后，隔一个点取一条边，直到无边可取。这时，如果还剩2个点，则必须再取一条边，否则算法停止。经过简单分析可知，这个最佳解一共取了2k3条边，也就是2×2k3个顶点。因为2×2k3?4k3

1

1

2

3

4

最佳解是C={2,4,6,8}

5

6

7

8

9

1

2

3

4

近似算法Approx-Vertex-Cover最好解是C={2,3,5,6,8,9}

5

6

7

8

9

证明算法Approx-Vertex-Cover选出的边的集合是一个局部最大(maximal)匹配。局部最大是指不能够再加一条边到这个集合中而仍能形成匹配。

证明： 因为算法Approx-Vertex-Cover每选出一条边之后，这条边的两个顶点就从图里删去，后面选出的边不可能与这条边共顶点，所以所有选出的边都是两两不相交的，因此算法Approx-Vertex-Cover选出的边的集合是一个匹配。又因为这个集合中顶点形成一个顶点复盖，因此图里剩下的每条边必定与这个集合中某顶点关联，所以这个匹配不可能再扩大了。

在证明图的顶点复盖问题是NPC问题时，我们把clique问题归约到图的顶点复盖问题，并证明图G(V,E)有一个k-clique当且仅当其补图G有一个(n-k)的顶点复盖，这里n=|V|。因为顶点复盖问题有近似度为2的多项式算法，那么，是否可以利用这个关系，使得clique问题也有近似度为常数的多项式算法呢？

解： 虽然G(V,E)的最大clique对应G的最小顶点复盖，Clique问题不能由此得到近似度为常数的多项式算法。假设我们用顶点复盖的近似算法求图G(V,E)的团如下：

构造G(V,E)的补图G。

用近似度为2的顶点复盖算法求G的顶点复盖C。

由C得到原图的clique=V–C。

假设上面算法产生的顶点复盖C有|C|=k个顶点，而最小顶点复盖C*有k*k个顶点，k/k*?2。如果我们用顶点复盖C得到G中一个有(n-k)个顶点的clique，因为最大clique有n-k*个点，那么这个近似解有近似度(n-k*)/(n-k)=1+(k-k*)/(n-k)。这个比例不能保证小于某常数。如果k接近n，而且k约等于2k*，这个比例会趋向无穷大。我们看个例子。如果G是如下图(a)所示的有2m+1个顶点的图。如果我们用近似度为2的算法求顶点复盖，可能取m条垂直边，得到如图(a)所示的2m个点的顶点复盖C。如果用这个C在原图中找一个clique，我们得到只有一个顶点的clique，而G的最小顶点复盖，如图(b)所示，只需m个点，原图G的最大的clique有(m+1)个顶点。上述算法对这个例子得到的近似度是m+1

1

1

2

3

4

5

6

7

8

9

11

12

13

14

近似算法Approx-Vertex-Cover最坏解是C={1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,17,18,19}

15

16

17

18

19

10

1

1

2

3

4

5

6

7

8

9

11

12

13

14

最小复盖是C*={1,3,5,7,9,12,14,16,18}

15

16

17

18

19

10

某教授提出了下面这个求顶点复盖的启发式算法：找到图中一个有最大度数(degree)的顶点，把这个点选入顶点复盖，然后把这个点以及与该点关联的边从图中刪去。然后，不断重复这一过程直到图中不再有边为止。证明这个算法不能保证近似度2。(提示：构造一个二部图使左边的点在算法执行中不被删去，而右边的点逐步被刪去，并使右边的点的个数大于左边点的个数一倍。)

解： 让我们构造一个二部图使左边的点在算法执行中不被删去，而右边的点逐步被刪去，并使右边的点的个数大于左边点的个数一倍。让我们构造一个具体例子加以说明。为简单起见，我们假定，如果两个顶点，分别在左右两边，并有相同的最大度数时，算法取右边的顶点。

如下图(a)所示，先左右各构造6个点和6条不相交的边。对这个图而言，这个启发式算法会选取右边6个点。我们在(a)的基础上，在右边加上3个点得到图(b)，其中每个