6
由于不能事先决定最初在何处进行划分，所以分治策略难以 解决这个问题。但这个问题满足最优子结构性质：即，当选 择了进行最外层相乘的位置之后，其左右两边的矩阵相乘序 列都必须是时间代价最小的，可以考虑采用贪心策略。
一种使用贪心策略的解决方法是：每次优先选择其相乘代价 最小的两个矩阵。例如在本实例中，A1•A2•A3•A4有三个可能 的相邻矩阵乘积，其中 A2•A3 的代价 400 为最小。那么首先完 成 A2•A3，在余下的两个可能的相邻矩阵乘积中： 30× 1 × 10 和1×10×25相比较，后者较小。于是得到的解为A1( ( A2 A3 ) A4 )，与穷举法的最优结果一致。不过该贪心策略不能保证得 到最优解。例如反例： 矩阵A、B、C，维数分别为：40×1，1×20，20×50， (A•B)•C 40×1×20+40×20×50=40800 A•(B•C) 1×20×50+40×1×50=3000
7
另外一种采用贪心策略的方法是，对于n个矩阵A1... An的维数 序列 d0...dn，每次从 d1...dn-1 中取最大值 di，首先进行 Ai 与 Ai+1 的乘法使最大的维数仅参加一次乘法运算，这样做有可能有 利于减少矩阵连乘的计算量。使用这一策略，对上面的两个 简单实例进行计算，其结果都是正确的。但是这个贪心算法 仍然不能总是找出最优解。
* * cos t * * * 0 * * * * 1200 0 * * * 1400 * * 400 650 0 10000 last * * 0 * * * * 700
1 * * * * 1 1 2 3 * 1 3 * * 1 * * * 1 1
8
此算法的递归过程中，存在与fibo函数相似的地方，即会有大 量的重复调用，其调用关系如Fig7.2所示，其中n=4。
9
递归函数 MinCost 的调用过程在 n=4 时共 27 次， n=5 时为 81 次， n=6时为249次，当n增大时，计算量急剧增加。如果采用自底 向上的计算方式，函数MinCost(1,n)的计算代价将大大减少。 其计算过程为： MinCost(1,1)=MinCost(2,2)=MinCost(3,3)=MinCost(4,4)=0 MinCost(1,2)=MinCost(1,1)+MinCost(2,2)+d0d1d2=30×1×40 =1200 类似地， Mincost(2,3)=d1d2d3=1×40×10=400； Mincost(3,4)=d2d3d4=40×10×25=10000； 在第二步计算MinCost(1,3)和MinCost(2,4)， 最后计算MinCost(1,4)。 由 此 可 以 看 出 ， n=4 时 函 数 MinCost(1,4) 的 计 算 量 是 4+3+2+1=10次，n=5时为15次，n=6时为21次。

7.2 最优二分搜索树
（Optimal Binary Search Tree）
7.2.1
OBST问题
二分字典树是构造数据存储与检索系统的一种方便形式，例 如一个翻译系统需要一个字典数据库。可以按照单词的字典 顺序构造一个二分搜索树，能获得较高的搜索效率。 假定字典中只包含15个单词： and，cabbage，come，has，king，of，pig，ring，said， talk，the，thing，time，walrus，wing。 按照字典顺序插入显然形成一个退化的二分树即线性链表， 其平均搜索代价是(1+15)/2=8次单词比较。
17
平均搜索代价的差别说明，不同的二分搜索树在一定的查找 概率条件下，性能是不同的。因此，在单词集合及其查找概 率给定的条件下，构造一个平均搜索代价最小的二分搜索树 的意义是很明显的。 在实际问题中，还要考虑不成功的搜索，即查找给定单词集 合之外的单词。这时可以把二分搜索树加以扩充，例如 Fig7.4中的(c)，可以为这棵4个节点的树增加5个外部节点， 形成一棵新树，如Fig7.5所示。
10
4. 矩阵连乘的DP算法 设矩阵个数为n，维数为dim[n+1]（n+1个值），同时用数组 MultiOrder[n]保存程序运行时得到的最优乘法顺序，可得： 算法7.1 最优矩阵连乘算法 MatrixOrder 函数MatrixOrder返回最优连乘次序所需的最小时间代价，同 时将最优次序保存在数组MultiOrder中，从此数组中得到最 优乘法次序的算法为：ExtractOrder 用上述算法计算本节给出的实例，其结果为：
2
7.1 动态规划的基本原理
7.1.1
Fibonacci数的计算
Fibonacci数又称为Fibonacci数列，定义为： F0=0, F1=1, Fn=Fn-1 + Fn-2 (n ≥ 2) 计算Fibonacci数列可由递归函数fibo完成。 递归函数fibo 由此可知，函数fibo的计算量随n的增加而急剧增加，n=6时 需25次调用，n=10时需177次调用，n=15时需1974次调用。 进一步的研究表明，调用次数 An = 2Fn+1 - 1，其中 1 n 。 ( 5 1) 1.618 Fn ( ) ， 2 可以估计， T ( n) An ( 22 / n ) ，其计算量是n的指数函数。
可以从 Fibonacci 数的计算得到启发，采用动态规划的方法设 计算法。最简单的递归算法描述如下：
n1 0 , MinCost [1, n] min { MinCost [1, k ] MinCost [k 1, n] d 0d k d n 1 k n
递归算法MinCost
16
由这四个单词可以组成许多种不同的二分字典树，Fig7.4中给 出了其中的三个。
按照上面给出的计算方法，三棵树（ a,b,c）的平均搜索代价 分别为： (a) 0.08+2×(0.12+0.35)+3×0.45=2.37次比较； (a) 0.35+2×(0.08+0.45)+3×0.12=1.77次比较； (a) 0.35+2×(0.12+0.45)+3×0.08=1.73次比较。
3
从 Fig.7.1 中可以看出，大量的调用过程是重复的，此算法可 以改进。
函数fibo的改进函数fib 这个程序的时间代价为O(n)阶。
4
7.1.2
矩阵连乘的顺序问题
1. 一个实例 四个矩阵A1、A2、A3、A4相乘，设其阶数分别为 A1：30×1，A2：1×40，A3：40×10，A4：10×25。 因为矩阵相乘满足结合律，所以可有下面五种（实际为六种） 不同的运算次序，而且不同的运算次序所需的元素间乘法的 次数不同，如下面所列： ( ( A1 A2 ) A3 ) A4 ( A1 A2 )( A3 A4 ) ( A1( A2 A3 ) ) A4 A1( ( A2 A3 ) A4 ) A1( A2( A3 A4 ) ) 30×1×40+30×40×10+30×10×25=20700 30×1×40+40×10×25+30×40×25=41200 1×40×10+30×1×10+30×10×25=8200 1×40×10+1×10×25+30×1×25=1400 40×10×25+1×40×25+30×1×25=11750
A(T )
P C
i 1 i
n
i
即，二分搜索树T的平均搜索代价应为从根到各个单词节点在 T中的路长Ci与其查找概率Pi乘积之和。当各个单词的查找概 率不同时，完全二分搜索树就不一定最优了。例如，假定词 典仅由4个单词cat、come、of、the组成，它们的查找概率分 别为： cat:0.12，come:0.08，of:0.35，the:0.45
最小代价为cost[0][n]=1400， 最优乘法次序MultiOrder[1..3]=2,3,1，即A1((A2A3)A4)。
11
7.1.3
动态规划（DP）算法的基本条件
1. 最优子结构性质 最优化原理。其特征是：当要求一个问题的最优解时，构成 整体解的子问题的解也必须是最优的。例如，为了使计算n个 矩阵连乘A1•A2•...•An的代价最小，无论最后一次乘法的位置k 在何处（1≤k<n），其左右两部分A1•...•Ak，Ak+1•...•An的乘积 也必须是代价最小的。这也可用最短路径问题来说明：若 V1V2...Vn是一条从V1到Vn的最短路径，那么这条路径的任何 一段，比如从Vi到Vj（1≤i<j≤n）也必须是一条最短路径。 2. 子结构重迭性质 简单的递归程序解法都是一种自顶向下进行递归分解的过程， 其中包含了大量的重复调用，在这种情况下采用动态规划方 法特别有效。因此，问题中这种子结构重迭性质是采用动态 规划方法的另一个条件。动态规划算法的一个特征是自底向 上，它可以大幅度减少计算代价。
p q
i 1 i i 0
n
n
i
1 。
求：构造一种二分搜索树T，使平均搜索代价A(T)最小。 解这个问题最简单的方法是把由n个单词（节点）组成的所有 二分搜索树的平均搜索代价全算出来，取其最小者。不过，4 个单词的二分搜索树有14种，7个单词的二分搜索树有429种 就可知道，n较大时，这种方法是根本行不通的。
计算机算法
——设计与分析导论
南开大学 计算机科学与技术系 刘璟
1
Chapter 7. 动态规划
（Dynamic Programming）
7.1 动态规划的基本原理
7.2 最优二分搜索树(Optimal Binary Search Tree)
7.3 近似串匹配(Approximate String Matching)问题