算法导论35.3 Exercises 答案

发表于 分类于 阅读次数： 本文字数： 5k 阅读时长 ≈ 5 分钟

35.3-1

下表将给出对单词列表{arid, dash, drain, heard, lost, nose, shun, slate, snare, thread}的模拟过程：

\(\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}\hline i&U_i&\mathscr{C}&\mathtt{arid}&\mathtt{dash}&\mathtt{drain}&\mathtt{heard}&\mathtt{lost}&\mathtt{nose}&\mathtt{shun}&\mathtt{slate}&\mathtt{snare}&\mathtt{thread}\\\hline 0&\mathtt{adehilnorstu}&\{\}&\mathtt{\underline{arid}}&\mathtt{\underline{\mathtt{dash}}}&\mathtt{\underline{drain}}&\mathtt{\underline{heard}}&\mathtt{\underline{lost}}&\mathtt{\underline{nose}}&\mathtt{\underline{shun}}&\mathtt{\underline{slate}}&\mathtt{\underline{snare}}&\mathtt{\underline{thread}}\\\hline 1&\mathtt{ilnosu}&\{\mathtt{thread}\}&\mathtt{ar\underline{i}d}&\mathtt{da\underline{\mathtt{s}}h}&\mathtt{dra\underline{in}}&\mathtt{heard}&\mathtt{\underline{los}t}&\mathtt{\underline{nos}e}&\mathtt{\underline{s}h\underline{un}}&\mathtt{\underline{sl}ate}&\mathtt{\underline{sn}are}&\mathtt{thread}\\\hline 2&\mathtt{inu}&\{\mathtt{thread,lost}\}&\mathtt{ar\underline{i}d}&\mathtt{dash}&\mathtt{dra\underline{in}}&\mathtt{heard}&\mathtt{lost}&\mathtt{\underline{n}ose}&\mathtt{sh\underline{un}}&\mathtt{slate}&\mathtt{s\underline{n}are}&\mathtt{thread}\\\hline 3&\mathtt{u}&\{\mathtt{thread,lost,drain}\}&\mathtt{arod}&\mathtt{dash}&\mathtt{drain}&\mathtt{heard}&\mathtt{lost}&\mathtt{nose}&\mathtt{sh\underline{u}n}&\mathtt{slate}&\mathtt{snare}&\mathtt{thread}\\\hline 4&&\{\mathtt{thread,lost,drain,shun}\}&\mathtt{arod}&\mathtt{dash}&\mathtt{drain}&\mathtt{heard}&\mathtt{lost}&\mathtt{nose}&\mathtt{shun}&\mathtt{slate}&\mathtt{snare}&\mathtt{thread}\\\hline \end{array}\)

因此，选择出来的集合\(\mathscr{C}=\{\mathtt{thread,lost,drain,shun}\}\)。

35.3-2

先将判定性集合覆盖问题定义成一种语言SET-COVER：

\[\text{SET-COVER} = \left\{\langle X, \mathcal{F},k\rangle : \text{there exists a set }\mathscr{C}\subseteq \mathcal{F}\text{ such that }|\mathscr{C}|\le k\text{ and }X=\bigcup_{S\in \mathscr{C}} S\right\}\]

首先证明SET-COVER属于\(\text{NP}\)。问题实例\(\langle X, \mathcal{F},k\rangle\)的一个证据是一个集合\(\mathscr{C}\)，检验程序只需要判断是否满足\(\mathscr{C}\subseteq \mathcal{F},|\mathscr{C}|\le k\)以及\(\displaystyle{X=\bigcup_{S\in \mathscr{C}} S}\)。可见，这个验证程序可以在多项式时间内完成，因此SET-COVER属于\(\text{NP}\)。

接下来证明SET-COVER是NP困难的，考虑使用顶点覆盖问题进行规约，即证明\(\text{VERTEX-COVER}\le_P\text{SET-COVER}\)。对于VERTEX-COVER问题中的任意一个实例\(\langle G,k\rangle\)，规约算法\(F\)构造出如下一个SET-COVER问题的实例\(\langle X, \mathcal{F},k\rangle\)，使得\(G\)包含一个大小为\(k\)的点覆盖，当且仅当\(X\)关于集合族\(\mathcal{F}\)包含一个大小为\(k\)的集合覆盖。

规约过程是：令\(X=E\)。对于每个节点\(v\in V\)，构造集合\(S_v=\{(w,v):w\in V,(w,v)\in E\}\)，并将集合\(S_v\)添加到\(\mathcal{F}\)中。并且两个问题实例的\(k\)值相同。可见\(\langle X, \mathcal{F},k\rangle\)三个参数都能够在多项式时间内构造出来，因此规约算法是多项式时间的。

现在证明\(G\)包含一个大小为\(k\)的点覆盖，当且仅当\(X\)关于集合族\(\mathcal{F}\)包含一个大小为\(k\)的集合覆盖。

充分性：如果\(G\)包含一个大小为\(k\)的点覆盖\(V'\)，也就是说，\(\forall (u,v)\in E\)，都有\((u,v)\)被某个点覆盖，不失一般性，假设这个点是\(u\)。那么\(\mathscr{C}\)中就有一个集合\(S_u\)，它包含了边\((u,v)\)。由于\(X=E\)，因此\(\mathscr{C}\)也是一个大小为\(k\)的集合覆盖。

必要性：如果集合\(X\)包含一个大小为\(k\)的集合覆盖\(\mathscr{C}\)，那么意味着\(\forall(u,v)\in X\)，必定存在一个集合\(S_u\)或者是\(S_v\)，其中一个在\(\mathscr{C}\)中。不失一般性，假设\(S_u\)在\(\mathscr{C}\)中，那么在图\(G\)中，边\((u,v)\)被点\(u\)覆盖。因此令\(V'=\{v:S_v\in\mathscr{C}\}\)，那么\(V'\)就是\(G\)的一个大小为\(k\)的点覆盖。

因此\(\text{VERTEX-COVER}\le_P\text{SET-COVER}\)。由于VERTEX-COVER是NP完全的，那么SET-COVER是NP困难的，也是NP完全的，原结论成立。

35.3-3

考虑对\(X\)中的每个元素和\(\mathcal{F}\)中的所有集合\(S\)建立对应关系，并且将集合\(S\)放进第\(|S|\)个桶中。每次取出元素最多的集合\(S'\)时，需要对于所有\(x\in S\)，其它包含\(x\)的集合\(T\)都需要删去\(x\)，并且将它们放进前一个桶\(|T|-1\)中。更具体的过程由GREEDY-SET-COVER'给出。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
// INSERT-SET和DELETE-SET都是对哈希表进行增加和删除关键字操作。
GREEDY-SET-COVER'(X, F)
  M = max{|S| : S ∈ F}
  let B[0 : M] be a new array by empty set
  let D be a hash-table
  for each S in F
    INSERT-SET(B[|S|], S)
    for each x in S
      INSERT(D[x], S)
  C = Ø
  for i = M downto 1
    while B[i] != Ø
      select a set S from B[i] randomly and remove it
      C = C ⋃ {S}
      for each x in S
        for each T in D[x]
          if T != S
            DELETE-SET(B[|T|], T)
            T = T - {x}
            INSERT-SET(B[|T|], T)
  recover each set S in C
  return C

考虑GREEDY-SET-COVER'的运行时间，前7行都是为每个集合\(S\in \mathcal{F}\)和它们的所有元素都建立二元关系\(x\)，因此这一部分的运行时间为\(\displaystyle{O\left(\sum_{S\in \mathcal{F}} |S|\right)}\)。对于第9行的for循环，它只是从后往前遍历每个桶。第10行的while循环则是取出一个候选集合\(S\)并添加到\(\mathscr{C}\)中。接下来枚举\(S\)中剩余的元素\(x\)，并在\(\mathcal{F}\)中剩下的集合删去它们。可见，每个集合\(S\)只会被第11行代码最多选择一次，并且删去了其它集合中关于这个集合中的所有元素。因此每个元素\(x\)只会被第13行的for循环遍历一次。计算出集合\(\mathscr{C}\)后，需要对它进行恢复。因此第8-20行代码的运行时间为\(\displaystyle{O\left(\sum_{S\in \mathcal{F}} |S|\right)}\)。

因此，GREEDY-SET-COVER'的运行时间为\(\displaystyle{O\left(\sum_{S\in \mathcal{F}} |S|\right)}\)。

35.3-4

考虑GREEDY-SET-COVER的第5行代码，只要\(U_i\neq \varnothing\)，那么必定需要选出一个集合\(S\)，使得\(U_i\)中的元素减少（否则算法直接结束）。因此，对于从GREEDY-SET-COVER产生的覆盖\(\mathscr{C}\)，有\(|\mathscr{C}|\le |X|\)。

由于最优覆盖\(|\mathscr{C}^{\ast}|\)是\(X\)的最优覆盖，因此\(X\)中所有元素都出现在\(\mathscr{C^{\ast}}\)中的某些集合中，也就是\(\displaystyle{|X|\le \sum_{S\in \mathscr{C}^{\ast}}|S|}\)。那么有：

\(\begin{aligned} |\mathscr{C}|&\le |X|\\ &\le \sum_{S\in \mathscr{C}^{\ast}}|S|\\ &\le \sum_{S\in \mathscr{C}^{\ast}}\max\{|S|:S\in\mathcal{F}\}\\ &=|\mathscr{C}^{\ast}|\max\{|S|:S\in\mathcal{F}\} \end{aligned}\)

因此原结论成立。

35.3-5

给出的算法BAD-SET-COVER-INSTANCE如下描述：

1
2
3
4
5
6
7
8
9
10
11
BAD-SET-COVER-INSTANCE(n)
  X = {0, 1, 2, ..., n - 1}
  F = Ø
  m = ⌊n / 3⌋
  for i = 0 to m - 1
    F = F ⋃ {{3 * i, 3 * i + 1}, {3 * i, 3 * i + 2}, {3 * i + 1, 3 * i + 2}}
  if n % 3 == 1
    F = F ⋃ {{n - 1}}
  else if n % 3 == 2
    F = F ⋃ {{n - 1, n - 2}}
  return X, F

对于任意形如\(3i,3i+1,3i+2\)的这\(3\)个元素，有且仅有\(2\)个集合覆盖这\(3\)个元素之一。对于这\(3\)个元素，有\(3\)种不同的选择集合方法能够覆盖到这\(3\)个元素。

因此，构造出的这个问题实例一共有\(3^{\lfloor n/3\rfloor}=O(3^{n/3})\)种不同数量的最优解，它是\(n\)的指数。