算法设计教程04.ppt

1、1,学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。,第4章 动态规划(DP)Dynamic Programming,2,最优化原理,1951年美国数学家RBellman等人，根据一类多阶段问题的特点，把多阶段决策问题变换为一系列互相联系的单阶段问题，然后逐个加以解决。 同时，提出了解决这类问题的“最优化原理”(PrincipleofOptimalit

2、y)。 “最优化原理”用数学化的语言来描述：假设为了解决某一优化问题，需要依次作出n个决策D1，D2，Dn，如若这个决策序列是最优的，对于任何一个整数k，1 k n，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策Dk+1，Dk+2，Dn也是最优的。（最优子结构性质 ）,3,最优化原理,最优化原理是动态规划的基础。任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件： (1) 问题中的状态必须满足最优化原理；(2) 问题中的状态必须满足无后效性。 所谓的无后效性是指：“下一时刻的状态只与当

3、前状态有关，而和当前状态之前的状态无关，当前的状态是对以往决策的总结”。,4,动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解。,4.1算法总体思想,动态规划通常应用于最优化问题，即做出一组选择以达到一个最优解。关键是存储子问题的每一个解，以备它重复出现。,5,动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题。,4.1算法总体思想,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重

4、复计算了许多次。,6,问题4-1：存在一个数字三角形，从顶到底有多条路径， 每一步可沿左斜线向下或垂直向下。路径所经过的数字之和称为路径得分，要求求出最小路径得分。,状态表示1-1 用一元组D（X）描述问题，D（X）表示从顶到达第X层的得分。但是一元组D（X）描述的子问题不能满足最优子结构性质，因为D（X）的最优解可能不包含子问题D（X-I）的最优解。这样，动态规划方法是无法在状态表示1-1上应用。,动态规划对状态表示的要求,7,状态表示 1-2 用二元组D（X，Y）描述问题，D（X，Y）表示到达第X层第Y个位置时的得分，那么 D（X，Y）的最优解包含了子问题D（X+1，Y）或D（X+1，Y-

5、1）的最优解，状态转移方程为 : D（X，Y）= minD(X+1,Y),D(X+1,Y-1)+AX,Y D（4，*）= A4,*,8,D(X，Y)= min D(X+1，Y),D(X+1,Y-1) + AX，Y,9,声明部分； 输入a数组,M行N列；/下标从1开始 for (j = 1; j =1; i-) /自底向上DP for (j =M-i+1,n=1; n=2*i; j+,n+) Dij=min(Di+1j,Di+1,j-1)+aij; coutmin(D1); /输出第一行最小值 ,10,D(X，Y)= min D(X-1，Y),D(X-1,Y+1) + AX，Y,11,4.1算法

6、总体思想,动态规划设计一般要经历以下几个步骤： 1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。 2、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。 3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。 4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。 5、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。,12,4.1算法总体思想,1、阶段：把问题分成几个相互联系的有

7、顺序的几个环节，这些环节即称为阶段。 2、状态：某一阶段的出发位置称为状态。 3、决策：从某阶段的一个状态演变到下一个阶段某状态的选择。 4、状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。,13,4.1算法总体思想,动态规划与一般搜索技术最大不同的地方就是记录了已求解过的问题的结果。 子问题的记录： 最重要、最为复杂 状态表示 用一个数、一组数或一个向量来实现状态表示 子问题结果的记录,14,动态规划算法求解问题的一般思路,【例题4-2】最短路径问题。图中每个顶点代表一个城市，两个城市

8、间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少?,15,动态规划算法求解问题的一般思路,【分析】 把从A到E的全过程分成四个阶段，用k表示阶段变量 第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2； 第2阶段有两个初始状态B1、B2，B1有三条可供选择的支路，B2有两条可供选择的支路。 用dk(xk，xk+1)表示在第k阶段由初始状态xk到下阶段的初始状态xk+1的路径距离，Fk(xk)表示从第k阶段的xk到终点E的最短距离，利用倒推方法求解A到E的最短距离。,16,动态规划算法求解问题的一般思路,S1:K=4，有：F4

9、(D1)=3，F4(D2)=4，F4(D3)=3 S2: K=3，有：F3(C1)=mind3(C1,D1)+F4(D1),d3(C1,D2)+F4(D2)=min8,10=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6 S3: K=2，有：F2(B1)=mind2(B1,C1)+F3(C1),d2(B1,C2)+f3(C2),d2(B1,C3)+F3(C3)=min9,12,14=9 F2(B2)=mind2(B2,c2)+F3(C2),d2(B2,C4)

10、+F3(C4)=min16,10=10 S4：k=1，有：F1(A)=mind1(A,B1)+F2(B1),d1(A,B2)+F2(B2)=min14,13=13因此由A点到E点的全过程的最短路径为AB2一C4D3E。最短路程长度为13。,17,动态规划算法求解问题的一般思路,每个阶段中，都求出本阶段的各个初始状态到过程终点E的最短路径和最短距离，当逆序倒推到过程起点A时，便得到了全过程的最短路径及最短距离，同时附带得到了一组最优结果(即各阶段的各状态到终点E的最优结果)。,18,思考与练习：若城市路径示意图如图所示，图中，每条边上的数字是这段道路的长度。条件：从A地出发，只允许向右或向上走。

11、试寻找一条从A地到B地的最短路径和长度。,19,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,在动态规划中，可将一个问题的解决方案视为一系列决策的结果。不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。,20,4.1算法总体思想,动态规划设计的一般模式： for k=阶段最小值 to 阶段最大值 do /顺推每一个阶段 for i=状态最小值 to 状态最大值 do /枚举阶段k的每一个状态 for j=决策

12、最小值 to 决策最大值 do /枚举阶段k中状态i可选择的每一种决策 fik=min(max)fik-1+aik-1,jk-1|ik-1通过决策jk-1可达ik,21,4.2 动态规划算法的基本要素,一、最优子结构,某个问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。,例如图中，若路线I和J是A到C的最优路径，则根据最优化原理，路线J必是从B到C的最优路线。 用反证法证明：假设有另一路径J是B到C的最优路径，则A到C的路线取I和J比I和J更优，矛盾。从而证明J必是B到C的最优路径。 最优子结构是问题能用动态规划算法求解的前提。,22,4.2动态规划算法的基本要素,二、重叠子问

13、题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。,动态规划算法对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。,通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,23,4.2动态规划算法的基本要素,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,步骤： 为每个问题建立一个记录项，初值设为一个特殊值（表未

14、求解） 每个待求解子问题，首先查记录项，有解答则直接选取，否则求解该子问题。,24,4.3 典型问题-LIS(Longest Increasing Subsequence),【问题描述】给出一个序列a1,a2,a3,a4,a5,a6,a7.an，求它的一个子序列（设为s1,s2,.sn），使得这个子序列满足这样的性质，s1s2s3.sn并且这个子序列的长度最长。 【任务】输出这个最长子序列的长度。 【样例输入】 1 7 3 5 9 4 8 【样例输出】 1 3 5 9, 长度为4 1359、1348,25,4.3 典型问题- LIS,.,26,4.3 典型问题- LIS,最长队列长度,/a数组

15、存储原始数据 /b数组存储对应最长上升子序列长度,27,4.3 典型问题-LIS,#define MAXN 200 void main() int n, aMAXN, bMAXN, cMAXN, i, j, max,lab,preMAXN; /a数组存储原始数据，pre数组存储前一个数据编号 /b数组存储对应最长上升子序列长度 for (i = 1; i ai; memset(b, 0, sizeof(a); memset(c, 0, sizeof(c);,28,4.3 典型问题-LIS,/求最长上升子序列O(n2) b1 = 1; prei=0; /i=1-n for (i = 2; i =

16、 1; j-) /枚举每个状态 if (ajmax) max = bj; prei=j; bi = max + 1; ,29,4.3 典型问题- LIS,30,/lab:max所对应a数组元素下标 O(n) max = b1; for (i = 2; i max) max = bi;lab=i; coutLongest Increasing Subsequence is：maxendl;,31,4.3 典型问题-LIS,/拷贝数列到C数组 i = lab;int num=max;j=max; while( num0 ) cj=ai; j-； i=prei; num-; /输出数列O(n) fo

17、r(i=1;i=max;i+) coutsetw(6)ci; coutendl; ,32,4.3 典型问题-合唱队形,【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, , K，他们的身高分别为T1, T2, , TK，则他们的身高满足T1 Ti+1 TK (1 = i = K)。 【任务】已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【样例输入】8 186 186 150 200 160 130 197 220 【样例输出】 4 【说明】

18、该样例中，可以要队头身高186的两个人出列,以及队尾197和220的人出列,共4人出列,所以输出4.,33,4.3 典型问题-合唱队形,【算法分析】:分别从左到右求最大上升子序列，从右到左求最大下降子序列，再枚举中间最高的一个人。算法时间复杂度O(N2)。 【思路】：递推关系式 bi=maxbj(1 aj+1 ci=maxcj(i aj+1 合唱队人数=maxbi+ci-1 (第i个人被重复计算了一次) 出列人数=N-合唱队人数 =N-(maxbi+ci-1),34,4.3 典型问题-合唱队形,最长队列长度-1,4.3 典型问题-合唱队形,#include #define MAXN 200 m

19、ain() int n, aMAXN, bMAXN, cMAXN, i, j, max; cinn; for (i = 1; i ai; memset(b, 0, sizeof(a); memset(c, 0, sizeof(c);,/求左侧的最长上升子序列 O(n2) b1 = 1; for (i = 2; i = 1; j-) if(ajmax) max = bj; bi = max + 1; ,4.3 典型问题-合唱队形,/求右侧的最长上升子序列 O(n2) cn = 1; for (i = n - 1; i 0; i-) max = 0; for (j = i + 1; j max)

20、max = cj; ci = max + 1; ,4.3 典型问题-合唱队形,/求需要出列人数 O(n) max = b1 + c1; for (i = 2; i max) max = bi + ci; printf(%dn, n - max + 1); ,思考：如何判断哪些人出队列？,38,4.4 典型问题最大k乘积,题目：在一个长度为N的数字串中插入k-1个乘号，将N分成k部分，找出一种分法，使得这k个部分的乘积最大。 a1a2.ai.aj.an 例如有一个数字串: 312，当N=3，K=2时会有以下两种分法： 1）3*12=36 2）31*2=62这时，符合题目要求的结果是： 31*2=

21、62,39,K部分,3部分,2部分,1部分,解决方法,示例：1321,13*2*1,2部分,3部分,1*3*21,1*32*1,13*2*1,Max,1*321 13 * 21 132*1,41,m(d,j-1)表示：前d位(从1.d)分成j-1段所得的最大乘积 若要求出分为k个部分的最大乘积，则只需穷举分为k-1部分基础上再加一个乘号，乘号的插入位置d。打擂台选出d在各个位置时得到的最大乘积即为问题的解。 依此类推，把k-1的问题归结为k-2的情况 .求在任意一段中插入0个乘号的最大乘积 .在任意一段中插入0个乘号时的最大乘积，而此时的值即为该段的数值。,m(i,j)表示：前i位(从1.i)

22、分成j段所得的最大乘积 m(2,2)=maxm(1,1)*w(2,2) m(3,2)=maxm(1,1)*w(2,3),m(2,1)*w(3,3) m(3,3)=maxm(2,2)*w(3,3) m(4,2)=maxm(1,1)*w(2,4),m(2,1)*w(3,4), m(3,1)*w(4,4) m(4,3)=maxm(2,2)*w(3,4),m(3,2)*w(4,4),13,132,1321,3,32,6,321,63,43,4.4 典型问题最大k乘积,设w(h1,h2) : 从第h1位到第h2位所组成的十进制数。 h2h1才有意义 W为N行N列右上三角矩阵,for(i=1; i= N;

23、 i+) /O(n2) wii= ai ; /对角线元素 for(j=i+1 ; j= N; j+) wij = wij-1*10 + aj ; ,44,设m(i,j)表示：前i位(从1.i)分成j段所得的最大乘积,则可得到如下的DP方程： if(j=1) m(i,1) = w(1,i) ; if(j =1 ,void maxdp(int n,int k,int *a) for(i=1; imax) max = temp ; mij = max ; ,46,main() La=0； 输入n和k的值; while ( ( c=getchar() )!=n) /*读入数据*/ a+la = c-0

24、 ; for(i=1; i= N; i+) /O(n2) wii= ai ; for(j=i+1 ; j= N; j+) wij = wij-1*10 + aj ; ,47,for(i=1 ; i= N; i+) /输出O(n2) for(j=1 ; j= N; j+) printf(%5d,wij); printf(n); maxdp(N,k,a) ; printf(nmax=%ld ,mNk) ; ,49,进一步的问题是: 最大乘积是怎么得到的呢？ 乘号插入的位置 用什么表达式描述记录？,4.4 典型问题最大k乘积,50,分析： 表达式即求哪一位后面插入乘号，根据刚才的分析，d表示最后一个

25、乘号的位置，但d仅仅是将i位分成j 部分最后一个乘号的位置。 可以利用一个二维数组bitij表示前i位分成j份最后一个乘号的位置,for(i=1; imax) max = temp; maxIndex = d; m(i , j) = max; bit i j = maxIndex; ,52,目前已经知道任意前几位分成任意部分最后一个乘号的位置。 int i = n, j = k; while(j 1) cout biti jendl; /前 i 分成 j部分的最后一个乘号号位置 i = biti j; j-; ,53,4.5 典型问题0-1背包问题,问题描述给定n种物品和一背包。物品i的重量是

26、wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大? 0-1背包问题是一个特殊的整数规划问题。,54,4.5 典型问题0-1背包问题,1、减小规模 m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。 m(i+1，j)可选择物品为i+1，n时0-1背包问题的最优值。 m(n，j)可选择物品为n时0-1背包问题的最优值。规模已经为1,55,4.5 典型问题0-1背包问题,2、推导递归式，判断第i件？,1）不放，背包当前产生价值仍为m(i+1，j)；,2）放入，调整背包容量j-wi，背包当前产生价值为 m(i+1,j-wi)+

27、vi,56,4.5 典型问题0-1背包问题,m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。 由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下:,void KnapSack(int v,int w,int c,int n,int m11) int jMax=min(wn,c); for (j=0;j=wn时, m(n,j)=vn mnj=vn; for (i=n-1;i=1;i-) /DP int jMax=min(wi,c); for (j=0;j=wn mij=max(mi+1j,mi+1j-wi+vi); coutm1c; /在C容量

28、可获的最大价值 ,58,4.5 典型问题0-1背包问题,黑板演示 N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6,59,4.5 典型问题0-1背包问题,算法复杂度分析： 从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。,N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6,m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值,60,4.5 典型问题0-1背包问题,用倒推法来求出每种物品是否选中。选中1，2，5三件物品，最高价值15，总重8

29、。,void traceback(int m11,int w,int c,int n,int x) for(i=1;i0 ? 1:0); ,N=5，c=10，w=2，2，6，5，4,v=6,3,5,4,6,61,4.5 0-1背包问题-改变m(i,j)含义,1、减小规模 m(i，j)是背包容量为j，可选择物品为1,2,3.i时0-1背包问题的最优值。 m(i+1，j)可选择物品为1,2,3.i ,i+1时0-1背包问题的最优值。 m(1，j)可选择物品为1时0-1背包问题的最优值。规模已经为1,62,4.5 典型问题0-1背包问题,2、推导递归式，判断是否放入第i件？ 1）不放，背包当前产生价

30、值仍为m(i-1，j)； 2）放入，调整背包容量j-wi，背包当前产生价值为 m(i-1,j-wi)+Vi,63,4.5 典型问题0-1背包问题,N=5，c=10，w=2，2，6，5，4, v=6,3,5,4,6,64,【思考】贪心算法与动态规划的差异,对于具有最优子结构的问题应该选用贪心算法还是动态规划算法求解? 是否能用动态规划算法求解的问题也能用贪心算法求解?,65,思考与练习项目选择问题,某工厂预计明年有A,B,C,D四个新建项目，每个项目的投资额 wk及其投资后的收益 vk如下表所示。投资总额为30万元，问如何选择项目才能使总收益最大。 上述问题的静态规划模型如下：,66,分析项目选

31、择问题,1、描述该问题的最优解 若x1 x2. xn是使总收益最大的最优解(xi 0,1)，此时总投资额为C，投资项目的选择范围为1n，我们将这个最优解记为m1c; 则x2 x3. xn也必定是在总投资额为c-w1x1 (当x1=0时为c，x1=1时为c-w1)，投资项目的选择范围为2n时的子问题的最优解，我们将其记为m2c-w1x1; 此时我们需要证明这一结论，用反证法即可。 证明： 假设x2 x3. xn不是当前状态的最优解，则必定存在一个解z2 z3. zn为最优解，这样对于整个问题的最优解就应该是x1 z2 z3. Zn。这显然与x1 x2. xn为最优解相矛盾，故假设不成立，得证。,

32、2、递归定义最优解 若我们把投资总额为j，投资项目的选择范围为in时的问题的最优解定义为mij； 显然，按照第一步的模式，m1c的子问题的最优解为m2c-w1x1，那么mij的子问题的最优解就应该为mi+1j-wixi； 于是我们可以把这个问题递归定义为： mij=maxmi+1j,mi+1j-wi+vi（这两项是由xi的两种取值不同而来的） 再根据j的取值范围我们便可以得到这个问题的递归式：,边界条件为：,68,3、以自底向上的方式计算出最优值 void KnapSack(int v,int w,int c,int n,int m11) int jMax=min(wn-1,c); for (

33、j=0;j1;i-) int jMax=min(wi-1,c); for (j=0;j=w1) m1c=max(m1c,m2c-w1+v1); ,69,4.6 典型问题花瓶插花问题,【问题描述】想以最美观的方式布置花店的橱窗。 有F束花，每束花的品种都不一样，同时至少有同样数量的花瓶。 花瓶从左到右按1 到 V编号。 花束可以移动，并且每束花用1到F的整数唯一标识，花束的整数决定了花束在花瓶中的排列的顺序，如果ij，则花束i必须放在花束j左边的花瓶中。 如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶只能放一束花。,70,4.6 典型问题花瓶插花问题,当各个花瓶中放入不同的花束时，

34、会产生不同的美学效果，并以美学值（一个整数）来表示，空花瓶的美学值为0。 假设有3束花，5个花瓶。花瓶与花束不同的搭配所具有的美学值，可以用如下的表格表示： pij：第i束花插入第j个花瓶的好看程度,pFV,71,4.6 典型问题花瓶插花问题,qij表示1.i束鲜花插入1.j个花瓶所能得到的最大好看程度,1.j束鲜花插入到前面的1.j只花瓶中,所得到的好看程度是 qjj=p11+p22+.+p jj. 第i束鲜花若放入第j号花瓶,最大好看程度是qi-1j-1+pij; 第i束鲜花若放入前j-1个花瓶中的某一个,所得的好看程度是qij-1, 插入第i束鲜花所能得到的最大好看程度为:qij=MAX

35、(qi-1j-1+pij,qij-1),72,4.6 典型问题花瓶插花问题,qij表示1.i束鲜花插入1.j个花瓶所能得到的最大好看程度,规划方程为: qij=MAX(qi-1j-1+pij,qij-1),边界条件为： q00=0；q0j=0(1=j=v),73,/没有一束花插入花瓶时,好看程度为0 q00=0; / v束鲜花分别插入v个花瓶时最大好看程度 for(j=1;j=V;j+) q0j=0; /设置第j束鲜花放入第j号花瓶中的最大好看程度 qjj=qj-1j-1+pjj; ,qij,74,for (j=1;j=V; j+) for(i=1;ij; i+) /计算在第j阶段,插入第i束

36、鲜花所能得到的最大好看程度 qij=MAX(qi-1j-1+pij,qij-1); return(qFV);,qij,qFV,75,/确定第i束花放的花瓶编号wayi,newv=V; /wayi确定第i束花放的花瓶 for (i=F; i0;i-) /i代表花束编号 while(qi-1newv-1+pinewvqinewv) newv-; /确定鲜花i插在花瓶newv中,并准备考虑前一只花瓶 wayi=newv; newv-； ,qij,qFV,76,4.7 田忌赛马,问题描述 田忌与齐王赛马，双方各有n匹马参赛（n=100），每场比赛赌注为1两黄金，已知齐王与田忌的每匹马的速度，并且齐王肯

37、定是按马的速度从快到慢出场，写一个程序帮助田忌计算他最好的结果是赢多少两黄金（输用负数表示）。,77,4.7 田忌赛马,分析：先排序，齐王的马的速度放在数组a中，田忌的马的速度放在数组b中。,算法是动态规划和贪心算法相结合。 从两人的最弱的马入手： 若田忌的马快，就让这两匹马比赛； 若田忌的马慢,干脆就让他对付齐王最快的马； 若两匹马的速度相等，这时有两种选择方案，或者它俩比赛，或者对付齐王最快的马。,78,4.7 田忌赛马,定义子问题：c(i，j)为齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益。 初始化时：ci1表示齐王的第i匹马与田忌最快的马比赛的结果。,79

38、,4.7 田忌赛马,c(i，j):齐王的i.j匹马与田忌的第j匹马比赛，田忌所获得的最大收益,80,4.7 田忌赛马,for(i=n-1;i=1;i-) for(j=2;jbj) cij=ci+1j-1-1; if(ai+j-1=bj) cij=max(ci+1j-1-1,cij-1)； ,81,4.7 田忌赛马,c(i，j):齐王的从第i匹马开始的j匹马与田忌的最快的j匹马比赛，田忌所获得的最大收益,82,练习,83,提示：,for(r=n-2;r=0;r-) for(c=0;ctr+1c+1) trc+=tr+1c; else trc+=tr+1c+1;,7 8 10 74 4 452 6

39、 5,84,4.8 典型问题石子归并问题（略）,问题描述在一个圆形操场的四周摆放着N堆石子(N=100),现要将石子有次序地合并成一堆. 规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数记为该次合并的得分. 编写一程序,读入堆栈数N及每堆栈的石子数(=20). 选择一种合并石子的方案, 做N-1次合并,使所有得分的总和最小（最大）。,85,4.8 典型问题石子归并问题,方法一每次找相邻最小的两堆合并 从最左上面的一堆开始,沿顺时针方向排成一个序列. 合并的过程如下: 每次合并得分: 第一次合并 3 4 6 5 4 25 第二次合并 5 4 6 5 4 9 第三次合并 9 6 5

40、4 9 第四次合并 9 6 9 15 第五次合并 15 9 24 总得分=5+9+9+15+24=62,例如有6堆石子,每堆石子数依次为3 4 6 5 4 2. 要求做5次合并,得分的总和最小.,贪心法：每一次选择得分最小的相邻两堆合并,不一定保证余下的合并过程能导致最优解.,86,4.8 典型问题石子归并问题,方法二：另外方法逐次合并 合并的过程如下: 每次合并得分: 第一次合并 3 4 6 5 4 27 第二次合并 7 6 5 4 2 13 第三次合并 13 5 4 2 6 第四次合并 13 5 6 11 第五次合并 13 11 24 总得分=7+13+6+11+24=61,例如有6堆石子

41、,每堆石子数依次为3 4 6 5 4 2. 要求做5次合并,得分的总和最小.,如果N-1次合并的全局最优解包含了每一次合并的子问题的最优解,那么经这样的N-1次合并后的得分总和必然是最优的.,87,4.8 典型问题石子归并问题,例如上例中第五次合并石子数分别为13和11的相邻两堆. 这两堆石头分别由最初的第1,2,3堆(石头数分别为3,4,6)和第4,5,6堆(石头数分别为5,4,2)经4次合并后形成的. 于是问题又归结为如何使得这两个子序列的N-2 次合并的得分总和最优. 为了实现这一目标,我们将第1个序列又一分为二: 第1、2堆构成子序列1,第3堆为子序列2. 第一次合并子序列1中的两堆,

42、得分7; 第二次再将之与子序列2的一堆合并,得分13. 显然对于第1个子序列来说,这样的合并方案是最优的. 同样,我们将第2个子序列也一分为二: 第4堆为子序列1,第5,6堆构成子序列2. 第三次合并子序列2中的2堆,得分6; 第四次再将之与子序列1中的一堆合并,得分13. 显然对于第二个子序列来说,这样的合并方案也是最优的. 由此得出一个结论: 6堆石子经过这样的5次合并后,得分的总和最小.,88,4.8 典型问题石子归并问题,动态规划思路： 阶段i：石子的每一次合并过程，先两两合并，再三三合并，.最后N堆合并 状态s：每一阶段中各个不同合并方法的石子合并总得分。 决策：把当前阶段的合并方法

43、细分成前一阶段已计算出的方法，选择其中的最优方案。 采用动态规划求解的关键是确定所有石子堆子序列的最佳合并方案。 这些石子堆子序列包括：第堆、第堆、第堆、第堆、第N堆、第堆；第堆、第堆、第堆、第堆、第堆、第堆、第N堆、第堆、第堆；第堆、第N堆第2堆、第N堆、第堆第N堆、第堆、第N堆,89,4.8 典型问题石子归并问题,为了便于运算，我们用i，j表示一个从第i堆数起，顺时针数j堆时的子序列第i堆、第i堆、第（ij1）mod n堆 设fi，j将子序列i，j中的j堆石子合并成一堆的最佳得分和；ci，j将i，j一分为二，其中子序列的堆数；（iN，jN）显然，对每一堆石子来说，它的fi，1因为一开始还没

44、有合并，所以这些值应该全部为0。 ci， (1iN),90,4.8 典型问题石子归并问题,规划的方向是顺推。先考虑含二堆石子的N个子序列（各子序列分别从第堆、第堆、第N堆数起，顺时针数堆）的合并方案f，f，fN，c，c，cN， 然后考虑含三堆石子的个子序列（各子序列分别从第堆、第堆、第堆数起，顺时针数堆）的合并方案f，f，fN，c，c，cN， 依次类推，直至考虑了含N堆石子的N个子序列（各子序列分别从第堆、第堆、 、第N堆数起，顺时针数N堆）的合并方案f，N，f，N，fN，Nc，N，c，N，cN，N 最后，在子序列，N，N，N，N中，选择得分总和（f值）最小（或最大）的一个子序列i，N（iN）

45、，由此出发倒推合并过程。,91,4.8 典型问题石子归并问题,动态规划方程和倒推合并过程 对子序列(i,j)最后一次合并,其得分为第i堆数起,顺时针数j堆的石子总数t. 被合并的两堆石子是由子序列(i,k)和(i+k-1)modn+1, j-k) (1kj-1)经有限次合并形成的. 为了求出最佳合并方案中的k值,我们定义一个动态规划方程: 当求最大得分总和时 f(i,j)=maxf(i,k)+f(x,j-k)+t 1kj-1 c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t 2jn,1in 当求最小得分总和时 f(i,j)=minf(i,k)+f(x,j-k)+t1kj-1

46、c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t2jn,1in 其中x=(i+k-1)modn+1,即第i堆数起,顺时针数k+1堆的堆序号.,92,4.8 典型问题石子归并问题,fi,j,ci,j,f(i,j)=minf(i,k)+f(x,j-k)+t 1kj-1 c(i,j)=k f(i,j)=f(i,k)+f(x,j-k)+t 2jn,1in x=(i+k-1)modn+1,93,4.8 典型问题石子归并问题,94,4.8 典型问题石子归并问题,上述倒推过程,可由一个print(子序列)的递归算法描述: void print(i,j) if(j!=1) /*继续倒推合并过

47、程*/ print(i,c(i,j); /*倒推子序列1的合并过程*/ print(i+c(i,j)-1)%(n+1),j-c(i,j); /*倒推子序列2的合并过程*/ for(k=1;kN;k+) if(第K堆石子未从圈内去除) if(K=i | K=X) 置第K堆石子待合并标志; else 第K堆石子未被合并; 第i堆石子数第i堆石子数+第X堆石子数; 将第X堆石子从圈内去除; ,95,4.8 典型问题石子归并问题,96,4.9 最优二叉搜索树(略),1、二叉搜索树,是一棵二元树，或者为空，或者每个结点含有一个可比较大小的数据元素。并且： （1）若它的左子树不空，则左子树上所有节点的值均

48、小于它的根节点的值； （2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值； （3 它的左、右子树也分别为二叉排序树 注：树中所有结点互异,97,4.9 最优二叉搜索树,查找过程： (1)若T是空树，则搜索失败，否则： (2)若x等于T的根结点的数据域之值，则查找成功；否则： (3)若x小于T的根结点的数据域之值，则搜索左子树；否则： (4)查找右子树。,2、在二叉搜索树T中查找标识符x,98,4.9 最优二叉搜索树,设S=x1,x2,.,xn是一个有序集，且x1x2.xn。表示有序集S的二叉搜索树，利用二叉树的结点来存储有序集中的元素。二叉搜索树的叶结点是形如(xi，xi+1)

49、的开区间。在表示S的二叉搜索树中搜索一个元素x，返回的结果有两种情形： 在二叉搜索树的内结点中找到x=xi。 在二叉搜索树的叶结点中确定x(xi，xi+1)。 设第一种情形中找到元素x=xi的概率为bi；在第二种情形中确定x(xi，xi+1)的概率为ai。并约定x0=-，xn+1=+。显然有,搜索成功与不成功的概率,表示内部结点，包含了关键码集合中的某一个关键码；表示外部结点，代表了造成搜索失败的各关键码间隔中的不在关键码集合中的关键码。 在每两个外部结点之间必然存在一个内部结点。,99,4.9最优二叉搜索树,(a0,b1,a1,.,bn,an)称为集合S的存取概率分布。 在表示S的二叉搜索树T中，设存储元素xi的结点深度为ci；存储叶结点(xj,xj+1)的结点深度为dj，则,上式表示在二叉搜索树T中作一次搜索所需要的平均比较次数。P又称为二叉搜索树T的平均路长。在一般情况下，不同的二叉树的平均路长是不相同的。,100,二叉搜索树的期望耗费示例,101,4.9 最优二叉搜索树,最优二叉搜索树问