《算法设计与分析》第07章

【程序7－4】矩阵连乘的备忘录方法 int MatrixChain::LookupChain(int i, int j) { if (m[i][j]>0) return m[i][j]; if(i==j) return 0; int u=LookupChain(i+1,j)+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for (int k=i+1;k<j; k++) { int t=LookupChain(i,k)+LookupChain(k+1,j) +p[i]*p[k+1]*p[j+1]; if (t<u) { u=t; s[i][j]=k; } } m[i][j]=u; return u; }
完全加括号的矩阵连乘积可递归地定义为： 单个矩阵是完全加括号的； 矩阵连乘积A是完全加括号的，则A可表示为两 个完全加括号的矩阵连乘积B和C的乘积并加括号， 即A=(BC)。
例7－4 4 个 矩 阵 连 乘 积 ABCD ， 设 它 们 的 维 数 分 别 为 A:5010，B:1040, C:4030, D:305。
7.2.4 算法正确性
定理7－1 弗洛伊德算法得到的d[i][j]，0i,jn-1是从i到j的 最短路径。
7.3 矩阵连乘
7.3.1 问题描述
给定n个矩阵{A0,A1,…,An－1}， 其中Ai，i=0,…,n1的维数为pipi+1，并且Ai与Ai+1是可乘的。考察这n 个矩阵的连乘积A0A1…An1 ，由于矩阵乘法满足结 合律，所以计算矩阵的连乘可有许多不同的计算次 序。矩阵连乘问题是确定计算矩阵连乘积的计算次 序，使得按照这一次序计算矩阵连乘积，需要的 “数乘”次数最少。
7.2.2 动态规划法求解
最优子结构 设图G=(V,E)是带权有向图，(i,j)是从结点i到结点j 的最短路径长度，k是这条路径上的一个结点 ， (i,k) 和(k,j)分别是从i到k和从k到j的最短路径长 度，则必有(i,j)= (i,k)+(k,j)。因为若不然，则 (i,j)代表的路径就不是最短路径。这表明每对结点 之间的最短路径问题的最优解具有最优子结构特性。
int MatrixChain::LookupChain()
for (int r=2; r<=n;r++) for (int i=0;i<=n-r;i++) { int j=i+r-1; m[i][j]=m[i+1][j]+p[i]*p[i+1]*p[j+1]; s[i][j]=i; for (int k=i+1;k<j;k++) { int t=m[i][k] +m[k+1][j]+p[i]*p[k+1]*p[j+1]; if (t<m[i][j]) { m[i][j]=t;s[i][j]=k; } } } return m[0][n-1];
for (k=0;k<n;k++) for (i=0;i<n;i++) for (j=0;j<n;j++) if (d[i][k]+d[k][j] < d[i][j] ){ d[i][j]=d[i][k]+d[k][j]; path[i][j]=path[k][j]; } }弗洛伊德算法的时间复杂度为O(n3)
【程序7－1】多段图的向前递推算法 template<class T> void Graph<T>::FMultiGraph(int k,int *p) {//采用程序6－8的邻接表存储图G。 float *cost=new float[n]; int q,*d=new int[n]; cost[n-1]=0,d[n-1]=-1;
矩阵连乘A[0:n-1]的最优计算次序的计算量等于 A[0:k]和A[k+1:n-1]两者的最优计算次序的计算量之 和，再加上A[0:k]和A[k+1:n-1]相乘的计算量。如果 两个矩阵子序列的计算次序不是最优的，则原矩阵 的计算次序也不可能是最优的。这就是说，矩阵连 乘问题的最优解具有最优子结构特性。
第7章 动态规划法
7.1 7.2 7.3 7.4 7.5 7.6 7.7
一般方法和基本要素 每对结点间的最短路径 矩阵连乘 最长公共子序列 最优二叉搜索树 0/1背包 流水作业调度
7.1 一般方法和基本要素
动态规划法的实质也是将较大问题分解为较小的 同类子问题，这一点上它与分治法和贪心法类似。 但动态规划法有自己的特点。分治法的子问题相 互独立，相同的子问题被重复计算，动态规划法 解决这种子问题重叠现象。贪心法要求针对问题 设计最优量度标准，但这在很多情况下并不容易。 动态规划法利用最优子结构，自底向上从子问题 的最优解逐步构造出整个问题的最优解，动态规 划则可以处理不具备贪心准则的问题。
重叠子问题：为了计算dk[i][j]时，必须先计算 dk－1[i][j]、dk－1[i][k]和dk－1[i][k]，dk1的元素被多 个dk的元素的计算共享。
7.2.3 弗洛伊德算法
弗洛伊德算法的基本思想是：令k=0,1,,n-1，每 次考察一个结点k。二维数组d用于保存各条最短路 径的长度，其中，d[i][j]存放从结点i到结点j的最短 路径的长度。在算法的第k步上应作出决策：从i到j 的最短路径上是否包含结点k。
7.1.2 基本要素
一个最优化多步决策问题适合用动态规划法求 解有两个要素：最优子结构特性和重叠子问题。
7.1.3 多段图问题
例7－1 多段图G=(V,E)是一个带权有向图，它具有如下特性： 图中的结点被划分成k2个互不相交的子集Vi， 1ik。其中V1和Vk分别只有一个结点，V1包含源点 （source）s，Vk包含汇点（sink）t。对所有边 <u,v>E，多段图要求若uVi，则vVi＋1，1i<k， 每条边的权值为c(u,v)。从s到t的路径长度是这条路 径上边的权值之和，多段图问题（multistage graph problem）是求从s到t的一条长度最短的路径。
}
void MatrixChain::Traceback(int i,int j) { if(i==j) { cout<<'A'<<i;return;} if (i<s[i][j]) cout<<'('; Traceback(i,s[i][j]);if (i&l[j]+1<j)cout<<'('; Traceback(s[i][j]+1,j);if(s[i][j]+1<j) cout<<')'; } void MatrixChain::Traceback() { cout<<'('; Traceback(0,n-1);cout<<')'; cout<<endl; }
最优解的递推关系 先定义一个二维数组m，用来保存矩阵连乘时所需的 最少计算量。
i j 0 m [ i ][ j ] min { m [ i ][ k ] m [ k 1 ][ j ] p p p } i k 1 j 1 i k j i j
7.3.3 矩阵连乘算法
例7－5 6个矩阵连乘积A0A1A2A3A4A5，设它们的维数分别 为A:3035，B:3515 C:155 D:510，E:1020， F:2025。
7.3.4
备忘录方法
矩阵连乘的备忘录方法 备忘录方法为每个已经计算的子问题建立备忘录， 即保存子问题的计算结果以备需要时引用，从而 避免了相同子问题的重复求解。
for (int j=n-2;j>=0;j--){ float min=INFTY; for (ENode<T> *r=a[j];r;r=r->nextArc) { int v=r->adjVex; if (r->w+cost[v]<min) { min=r->w+cost[v];q=v; } } cost[j]=min;d[j]=q; } p[0]=0;p[k-1]=n-1; for(j=1;j<=k-2;j++) p[j]=d[p[j-1]]; delete []cost;delete []d; }
7.1.4 资源分配问题
【例7－2】 将n个资源分配给r个项目，已知如果把j个资源 分 配 给 第 i 个 项 目 ， 可 以 收 益 N(i,j) ， 0jn ， 1ir。求总收益最大的资源分配方案。
7.1.5 关键路径问题
问题描述 关键路径问题是一个带权有向无环图中两 个结点间的最长路径问题。
例7-3是AOE网络的一个例子，它代表一个包 括11项活动和9个事件的工程，其中，源点0表示 整个工程已经开始，汇点8表示整个工程结束。
例：7-3
0
1
2
3
4
5
6
7
8
Earlist(i) 0
6
4
5
7
7
16
15
19
Latest(i) 0
6
6
9
7
11
17
15
19
关键路径为：0,1,4,7,8 长度为：19
7.1.1 一般方法
最优性原理指出，一个最优策略具有这样的性 质，不论过去状态和决策如何，对前面的决策所 形成的状态而言，其余决策必定构成最优策略。 这便是最优决策序列的最优子结构特性。
设计一个动态规划算法，通常可以按以下几个步 骤进行： （1）刻画最优解的结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值； （4）根据计算得到的信息构造一个最优解。 其中，第（1）至（3）步是动态规划算法的基本 步骤。最优解值是最优解的目标函数的值。