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

PAGE32

第14章 NP完全问题

判断以下各命题对与错。

如果P1NP，那么就不存在多项式算法来判断一个图是否可以3着色。

如果P1NP，那么就不存在多项式算法来判断一个图是否含有一个6-clique。

如果P1NP，那么就不存在多项式算法来判断一个图是否有一个6-cover。

如果问题A有多项式算法在?(n3)时间内被判定，而问题B在?(n3)时间内可归约为问题A，那么问题B也就可以在?(n3)时间内被判定，这里的n指的都是问题的输入规模。

如果问题A有算法在?(2n)时间内被判定，而问题B在多项式时间内可归约为问题A，那么问题B也就可以在?(2n)时间内被判定

解：(a)对 (b)错 (c)错 (d)错 (e)错。

假设给你一个“宝盒子”P，它可以在常数时间内正确判定一个有n个正整数的集合S是否可以被平分，但它不能给出实际的平分，它只可以被你的程序调用并输出P(S)=1或P(S)=0。请设计一个以P为子程序的多项式算法为一个可平分的集合S作出实际的平分。

解：算法思路如下：设S={a1,a2,…,an}。如果集合S可被平分为集合A和S-A，那么我们可以用P来检测a2是否可以与a1分在同一个集合。办法是，我们把a1和a2从S中刪去，换之以一个数c，其值为(a1+a2)，即S?S?{c}–{a1,a2}。如果改动后的集合S仍然有P(S)=1，则表明新的集合S可以平分，而新集合可以平分则表明原集合可以平分，并且a1和a2可以分在同一个集合。否则，如果有P(S)=0，则表明a1和a2不可以分在同一个集合，我们则恢复原集合。我们用这个办法把所有可以与a1分在同一个集合的整数都找出来，平分完成。下面伪码精确地表达了这个算法。

Partition(S)

ifP(S)=0 //P作为子程序被调用

thenreturn(Shasnopartition)

endif

A?{a1}

c?a1

S’?S?{c}–{a1} //c=a1，在S中换一个符号而已

fori?2ton

c?c+ai

S’?S’–{ai}

ifP(S’)=1

then A?Aè{ai}

else c?c-ai

S’?S’è{ai}

endif

endfor

returnA,S-A

End

这显然是个多项式算法。

集合复盖(set-cover)问题是这样定义的：假设F={S1，S2，…，Sn}是含n个集合的一个家族(family)，这些集合的并集一共含有m个不同的元素，即?1≤i≤nSi={a1，a2，…，am}。家族中一部分集合的组合C称为一个子家族。如果这m个元素中每个元素都出现在子家族C中的某个集合里，那么C称为是F的一个复盖，因为C复盖了F中所有元素，即?Si∈CSi={a1，a2，…，am}。如果C是F的一个复盖并且所含集合数最少，则称为一个最小复盖。比如，F={S1，S2，S3}，这里S1={a,b},S2={b,c},S3={a,c,d}，S1èS2èS3={a,b,c,d}。因为S1èS3={a,b,c,d}，所以C={S1，S3}就是一个F的集合复盖。因为在这个家族F中没有一个集合能包含全部4个元素，所以子家族C={S1，S

定义集合复盖问题所对应的一个判断型问题。

证明集合复盖问题是NP难问题。

解：(a)对应的一个判断性问题可定义如下：假设F={S1，S2，…，Sn}是含n个集合的一个家族(family)，这些集合的并集一共含有m个不同的元素，即?1≤i≤nSi={a1，a2，…，am}。对一个给定正整数k，判断F中是否有一个k-复盖，即含k

证明集合复盖问题是NP难问题。

我们把顶点复盖问题多项式归约到集合复盖问题。假设一个顶点复盖问题的实例是图G(V,E)和整数k。下面解释如何由这个实例来构造一个集合复盖问题的实例。

假设图G(V,E)有m条边，E={e1，e2，…，em}，那么，对应G中每一条边ei(1?i?m)，我们构造一个元素ai。然后，对应G中每一个顶点v?V，我们构造一个集合Sv，而它所含元素就是与点v关联的边所对应的元素，即Sv={ai|边ei与v关联，1?i?m}。设|V|=n，那么这n个集合一起就组成了一个家族F，F={Sv|v?V}。下面看一个例子。假设顶点复盖问题的图如下。

我们为6个顶点构造6个集合如下：

Sa={a1,a3,a4}，