《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——矩阵连乘问题
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——矩阵连乘问题，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2902字，纯文字阅读大概需要5分钟。
内容图文
2014.07.07 15:47
简介：
给定N个矩阵，A1、A2、...、An，如果相邻矩阵的维度都满足相乘条件，如何组织这n-1次乘法的顺序，使得总共的乘法次数最少？
描述：
根据矩阵乘法的定义，如果矩阵X的维度是aXb，矩阵Y的维度是bXc。那么XY相乘需要的乘法次数是aXbXc。
这道题目是典型的动态规划问题。从使用者的角度来看，动态规划问题通常的应用情景主要有两个特点：
1. 暴力搜索能够得出答案，但速度实在太慢。如果用空间换时间，记录一些中间状态的话，可以极大程度地降低复杂度，减少重复计算。
2. 贪婪思路无法得出正确答案，所以尽管贪婪思路的代码通常很简洁，思路清晰，但既然不能解决问题，也就不能用了。
最常见的动态规划问题的描述一般都像这样：“用X维数组dp表示能得到的最优XXX，dp[i][j][k]...表示第i步时第j段时...的最优解。”
这样描述的特点，就是不论描述起来有多么冗长和复杂，基本思路都是把一整个问题分解为若干维度，每个维度分解为多步。每一次推导，只是走有限步。如果每次走s步，那么就会保证有s个初始状态，这样能够保证每一个状态的解都能被计算出。这个解一定是最优解。而同样的问题使用贪婪策略通常只能得到接近最优解的次优解。
分治法用递归的方法分解子问题，然后通过合并子问题来解决整体问题。动态规划则使用递推公式从当前状态推导下一状态。
比如下面这个式子：dp[i][j]=min(dp[i][j-1], dp[i-1][j])+1。我只是随手写了这个式子，而动态规划的递推公式通常都是dp[i]与dp[i-1]之间的关系式，或者有更多维度。而我们所期待的最终答案很可能就是dp[n][m]或者dp[n][n]。而dp[0][0]则是我们推导的起点，通常是已知的（有时你必须动动脑子才能想清楚这个已知值到底是几）。
于是，动态规划的起点、终点、中间状态、递推公式、维度等等概念大概是这么回事：
1. 维度：你要用一个几维数组来表示你的最优解呢？例如求出一个字符串中回文字串的个数，你可以用dp[i][j]表示字符串s[i,j]中所有回文子串的个数。这就是二维动态规划。
2. 起点：你开始递推之前，必须得知道dp[0]、dp[0][0]之类的等于几。这个过程有时会花很久，有时则是一念之间的事。
3. 中间状态：dp[i][j]代表什么？问题不同意义自然不同。总之它是一个中间状态，你必须很清楚它的意义。
4. 递推公式：从dp[i-1][j]、dp[i-1][j-1]、dp[i][j-1]如何推导出dp[i][j]呢？用递推公式。递推公式怎么得出的？用你的草稿纸和笔，这就是脑细胞的用武之地了。
5. 终点：dp[n]、dp[n][m]、dp[n][m][p]等等。不论n、m、p等等字母代表什么，终点在哪儿肯定是一开始就确定的。这个不成问题。
最后，用三句话解决矩阵连乘问题：
1. 用dp[i][j]表示i号矩阵连乘到j号矩阵为止需要的最少乘法次数。
2. dp[0][n-1]是我们需要的最终结果。
3. 递推公式请直接看代码。
实现：
1
//
Ordering matrix multiplication, a typical dynamic programming problem.
2
//
Description:
3
//
You have a list of matrices M1, M2, ..., Mn to multiply.
4
//
Each with dimension (X1, Y1), (X2, Y2), ..., (Xn, Yn)
5
//
Of course, Yi == X(i + 1)
6
//
You can arrange the order of matrix multiplications,
7
//
to achieve minimal number of multiplications.
8
//
For example: A * B * C can be A * (B * C) or (A * B) * C,
9
//
they might require different number of multiplications.
10 #include <iostream>
11 #include <vector>
12usingnamespace std;
1314constint INF = 1000000000;
1516int orderingMatrixMultiplication(const vector<int> &dimension)
17{
18int n = (int)dimension.size() - 1;
19 vector<vector<int> > dp;
2021 dp.resize(n, vector<int>(n, INF));
2223int i, j, k;
2425for (i = 0; i < n; ++i) {
26 dp[i][i] = 0;
27 }
2829for (i = 1; i < n; ++i) {
30for (j = 0; j + i < n; ++j) {
31for (k = j; k < j + i; ++k) {
32 dp[j][j + i] = min(dp[j][j + i], dp[j][k] + dp[k + 1][j + i]
33 + dimension[j] * dimension[k + 1] * dimension[j + i + 1]);
34 }
35 }
36 }
3738int result = dp[0][n - 1];
39 dp.clear();
4041return result;
42}
4344int main()
45{
46int i;
47int n;
48 vector<int> v;
4950while (cin >> n && n > 0) {
51 v.resize(n + 1);
52for (i = 0; i < n + 1; ++i) {
53 cin >> v[i];
54 }
55 cout << orderingMatrixMultiplication(v) << endl;
56 }
5758return0;
59 }
原文：http://www.cnblogs.com/zhuli19901106/p/3829955.html
内容总结
以上是互联网集市为您收集整理的《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——矩阵连乘问题全部内容，希望文章能够帮你解决《数据结构与算法分析：C语言描述》复习——第十章“算法设计技巧”——矩阵连乘问题所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。