算法导论14.2 Exercises 答案

发表于 更新于 分类于 阅读次数： 本文字数： 1.5k 阅读时长 ≈ 1 分钟

14.2-1

假设这六个矩阵分别为$A_1,A_2,\dots,A_6$，那么这$6$个矩阵的最优链乘方式为：

仅需进行$2010$次乘法。

14.2-2

1
2
3
4
5
6
7
8
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\ge 0,P(n)\ge c\cdot 2^n$，那么有

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

因此有$P(n)=\Omega(2^n)$。

14.2-4

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

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

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

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

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$，两者是对等的。因此有

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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)\
&=\dfrac{n^3-n}{3}
\end{aligned}$

14.2-6

考虑使用归纳法证明。

  • 当$n=1$时，不需要括号来对表达式进行括号化，原结论成立。

  • 当$n=2$时，仅需要一对括号才能将表达式$A_1A_2$完全括号化，得到$(A_1A_2)$。

  • 当$n>2$时，假设对于$k=1,2,\dots,n-1$均成立。那么我们可以将元素表达式$A1,A_2,A_3,\dots,A{n-1},An$分成两个不为空的表达式：$A_1A_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$个括号。

因此，原结论成立。