算法设计与分析动态规划算法_百度文库
第六章动态规划算法
§1.动态规划算法的基本思想
动态规划方法是处理分段过程最优化问题的一类及其有效的方法。在实际生活中，有一类问题的活动过程可以分成若干个阶段，而且在任一阶段后的行为依赖于该阶段的状态，与该阶段之前的过程是如何达到这种状态的方式无关。这类问题的解决是多阶段的决策过程。在50年代，贝尔曼（Richard Bellman）等人提出了解决这类问题的“最优化原则”，从而创建了最优化问题的一种新的算法动态规划算法。
最优化原则指出，多阶段过程的最优决策序列应当具有性质：
无论过程的初始状态和初始决策是什么，其余的决策都必须相对于初始决策所产生的状态构成一个最优决策序列。这要求原问题的最优解包含了其子问题的一个最优解（称为最优子结构性质）。
动态规划算法采用最优原则来建立递归关系式（关于求最优值的），在求解问题时有必要验证该递归关系式是否保持最优原则。若不保持，则不可用动态规划算法。在得到最优值的递归式之后，需要执行回溯以构造最优解。在使用动态规划算法自顶向下（Top-Down）求解时，每次产生的子问题并不总是新问题，有些子问题反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个问题只计算一次，而后将其解保存在一个表格中，当再次要解此子问题时，只是简单地调用（用常数时间）一下已有的结果。通常，不同的子问题个数随着输入问题的规模呈多项式增长，因此，动态规划算法通常只需要多项式时间，从而获得较高的解题效率。最优子结构性质和子问题重叠性质是采用动态规划算法的两个基本要素。
例1．多段图问题
设G=(V,E)是一个赋权有向图，其顶点集V被划分成k>2个不相交的子集Vi: ，其中，V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇)，下图
中所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi＋1中：，
＋1。
图6-1-1 一个5段图
多阶段图问题：求由s到t的最小成本路径（也叫最短路径）。对于每一条由s
到t的路径，可以把它看成在k-2个阶段作出的某个决策序列的相应结果：第i步决策就是确定Vi+1中哪个顶点在这条路径上。今假设s, v2, v3, … , vk-1, t是一条
由s到t的最短路径，再假定从源点s(初始状态)开始，已经作出了到顶点v2的决策(初始决策)，则v2就是初始决策产生的状态。若将v2看成是原问题的子问题
的初始状态，这个子问题就是找一条由v2到t的最短路径。事实上，路径v2, v3, … , vk-1, t一定是v2到t的一条最短路径。不然，设v2, q3, … , qk-1, t是一条由v2
到t的比v2, v3, … , vk-1, t更短的路径，则s, v2, q3, … , qk-1, t是一条由s到t的比s, v2, v3, … , vk-1, t更短的路径。与前面的假设矛盾。这说明多段图问题具有最优子结构性质。
例2． 0/1背包问题
有n件物品，第i件重量和价值分别是wi和pi, i=1, 2, …, n。要将这n件物品的一部分装入容量为c的背包中，要求每件物品或整个装入或不装入，不许分割出一部分装入。0/1背包问题就是要给出装包方法，使得装入背包的物品的总价值最大。这个问题归结为数学规划问题：
s.t.
0/1背包问题具有最优子结构性质。事实上，若是最优解，则将是0/1背包问题的子问题： max s.t.
i
i
(6.1.2)
最优解。因为，若是子问题(6.1.2)的最优解，且使得
则将是原问题(6.1.1)的可行解，并且使得
这与是最优解相悖。
例3. 矩阵连乘问题
给定n个数字矩阵A1，A2，…，An，其中Ai与Ai+1是可乘的，i=1,2,…,n-1.求矩阵连乘的加括号方法，使得所用的数乘次数最少。
考察两个矩阵相成的情形：C=AB。如果矩阵A，B分别是p×r和r×q矩阵，则它们的乘积C将是p×q矩阵，其(i, j)元素为
i=1,…,p, j=1,…,q, 因而AB所用的数乘次数是prq。如果有至少3个以上的矩阵连乘，则涉及到乘积次序问题，即加括号方法。例如3个矩阵连乘的加括号方法有两种：((A1A2)A3)和(A1(A2A3))。设A1，A2，A3分别是p0×p1，p1×p2，p2×p3矩阵，则以上两种乘法次序所用的数乘次数分别为：p0p1p2+p0p2p3和
p0p1p3+p1p2p3。如果p0=10, p1=100, p2=5, p3=50, 则两种乘法所用的数乘次数分别为：7500和750000。可见，由于加括号的方法不同，使得连乘所用的数乘次数有很大差别。对于n个矩阵的连乘积，令P(n)记连乘积的完全加括号数，则有如下递归关系
由此不难算出P=C(n-1)，其中C表示Catalan数：
也就是说，P(n)是随n指数增长的，所以，我们不能希望列举所有可能次序的连乘积，从中找到具有最少数乘次数的连乘积算法。事实上，矩阵连乘积问题具有最优子结构性质，我们可以采用动态规划的方法，在多项式时间内找到最优的连乘积次序。
用A[i:j]表示连乘积AiAi＋。分析计算A[1:n]的一个最优次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链分开，，则完全加括号方式为
＋n))，依此次序，我们先分别计算A[1:k]和
A[k+1:n]，然后将计算的结果相乘得到A[1:n]。可见，A[1:n]的一个最优序所包含的矩阵计算子链A[1:k]和A[k+1:n]的次序也一定是最优的。也就是说，矩阵连乘问题具有最优子结构性质。
如上三个例子都具有最优子结构性质，这个性质决定了解决此类问题的基本思路是：
首先确定原问题的最优值和其子问题的最优值之间的递推关系（自上向下），然后自底向上递归地构造出最优解（自下向上）。
最优子结构性质是最优化原理得以采用的先决条件。一般说来，分阶段选择策略确定最优解的问题往往会形成一个决策序列。Bellman认为，利用最优化原理以及所获得的递推关系式去求解最优决策序列，可以使枚举数量急剧下降。
4 这里有一个问题值得注意：最优子结构性质提示我们使用最优化原则产生的算法是递归算法，简单地使用递归算法可能会增加时间与空间开销。例如，用递归式直接计算矩阵连乘积A[1:n]的算法RecurMatrixChain的时间复杂度将是：
程序6-1-1 计算矩阵连乘的递归算法
int RecurMatrixChain(int i, int j)
{
if (i==j) return 0;
int u=RecurMatrixChain(i, i)
+RecurMatrixChain(i+1,j)
+p[i-1]*p[i]*p[j];
s[i][j]=i;
for(int k=i+1; k int t=RecurMatrixChain(i,k) +RecurMatrixChain(k+1,j) +p[i-1]*p[k]*p[j]; if (t u=t; s[i][j]=k;} } return u; } 如果用T(n)表示该算法的计算A[1:n]的时间，则有如下递归关系式： 当时 －， 可用数学归纳法直接证明：，这显然不是我们所期望的。注意到，在用递归算法自上向下求解具有最优子结构的问题时，每次产生的子问题并不总是新问题，有些问题被反复计算多次。如果对每一个问题只解一次，而后将其解保存在一个表格中，当再次需要解此问题时，只是简单地用常数时间查看一下结果，则可以节省大量的时间。在矩阵的连乘积问题中，若用 m[i][j]表示由第i个矩阵到第j个矩阵的连乘积所用的最少数乘次数，则计算 m[1][n]时共有个子问题。这是因为，对于，不同的有序对(i, 对应于不同的子问题，不同子问题最多只有下面将会看到， 个。 用动态规划解此问题时，可在多项式时间内完成。 程序6-1-2 求矩阵连乘最优次序的动态规划算法 { for (int i=1; i<=n; i++) m[i][i]=0; for (int r=2; r<=n; r++) for (int i=1; i<=n-r+1; i++){ int j=i+r-1; \\ r是跨度 m[i][j]= m[i+1][j]+p[i-1]*p[i]*p[j]; s[i][j]=i; for (int k=i+1; k int t= m[i][k]+ m[k+1][j]+p[i-1]*p[k]*p[j]; if (t< m[i][j]) { m[i][j]=t; s[i][j]=k; } } } } 算法MatrixChain的主要计算量取决于程序中对r, i和k的三重循环，循环体内的计算量为O(1)，三重循环的总次数是O(n3)，所以，算法的计算时间上界为 O(n3)。 例子求以下6个矩阵连乘积最少数乘计算次数及所采用乘法次序。 一般的计算m[i][j]以及s[i][j]的过程如下图所示： j 1 2 3 4 5 6 1 2 3 4 5 6 j 1 2 3 4 5 6 i 1 2 3 4 5 6 i m[i][j] s[i][j] 注意，上述算法只是明确给出了矩阵最优连乘次序所用的数乘次数m[1][n]，并未明确给出最优连乘次序，即完全加括号方法。但是以s[i][j]为元素的2维数组却给出了足够的信息。事实上，s[i][j]=k说明，计算连乘积A[i:j]的最佳方式应该在矩阵Ak和Ak+1之间断开，即最优加括号方式为(A[i:k])(A[k+1:j])。下面的算法Traceback按算法MatrixChain计算出的断点信息s指示的加括号方式输出计算 A[i:j]的最优次序。 程序6-1-3 根据最优值算法构造最优解 Void Traceback(int i, int j, int * * s) { if (i==j) return; Traceback(i, s[i][j], s); Traceback(s[i][j]+1, j, s); cout << “Multiply A” << i << “,” << s[i][j]; cout << “and A” << (s[i][j] +1) << “,” << j << endl; } 总结上面解矩阵连乘积问题，我们可以归纳出使用动态规划算法的基本步骤：1．分析最优解的结构 在这一步中，应该确定要解决的问题应该是具有最小子结构性质，这是选择动态规划算法的基础。 2. 建立递归关系 第一步的结构分析已经为建立递归关系奠定了基础。这一步的主要任务是递归地定义最优值，并建立该问题与其子问题最优值之间的递归关系。例如在矩阵连乘积问题中，递归关系为 - 在0/1背包问题中的递归关系是（gj(X)表示0/1背包问题Knap(j+1,n,X)的最优值） 在多段图问题中的递归关系是 这里j表示取Vi中的顶点j。 3. 计算最优值 依据递归关系式可以自底向上的方式（或自顶向下的方式－备忘录方法）进行计算，在计算过程中保存已经解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终获得多项式时间的算法。 4. 构造最优解 依据求最优值时记录的信息，构造出最优解（如矩阵连乘积）。 上述归纳的4个阶段是一个整体，必要时才分步完成，很多时是统一来完成的。§2. 多段图问题 多段图是一种简单而经典的使用动态规划算法的模型，它既能有效地反映动态规划算法的基本特征，而且在实际问题中有较多的应用。 图6-2-1 多段图的动态规划算法执行过程 最优值递推关系式为 min (6.2.1) 其中，COST(i,j)表示i段中顶点j到汇点t的最小成本路径的成本。根据(6.2.1)式，我们可以由后向前逐步确定各阶段中的顶点到汇顶点t的最短路径。对于如上的5阶段网络图，蓝色字体标出了各顶点到汇顶点t的最短距离。 事实上，我们也可以由前向后逐步确定由源顶点s到各阶段中顶点的最短路径，此时，最小成本的递归关系为 下图中的红色字体标出了由源顶点s到各顶点的最短距离。 图6-2-2 由前向后的处理方法（备忘录方法） 程序6-2-2 多段图的动态规划算法伪代码 MultiGraph(E, k, n, P) //有n个顶点的k段图G（按段序统一 //编号），E是边集，c(i, j)是边(i, j)的成本，P[1:k]是最小成 //本路径。 1 real COST(n); integer D(n-1)，P(k), r, j, k, n; 2 COST(n)=0; 3 4 5 6 7 8 9 for j from n-1 by –1 to 1 do 设r是这样一个顶点，且使得c(j, r)+COST(r)取最小值 COST(j)= c(j, r)+COST(r); D(j)=r; endfor P(1)=1; P(k)=n; for j from 2 to k-1 do 10 11 P(j)=D(P(j-1)); endfor 12 end MultiGraph 这里，D(j)将由j到汇顶点t的最短路径上j后面的顶点记录下来，P(j)则记录由源顶点s到汇顶点t的最短路径上处于第j阶段中的顶点。语句10是根据数组D中的信息逐段寻找到由源顶点s到汇顶点t的最短路径上的各个顶点。如果用邻接表表示图G，则语句4中r的确定可以在与d＋(j)成正比的时间内完成。因此，语句3－7的for循环所需的时间是。循环体9－11所需时间是，因而算法MultiGraph的时间复杂度是。下面给出的备忘录算法的时间复杂度也是如此。 程序6-2-3 多段图的备忘录算法伪代码 MemorizedMultiGraph(E, k, n, P) //有n个顶点的k段图G（按 //段序统一编号），E是边集，c(I, j)是边(I, j)的成本，P[1:k] //是最小成本路径。 1 real BCOST(n); integer D(n-1), P(k), r, j, k, n; 2 3 4 BCOST(1)=0; for j from 2 to n do 设r是这样一个顶点，且使得 BCOST(r)+ c(r, j) 取最小值 5 BCOST(j)= BCOST(r)+ c(r, j); 6 D(j)=r; 7 endfor 8 9 P(1)=1; P(k)=n; for j from k-1 by –1 to 2 do 10 P(j)=D(P(j+1)); 11 endfor 12 end MemorizedMultiGraph §3. 0/1背包问题 本节将使用动态规划的由前向后处理方法（也称备忘录算法）处理0/1背包问题： 10 s.t. （6.3.1） 通过作出变量x的取值序列来给出最优解。这个取值序列的对应决策序列是。在对xn作出决策之后，问题处于下列两种状态之一：背包剩余的容量仍为c，此时未产生任何效益；背包的剩余容量为，此时的效益值增长了pn。因而 一般地，如果记0/1背包子问题： s.t. 最优解的值为m[k][X]，则有 这里，而且。为使(6.13)式能够有效地递推下去，需要延拓k 和X的取值范围：；补充定义： 事实上，我们的主要目的是计算出m[n][c]，根据(6.11)式，我们可能需要计算，而为了计算，可能需要计算 ，如此等等，在递推公式(6.13)中用到的X值可能为负数。另外，如果将m[k][X]看作X的函数，则是一个分段函数，而且当取常值。所以将X的取值范围延拓至全体实数。 例子。时 由递推式(6.3.5)，，而且当时等式成立，这一事实可以写成 上述诸函数m[k][X]具有如下性质： 1．每个阶梯函数m[k][X]都是由其跳跃点偶(b,m[k][b])决定的。如果有个跳跃点，各点的函数值分别是v0,，则 这里约定。 2．令Sk是阶梯函数m[k][X]的跳跃点偶的集合，则阶梯函数 的跳跃点偶之集去掉点偶(0,0)后，恰是集合 12 这是因为函数的图象恰是由函数的图象先向右 平移wk，然后再向上移动pk而得。如前面例子 0 1 2 3 4 5 6 0 1 2 3 4 5 6 7 12S={(0,0), (2,1)} (w2, p2)=(3, 2) Sa={ (3,2), (5,3)} 2S={(0,0), (2,1), (3,2), (5,3)} 0 1 2 3 4 5 6 7 kk-1kk-1k根据递推公式(6.3.4)，S是从中去掉那些点偶(bi,vi)：在 中存 在点偶(bk,vk)使得而且，此时我们说(bk,vk)淹没(bi,vi)。前面例子的诸Sk计算如下： 3在由S2、Sa向S3的归并过程中，(5, 3)被(4, 5)淹没。 k 3．在处理实际问题时，由于要求，在计算时应该去掉那些使得的跳跃点偶(b,v)。根据前面的提到的淹没规则，如果将S中的元素按照第一个分量的递增次序排列，则第二个分量也呈递增的次序，而且Sn 的 最后一个元素，设为(b,v)，的v值即是0/1背包问题(6.3.1)的最优值m[n][c]。 k 4．最优解的获得可以通过检查诸Sk来确定。设(bkn,vkn)是Sn的最后一个元素。 若，则因为此时函数m[n][X]和函数[X]在 范围内的最大值一致，表明0/1背包问题(6.3.1)与其子问题 max 有相同的最优值。若，则。因为，此时函数m[n][X]在范围内的最大值是函数的最大值加pn，相应地，0/1背包问题(6.3.1)的最优值是其子问题(6.3.8)的最优值加pn。注意到此时跳跃点偶一定具有形式 其中。于是，我们可以依与否而决定取0或 1。如此等等，我们可以逐一确定的值。 在上述例子中，整理后的诸Sk为： (6, 6)是S3的最后一个跳跃点偶，所以该0/1问题的最优值是6。这个点偶不在 S2中，因而又，据此判断x2的取值。因为，所以；最后由知，所以最优解为(1,0,1). 为实现上述算法，可以用两个一维数组B和V来存放所有的跳跃点偶(b, v)，跳跃点偶集互相邻接地存放（将诸Si中的全部元素统一编号，从Si 生成时，元素也是递升地产生，而且使用淹没规则），并用指针F(k)来指示集合Sk，即Sk的第一个元素的位置，而F(n)-1是1中最后一个元素的位置（这里不存放Sn是由于我们只需要它的最后一个元素，而这个元素或者是Sn-1的最后一个元素，此时Sn-1与Sn有相同的最后元素；或者具有形式(6.3.9)，而14 且vkn是满足的最大值。所以，确定S的最后元素不必将S的元素全部求出来。而且确定最优解的其它变量时也不使用数据Sn）。因为产生 kSk仅使用信息Sk-1和(wk,pk)，所以不必存储Sa。根据以上分析，我们不难给出nn 动态规划解0/1背包问题的算法伪代码。 程序6-3-1 0/1背包问题动态规划算法伪代码 DKnapsack(w, p, c, n, m) //数组w, p中的元素分别代表各件物品的 //重量和价值，n是物品个数，c代表背包容量 real p(n), w(n), B(m), V(m), ww, pp, c; integer F[0:n], l, h, i, j, p, next; F[0]=1; B[0]=V[0]=0; l=1; h=1; //S0的首和尾 F(1)=2; next=2; // B、V中的第一个空位 for i from 1 to n-1 do k=l; u=最大指标r，使得而且 for j from l to u do (ww, pp)=( B[j]+wi, V[j]+pi); //Sia中的下一个元素 从Si-1中取来元素归并 B[next]=B[k]; V[next]=V[k]; Next=next+1; k=k+1; endwhile pp=max(V[k], pp); k=k+1; endif if pp > V[next-1] then (B[next], V[next])=(ww, pp); next=next+1; endif -1] do //清除 k=k+1; endwhile endfor 将Si-1剩余的元素并入Si (B[next], V[next])= (B[k], V[k]); next=next+1; k=k+1; endwhile l=h+1; h=next-1; F(i+1)=next; //为Si+1赋初值 endfor traceparts // 逐一确定 end Dknapsack 算法DKnapsack 的主要工作是产生诸Si。在i > 0的情况下，每个Si由Si-1和Si a归并而成，并且-1|。因此-1|， 由此知，算法DKnapsack的空间复杂度是O(2n)。 由Si-1生成Si需要的时间，因此，计算总共需要的时间为 ，算法DKnapsack的时间复杂度为O(2n)。 如果物品的重量wi和所产生的效益值pi都是整数，那么，Si中的元素(b,v)的分量b和v也都是整数，且 也都是不同的，故。又Si中不同的元素对应的各分量 此时算法DKnapsack的时间复杂度为。 附：从组合的角度来理解0/1背包问题 先假定背包的容量是充分大的，考虑有k件物品往背包里装时，背包中物品总重量的各种可能出现的情况： 16 一般地， 而 ， k递推关系式(6.3.10)正是我们计算诸Sk和Sa的依据，这只需将各种“重量”情 k况所对应的总价值带上，即产生元素对(b,v)，就能获得诸Sk和Sa。如上面的例子： 去掉被淹没的(5,3)最后将S3截断（根据约束条件），即去掉“重量”大于背包容量的点对，就得到所 需要的点对集 得到最大价值是6，因为\S2，应该是在前面的基础上增加了 而获得的，这个“基础”就是，所以，最优解中，。再考虑的情况，在最优解中应有。最后由\S0知，在最优解中。所以，(1,0,1)就是上面背包问题的一个最优解。 §4. 流水作业调度问题 问题描述：已知n个作业{1, 2, . . . , n}要在由两台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi，。流水作业调度问题要求 确定这n个作业的最优加工次序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。 记N={1, 2, . . . , n}，S为N的子集合。一般情况下，当机器M1开始加工S中的作业时，机器M2可能正在加工其它的作业，要等待时间t后才可用来加工S中的作业。将这种情况下流水线完成S中的作业所需的最短时间记为T(S, t)，则流水作业调度问题的最优值即是T(N, 0)。 流水作业调度问题具有最优子结构性质。事实上，设是n个流水作业的一个最优调度（实际上是作业的一个排序），其所需要的加工时间为，其中，T'是在机器M2的等待时间为时，调度安排作业所需的时间。若记\，我们证明。 首先由T'的定义知。如果，设是作业集S在机器M2等待时间为情况下的一个最优调度，则是N的一个调度，该调度所需的时间为a，这与是N的最优调度矛盾。所以，说明流水作业调度问题具有最优子结构性质。 关于流水作业调度问题的最优值递推关系式，我们可以如下建立。容易看出 \ 上述关系式可以推广到一般情形： \ 其中，这一项是由于在机器M2上，作业i必须在max{t,ai}时间之后才能开工。因此，在机器M1完成作业i之后，机器M2还需等待 时间后才能完成对作业i的加工。 按照递推关系(6.4.2)，我们容易给出流水调度问题的动态规划算法，但是其时间复杂度将是O(2n)。以下我们将根据这一问题的特点，采用Johnson法则简化算法，使得到时间复杂度为O(nlogn)。 设是作业集S在机器M2的等待时间为t时的任一最优调度。若在这个调度中，安排在最前面的两个作业分别是i和j，即。则由递推关系18 式(6.4.2)得 \\{i,j},tij) 其中 （上述推导中用到了关系式） 如果作业i和j满足 则称作业i和j满足Johnson不等式；不等式(6.4.3)等价于 此时，。因而 T(S\\{i,j},tji) (6.4.5) 如果作业i和j不满足Johnson不等式，则交换作业i和j的加工次序使满足Johnson不等式。在作业集S当机器M2的等待时间为t时的调度中，交换作业i和j的加工次序，得到作业集S的另一个调度，它所需的加工时间为 \{i,j},tji) 根据(6.4.5)式，。说明当作业i和j不满足Johnson不等式时，交换它们的加工次序后，不会增加加工时间。由此可知，对于流水作业调度问题，必然存在一个最优调度，使得作业和满足Johnson不等式： 一般地，可以证明，上述不等式与不等式 等价。 以下给出的是流水作业调度问题的Johnson算法： (1) 令 (2) 将AB中作业依ai的非减次序排列；将BA中作业依bi的非增次序排 列； (3) AB中作业接BA中作业即构成满足Johnson法则的最优调度。 程序6-4-1 流水作业调度问题的Johnson算法 int FlowShop(int n, int a, int b, int c) { class Jobtype{ public: int operator <= (Jobtype a) const {return (key <= a.key);} int key; int index; bool job; }; Jobtype *d=new Jobtype [n]; for (int i = 0; i< n; i++) { D[i].key = a[i] > b[i] ? b[i] : a[i]; D[i].job = a[i] <= b[i]; D[i].index = i; } sort(d, n) int j = 0, k = n-1; for (int i = 0; i < n; i++) { if ( d[i].job ) c[j++] = d[i].index; else c[k--] = d[i].index; } j = a[c[0]]; k = j + b[c[0]]; for (int i = 1; i < n; i++) { j + =a[c[i]]; k = j < k ? k + b[c[i]] : j + b[c[i]]; } 20 delete d; return k; } 上述算法的时间主要花在排序上，因此，在最坏情况下的时间复杂度为 O(nlogn)。空间复杂度为O(n)更容易看出。 §5. 最优二叉搜索树 设是一个有序集合，且表示有序集合的二叉搜索树是利用二叉树的顶点存储有序集中的元素，而且具有性质：存储于每个顶点中的元素x大于其左子树中任一个顶点中存储的元素，小于其右子树中任意顶点中存储的元素。二叉树中的叶顶点是形如的开区间。在二叉搜索树中搜索一个元素x，返回的结果或是在二叉树的内部顶点处找到：或是在二叉树的叶顶点中确定：x现在假定在第一种情况出现，即的概率为bi；在第二种情况出现，即的概率为ai.这里约定 显然 集合称为有序集S的存取概率分布。 在一个表示S的二叉搜索树T中，设存储元素xi的顶点深度（从根到该顶点的距离）为ci，叶顶点的深度为di，则 .2) 表示在二叉搜索树T中做一次搜索所需的平均比较次数。p也称为二叉搜索树T 的平均路长。最优二叉搜索树问题是 对于有序集S及其存取概率分布，在所有表示S的二叉搜索树中，找出一棵具有最小平均路长的二叉搜索树。 为了采用动态规划算法，我们首先要考虑该问题是否具有最优子结构性质。二叉搜索树T的一棵含有顶点和叶顶点 的子树可以看作是有序集关于全集为实数区间的一棵二叉搜索树（T自身可以看作是有序集关于全集为整个实数区间的二叉搜索树）。根据S的存取分布概率，x在子树的顶点处被搜索到的概率是 于是的存储概率分布为，其中，h,k分别是下面的条件概率： 设Tij是有序集关于存储概率分布的一棵最优二叉搜索树，其平均路长记为pij. Tij的根顶点存储的元素是xm,其左子树Tl和右子树Tr的平均路长分别记为pl和pr。由于Tl和Tr中顶点深度是它们在Tij中的深度减1，我们得 由于Tl是有序集的一棵二叉搜索树，故若 ，则替换Tl可得到平均路长比Tij更小的二叉搜索树。这与Tij是最优二叉搜索树矛盾。同理可证，Tr也是一棵最优二叉搜索树。因此，最优二叉搜索树问题具有最优子结构性质。 T2,10 采用上面的记号，则n元最优二叉搜索树问题即是求T1，n，其最优值为p1,n。 由最优二叉搜索树的最优子结构性质，可以建立最优值pi,j的递推公式： 初始时，记wijpij为m(i,j)，则为所求最优值。由(6.5.6)不难推得关于m(i,j)的递推公式 据此，可以设计求解最优二叉搜索树问题的动态规划算法。 程序6-5-1 最优二叉搜索树的动态规划算法 void OptimalBinarySearchTree( int a, int b, int n, int **m, int **s, int **w) { for (int i = 0; i < n; i++) { w[i+1][i] = a[i]; m[i+1][i] = 0; } for (int r = 0; ir< n; r++) { for (int i = 1; i <= n-r; i++) { int j = i+r; w[i][j] = w[i][j-1] + a[j] +b[j]; m[i][j] = m[i+1][j]; s[i][j] = i; for (int k =i + 1; k<= j; k++) { int t = m[i][k-1] + m[k+1][j]; if (t < m[i][j]) {