算法导论14.3 Exercises 答案

14.3-1

调用程序RECURSIVE-MATRIX-CHAIN要比直接枚举括号序列优秀。

假设枚举括号序列时也涉及到了第\(k\)个位置的划分，那么相当于将左半部分的所有解和右半部分的所有解一一组合，和最终答案比较。

而调用程序RECURSIVE-MATRIX-CHAIN仅仅将左半部分的最优解和右半部分的最优解进行组合，效率相对有所提升。

14.3-2

MERGE-SORT的递归树如图所示：

graph TD
  A[1:16];B[1:8];C[9:16];D[1:4];E[5:8];F[9:12];G[13:16];H[1:2];
  I[3:4];J[5:6];K[7:8];L[9:10];M[11:12];N[13:14];O[15:16];a[1:1];
  b[2:2];c[3:3];d[4:4];e[5:5];f[6:6];g[7:7];h[8:8];i[9:9];
  j[10:10];k[11:11];l[12:12];m[13:13];n[14:14];o[15:15];p[16:16];A-->B;
  A-->C;B-->D;B-->E;C-->F;C-->G;D-->H;D-->I;E-->J;
  E-->K;F-->L;F-->M;G-->N;G-->O;H-->a;H-->b;I-->c;
  I-->d;J-->e;J-->f;K-->g;K-->h;L-->i;L-->j;M-->k;
  M-->l;N-->m;N-->n;O-->o;O-->p;

归并排序时对于一个区间\([l:r]\)而言，MERGE-SORT递归地使用\([l,(l+r)/2],[(l+r)/2+1]\)这两个区间的子问题结果。但是这两个子问题并不重叠，因此记忆化并不能够有效改进分值算法的效率，如归并排序。

14.3-3

如果是最大化矩阵链乘的开销，这个问题仍然具有最优子结构：对于矩阵\(A_iA_{i+1}A_{i+2}\dots A_j\)的链乘，它的最大开销一定是存在某个\(k\)，来自\(A_iA_{i+1}A_{i+2}\dots A_k\)和\(A_{k+1}A_{k+2}\dots A_j\)的最大开销之和，并且组合起来。

14.3-4

考虑\(n=3\)，并且\(\langle p_0,p_1,p_2,p_3\rangle=\langle5,7,6,3\rangle\)。

按照这个贪心思想，那么实际上这个矩阵的运算顺序是\(((A_1A_2)A_3)\)，总开销为\(5\times 7\times 6+5\times 6\times 3=300\)。因为在求解\(m[1,3]\)时，有\(p_2< p_1\)。

实际上，最优的运算顺序为\((A_1(A_2A_3))\)，总开销为\(7\times 6\times 3+5\times 7\times 3=231\)，比这种贪心策略优秀。

14.3-5

不成立。最优子结构要求我们不关心以前做出的决策。但是以前做出的决策中，可能以前做出的决策是已经出来了\(l_i\)根长度为\(i\)的钢条，如果现在继续以\(i\)作为决策，那么就会违反题目条件。也就是说，前面的决策会影响后面的决策进行。