算法导论34.1 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 3.2k 阅读时长 ≈ 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$。和这个判定问题对应的语言是：

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$。