算法导论 14.2 Exercises 答案

发表于 2022-12-16 更新于 2023-07-24 分类于算法导论阅读次数： 130 本文字数： 1.7k 阅读时长 ≈ 2 分钟

14.2-1

假设这六个矩阵分别为 $A_{1}, A_{2}, \dots, A_{6}$ ，那么这 $6$ 个矩阵的最优链乘方式为：

$(A_{1} A_{2}) ((A_{3} A_{4}) (A_{5} A_{6}))$

仅需进行 $2010$ 次乘法。

14.2-2

MATRIX-CHAIN-MULTIPLY(A, s, i, j)
  if i == j
    return A[i]
  if i + 1 == j
    return RECTANGULAR-MATRIX-MULTIPLY(A[i], A[j])
  a = MATRIX-CHAIN-MULTIPLY(A, s, i, s[i, j])
  b = MATRIX-CHAIN-MULTIPLY(A, s, s[i, j] + 1, j)
  return RECTANGULAR-MATRIX-MULTIPLY(a, b)

14.2-3

假设 $\exists c \geq 0, P (n) \geq c \cdot 2^{n}$ ，那么有

$\begin{aligned} P (n) & = \sum_{k = 1}^{n - 1} P (k) \cdot P (n - k) \\ \geq \sum_{k = 1}^{n - 1} c 2^{k} \cdot c 2^{n - k} \\ = \sum_{k = 1}^{n - 1} c^{2} 2^{n} \\ = (n - 1) c^{2} 2^{n} \\ \geq c \cdot 2^{n} \end{aligned}$

因此有 $P (n) = Ω (2^{n})$ 。

14.2-4

将每个子问题视为图上的顶点： $\forall 1 \leq i \leq j \leq n, v_{i, j}$ 。那么这些顶点个数一共有 $\frac{n (n + 1)}{2}$ 个。

考虑所有节点 $v_{i, j}$ ，那么有

如果 $i = j$ ，那么这时 $v_{i, j}$ 没有出边，因为没有子问题。
如果 $i < j$ ，那么这时 $\forall k, i \leq k < j$ ，我们都需要解决子问题 $(i, k), (k + 1, j)$ 时的情况，因此各有两条有向边： $(v_{i, j}, v_{i, k}), (v_{i, j}, v_{k + 1, j})$ 。

最终，这个子问题图的边数为：

$\sum_{i = 1}^{n} \sum_{j = i}^{n} 2 (j - i) = \frac{n^{3} - n}{3}$

14.2-5

由于这里是计算 $R (i, j)$ 的总和次数，那么我们可以换另外一种角度思考：计算 $m [i^{'}, j^{'}]$ 时，有多少个其它表项被访问过，可以设其为 $S (i^{'}, j^{'})$ ？

如果计算 $m [a, b]$ 时访问了表项 $m [c, d]$ ，那么这次访问为 $R (c, d)$ 贡献了 $1$ ，为 $S (a, b)$ 也贡献了 $1$ ，两者是对等的。因此有

$\sum_{i = 1}^{n} \sum_{j = i}^{n} R (i, j) = \sum_{i^{'} = 1}^{n} \sum_{j^{'} = i^{'}}^{n} S (i^{'}, j^{'})$

简化了问题后，摘录 MATRIX-CHAIN-ORDER 的代码，可以看到只有在第 $9$ 行访问了两次非 m[i, j] 的元素：m[i, k], m[k + 1,]。

MATRIX-CHAIN-ORDER(p, n)
  let m[1 : n, 1 : n] and s[1 : n − 1, 2 : n] be new tables
  for i = 1 to n // chain length 1
    m[i, i] = 0
  for l = 2 to n // l is the chain length
    for i = 1 to n − l + 1 // chain begins at Ai
      j = i + l − 1 // chain ends at Aj
      m[i, j] = ∞
      for k = i to j − 1 // try Ai:kAk+1:j
        q = m[i, k] + m[k + 1, j] + pi−1pk pj
        if q < m[i, j]
        m[i, j] = q // remember this cost
        s[i, j] = k // remember this index
  return m and s

因此，有

$\begin{aligned} \sum_{i = 1}^{n} \sum_{j = i}^{n} R (i, j) & = \sum_{i^{'} = 1}^{n} \sum_{j^{'} = i^{'}}^{n} S (i^{'}, j^{'}) \\ = \sum_{l = 2}^{n} \sum_{i = 1}^{n - l + 1} 2 \cdot ((i + l - 1) - 1 - i + 1) \\ = \sum_{l = 2}^{n} \sum_{i = 1}^{n - l + 1} 2 (l - 1) \\ = \sum_{l = 2}^{n} (n - l + 1) \cdot 2 (l - 1) \\ = \frac{n^{3} - n}{3} \end{aligned}$

14.2-6

考虑使用归纳法证明。

当 $n = 1$ 时，不需要括号来对表达式进行括号化，原结论成立。
当 $n = 2$ 时，仅需要一对括号才能将表达式 $A_{1} A_{2}$ 完全括号化，得到 $(A_{1} A_{2})$ 。
当 $n > 2$ 时，假设对于 $k = 1, 2, \dots, n - 1$ 均成立。那么我们可以将元素表达式 $A_{1}, A_{2}, A_{3}, \dots, A_{n - 1}, A_{n}$ 分成两个不为空的表达式： $A_{1} A_{2}, \dots, A_{k}$ 和 $A_{k + 1}, A_{k + 2}, \dots, A_{n}$ 。那么按照假设，前一部分需要 $k - 1$ 个括号，后一部分需要 $n - k - 1$ 个括号。那么接下来再将这两部分元素进行括号化，仍然需要一个括号。因此最终需要 $(k - 1) + (n - k - 1) + 1 = n - 1$ 个括号。

因此，原结论成立。