算法导论34.1 Exercises 答案

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

34.1-1

充分性：显而易见，只需要运行一次LONGEST-PATH-LENGTH算法就可以得到最长路径的值\(l\)，判定性问题LONGEST-PATH只需要以LONGEST-PATH-LENGTH作为子程序，计算出\(l\)的值，再比较\(l\)和\(k\)的大小即可。如果LONGEST-PATH-LENGTH的时间复杂度为\(O(n^a)\)，其中\(a\)是一个正常数，那么LONGEST-PATH的时间复杂度同样为\(O(n^{a})\)，由此充分性成立。

必要性：对于图\(G=(V,E)\)，假设\(n=|V|\)。可见，一条简单路径的长度至多为\(n-1\)。由于判定性问题LONGEST-PATH-LENGTH满足单调性（即\(\langle G,u,v,k\rangle\)所有的路径都包含在\(\langle G,u,v,k-1\rangle\)中），因此可以考虑使用二分法来进行求解，需要进行\(O(\lg n)\)次判定。如果某次LONGEST-PATH给出的结果为\(1\)，那么说明\(k\)还能增大；否则只能减小。因此，如果LONGEST-PATH的时间复杂度为\(O(n^b)\)，那么LONGEST-PATH-LENGTH的时间复杂度为\(O(n^{b}\cdot \lg n)=O(n^{b+\epsilon})\)，其中\(b,\epsilon\)是一个正常数。由此必要性成立。

最终，原结论成立。

34.1-2

LONGEST-SIMPLE-CYCLE的形式化定义是：问题中的一个实例是一个图\(G\)，其解为图中的顶点序列，表示这个环。其判定性问题CYCLE是：给定一个图\(G\)和一个非负整数\(k\)，判断图\(G\)是否存在一个长度至少为\(k\)的环。如果存在，那么输出\(1\)；如果不存在，那么输出\(0\)。和这个判定问题对应的语言是：

\[\begin{aligned} \text{CYCLE}=\{\langle G, k\rangle:&G = (V, E)\text{ is an undirected graph, }\\ &k \ge 0\text{ is an integer, and}\\ &G\text{ contains a cycle at least }k\text{ edges}\} \end{aligned}\]

34.1-3

邻接矩阵的编码方式如下：首先输入一个\(32\)位无符号数表示这个图\(G=(V,E)\)的顶点数\(n=|V|\)，接下来输入\(|V|^2\)个比特，下标从\(0\)到\(|V|^2-1\)表示它们。那么，如果第\(i\)个比特为\(1\)，那么有一条边从\(\lfloor i/n\rfloor\)连向\(i\% n\)，否则没有边从\(\lfloor i/n\rfloor\)连向\(i\% n\)。

邻接表的编码方式如下：首先输入一个\(32\)位无符号整数表示这个图\(G=(V,E)\)的顶点数\(n=|V|\)。令\(m=\lceil (\lg n+1)\rceil\)，接下来循环\(n\)次这个过程，直到停止。在第\(u\)次循环中，首先读入一个\(m\)比特数\(d_u\)，表示和\(u\)相邻的节点数，接下来循环进行\(d_u\)次，每次读入一个\(m\)比特数\(v\)，表示\(u\)指向节点\(v\)，并记录。

以下是两种编码的转换过程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// READ(S, k)表示接下来从S中读入k比特，并解析为一个数。BIN(n, k)表示将非负整数n编码成一个k比特数。
ADJACENCY-MATRIX-TO-LIST(S)
  T = ""
  n = READ(S, 32)
  T = T + BIN(n, 32)
  m = ⌈lg(n + 1)⌉
  for u = 0 to n - 1
    E = READ(S, n)
    cnt = 0
    for v = 0 to n - 1
      if E[v] == '1'
        cnt = cnt + 1
    T = T + BIN(cnt, m)
    for i = 0 to n - 1
      if E[v] == '1'
        T = T + BIN(v, m)
  return T

ADJACENCY-LIST-TO-MATRIX(S)
  T = ""
  n = READ(S, 32)
  T = T + BIN(n, 32)
  m = ⌈lg(n + 1)⌉
  for u = 0 to n - 1
    let P be a n-length bit string with '0'
    d = READ(S, m)
    for i = 0 to d - 1
      v = READ(S, m)
      P[v] = '1'
    T = T + P
  return T

可见，无论图的稀疏程度如何，邻接矩阵所需要的比特数都是一样的，为\(O(n^2)\)。不过，当图\(G\)是完全图时，邻接表需要花费\(O(n^2\lg n)=O(n^{2+\epsilon})\)的比特来存储这些比特，其中\(\epsilon\)是一个正常数。此外这两个转换算法仅仅是两层嵌套循环，而没有进行其它操作（如递归）。这两个算法是以\(O(n^{2+\epsilon})\)的时间复杂度对这两种编码进行转换，因此它们是多项式相关的。

34.1-4

0-1背包问题的动态规划算法不是多项式时间的算法。这个问题的时间复杂度为\(O(nW)\)，其中\(W\)是背包的大小。考虑对这个问题进行编码，\(n\)可以编码成一个\(32\)位无符号整数。接下来需要对\(n\)个物品进行编码，无论如何编码，物品所需要的编码数\(b_1\)必定满足\(\Omega(n)\)。接下来对背包重量\(W\)进行编码，用\(b_2=\Theta(\lg W)\)比特即可完成，即有\(W=\Theta(2^{b_2})\)。因此，对于编码长度为\(b_1+b_2\)的问题所需要花费的时间为\(\Omega(b_1 \cdot 2^{b_2})\)。因此，0-1背包问题的动态规划算法不是多项式时间的算法。

34.1-5

假设这个多项式算法为\(A_1\)，其子程序为\(A_2\)。假设\(A_1\)调用了至多\(k\)次算法\(A_2\)，设这\(k\)次调用中，规模最大的一次的大小为\(n\)。那么如果\(A_2\)的运行时间为\(O(n^c)\)，其中\(c\)是一个正常数，那么算法\(A_1\)在这\(k\)次调用中就有着\(k\cdot O(n^c)\)的开销，再加上\(A_1\)本身也有额外的多项式次数的开销\(O(n^d)\)，因此\(A_1\)的运行时间为\(k\cdot O(n^c)+O(n^d)=O(n^{\max(c,d)})\)，因此它在多项式时间内运行。

接下来考虑构造一个算法来说明，对多项式算法进行多项式次调用会导致一个指数时间算法出现。给定正整数\(x\)和\(q\)，我们希望计算\(x^{2^q}\)的值。由于\(x^{2^q}=(x^{2^{q-1}})^2\)，因此我们可以给出一个算法COMPUTE-X-2-Q来计算\(x^{2^{q}}\)：

1
2
3
4
COMPUTE-X-2-Q(x, q)
  for i = 1 to q
    x = x * x
  return x

将COMPUTE-X-2-Q视作算法\(A_1\)，其代码第2行的乘法视作\(A_2\)。那么可以知道，\(A_1\)实际上调用了\(q\)次\(A_2\)，并且对两个数进行乘法计算是一个多项式算法（使用第30章的FFT，可以以\(O(n\lg n)\)的时间完成计算，其中\(n\)是数\(x\)的长度）。因此COMPUTE-X-2-Q是一个满足题目条件的算法，但是计算结果\(x^{2^q}\)经过编码后，需要\(O(\lg(x^{2^q}))=O(2^q\cdot \lg x)\)的比特才能完成编码，这说明COMPUTE-X-2-Q本身需要指数时间完成计算。因此原结论成立，COMPUTE-X-2-Q算法为所求。

34.1-6

假设现在存在两个程序\(A_1,A_2\)可以分别在多项式时间\(O(n^{k_1}),O(n^{k_2})\)内分别能够判定是否接受语言\(L_1,L_2\)。那么可以构造出如下程序用于判定语言\(L_1\cup L_2,L_1\cap L_2,L_1L_2,\overline{L_1},L_1^{\ast}\)是否属于\(P\)：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
// 假设字符串的下标从1开始。
A-UNION(A1, A2, x)
  if A1(x) == 1 or A2(x) == 1
    return 1
  else
    return 0
  
A-INTERSECTION(A1, A2, x)
  if A1(x) == 1 and A2(x) == 1
    return 1
  else
    return 0

A-CONCATENATION(A1, A2, x)
  // 考虑其中有一个为ε空字符串的情况。
  if (A1(x) == 1 and A2(ε) == 1) or (A1(ε) == 1 and A2(x) == 1)
    return 1
  n = x.size()
  for i = 1 to n - 1
    if A1(x[1 : i]) == 1 and A2(x[i + 1 : n]) == 1
      return 1
  return 0

A-COMPLEMENT(A1, x)
  if A1(x) == 0
    return 1
  else
    return 0

A-KLEENE-STAR(A1, x)
  n = x.size()
  let f[0 : n] be a new array by 0
  f[0] = 1
  for i = 1 to n
    for j = 1 to i
      if f[j - 1] == 1 and A1(x[j : i]) == 1
        f[i] = 1
        break
  return f[n]

算法A-UNION和A-INTERSECTION分别调用了\(1\)次\(A_1\)和\(A_2\)，因此其时间复杂度均为\(O(n^{\max(k_1,k_2)})\)。算法A-CONCATENATION对\(A_1,A_2\)分别至多调用了\((n+1)\)次，并且最大的规模为\(n\)，因此其时间复杂度为\((n+1)\cdot(O(n^{k_1})+O(n^{k_2}))=O(n^{\max(k_1,k_2)+1})\)。算法A-COMPLEMENT仅对\(A_1\)进行了\(1\)次调用，其时间复杂度为\(n^{k_1}\)。A-KLEENE-STAR算法对\(A_1\)进行了\(\dfrac{n(n+1)}{2}\)次调用，最大的一次规模为\(n\)，因此其时间复杂度为\(\dfrac{n(n+1)}{2}\cdot O(n^{k_1})=O(n^{k_1+2})\)。综上所述，A-UNION, A-INTERSECTION, A-CONCATENATION, A-COMPLEMENT, A-KLEENE-STAR可以在多项式时间内对各自的语言完成判定，因此语言\(L_1\cup L_2,L_1\cap L_2,L_1L_2,\overline{L_1},L_1^{\ast}\in P\)。