问答题
[说明]
某工程计算中要完成多个矩阵相乘(链乘)的计算任务。
两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算A m×n ×B n×p ，需要m×n×p次乘法运算。
矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵A1 10×100 ，A2 100×5 ，A3 5×50 三个矩阵相乘为例，若按(A1×A2)×A3计算，则需要进行10×100×5+10×5×50=7500次乘法运算；若按A1×(A2×A3)计算，则需要进行100×5×50+10×100×50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。
矩阵链乘问题可描述为：给定n个矩阵＜A1，A2，…，A n ＞，矩阵A：的维数为p i-l ×p i ，其中i=1，2，…，n。确定一种乘法顺序，使得这n个矩阵相乘时进行乘法的运算次数最少。
由于可能的计算顺序数量非常庞大，对较大的n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若A1×A2×…×An的一个最优计算顺序从第k个矩阵处断开，即分为A1×A2×…×Ak和Ak+1×Ak+2×…×An两个子问题，则该最优解应该包含A1×A2×…×Ak的一个最优计算顺序和Ak+1×Ak+2×…×An，的一个最优计算顺序。据此构造递归式，
某工程计算中要完成多个矩阵相乘(链乘)的计算任务。
两个矩阵相乘要求第一个矩阵的列数等于第二个矩阵的行数，计算量主要由进行乘法运算的次数决定。采用标准的矩阵相乘算法，计算A m×n ×B n×p ，需要m×n×p次乘法运算。
矩阵相乘满足结合律，多个矩阵相乘，不同的计算顺序会产生不同的计算量。以矩阵A1 10×100 ，A2 100×5 ，A3 5×50 三个矩阵相乘为例，若按(A1×A2)×A3计算，则需要进行10×100×5+10×5×50=7500次乘法运算；若按A1×(A2×A3)计算，则需要进行100×5×50+10×100×50=75000次乘法运算。可见不同的计算顺序对计算量有很大的影响。
矩阵链乘问题可描述为：给定n个矩阵＜A1，A2，…，A n ＞，矩阵A：的维数为p i-l ×p i ，其中i=1，2，…，n。确定一种乘法顺序，使得这n个矩阵相乘时进行乘法的运算次数最少。
由于可能的计算顺序数量非常庞大，对较大的n，用蛮力法确定计算顺序是不实际的。经过对问题进行分析，发现矩阵链乘问题具有最优子结构，即若A1×A2×…×An的一个最优计算顺序从第k个矩阵处断开，即分为A1×A2×…×Ak和Ak+1×Ak+2×…×An两个子问题，则该最优解应该包含A1×A2×…×Ak的一个最优计算顺序和Ak+1×Ak+2×…×An，的一个最优计算顺序。据此构造递归式，
问答题
根据以上说明和C代码，填充C代码中的空(1)～(4)。
【正确答案】
【答案解析】i＜n-P(2)j=i+P(3)const[i][k]+const[k+1][j]+seq[i]*seq[k+1]*seq[j+1](4)tempTraee=k；
[解析] 本题考查矩阵连乘最优调度问题，是一种动态规划算法。
上述算法中，第一个循环是给n个cost[i][i]附赋初值0；第二个循环是个外循环，其循环变量P是矩阵连乘的规模，(p=1时)先计算出所有规模为2的cost[i，i+1]，(p=2)再计算出所有规模为3的cost[i，i+2]，……，最后计算出来的即为我们所求的cost[1，n-1]，所以(1)填i＜n-p；第三个循环是内循环，其循环变量i表示矩阵连乘的起始位置，即从1，1+1，…，i，1+i，…，一直算到n-1，n，所以(2)填j=i+P；第四个循环用于计算min{cost[i，j](i≤k＜j)}；所以(3)填cost[i][k]+cost[k+1][j]+seq[i]*seq[k+1]*seq[j+1]；而(4)用于追踪取得最小花费代价的k值，即tempTrace=k；而每一项的计算可在O(1)时间里完成。
上述算法中，第一个循环是给n个cost[i][i]附赋初值0；第二个循环是个外循环，其循环变量P是矩阵连乘的规模，(p=1时)先计算出所有规模为2的cost[i，i+1]，(p=2)再计算出所有规模为3的cost[i，i+2]，……，最后计算出来的即为我们所求的cost[1，n-1]，所以(1)填i＜n-p；第三个循环是内循环，其循环变量i表示矩阵连乘的起始位置，即从1，1+1，…，i，1+i，…，一直算到n-1，n，所以(2)填j=i+P；第四个循环用于计算min{cost[i，j](i≤k＜j)}；所以(3)填cost[i][k]+cost[k+1][j]+seq[i]*seq[k+1]*seq[j+1]；而(4)用于追踪取得最小花费代价的k值，即tempTrace=k；而每一项的计算可在O(1)时间里完成。
问答题
根据以上说明和C代码，该问题采用了______算法设计策略，时间复杂度为______(用O符号表示)。
【正确答案】
【答案解析】动态规划 O(n
3
)
[解析] 求min(i≤K＜j)要做1次比较；(k=i，i+1，…，i+1-1而j=i+l)，而第3行的循环要做n-1次，故该循环执行完毕要做l(n-1)次比较。第2的循环1从1做到n-1，故该外循环执行完毕要做O(n
3
)比较。此即该算法的时间复杂度。
问答题
考虑实例n=6，各个矩阵的维数：A1为5×10，A2为10×3，A3为3×12，A4为12×5，A5为5×50，A6为50×6，即维数序列为5，10，3，12，5，50，6。则根据上述C代码得到的一个最优计算顺序为______(用加括号方式表示计算顺序)，所需要的乘法运算次数为______。
【正确答案】
【答案解析】(A1×A2)×((A3×A4)×(A5×A6)) 2010[解析] 启发式的思路是先把维度最大的消掉，如A5×A6相乘之后，维度50就没有了，所以考虑这两个矩阵先相乘；然后是A3×A4相乘之后，维度12就没有了，所以考虑这两个矩阵相乘；接着，A1×A2相乘之后，维度10就没有了，所以考虑这两个矩阵相乘……这样可以确定相乘的顺序(A1×A2)×((A3×A4)×(A5×A6))，需要的计算开销分别是5×50×6=1500，3×12×5=180.5×10×3=150.3×5×6=90,5×3×6=90，把上述值相加，即1500+180+150+90+90=2010。