算法设计-第3章.ppt

第3章 动态规划 学习要点: 理解动态规划算法的概念。 掌握动态规划算法的基本要素 （1）最优子结构性质 （2）重叠子问题性质 掌握设计动态规划算法的步骤。 (1)找出最优解的性质，并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息，构造最优解。 通过应用范例学习动态规划算法设计策略。 （1）矩阵连乘问题； （2）最长公共子序列； （3）最大子段和 （4）凸多边形最优三角剖分； （5）多边形游戏； （6）图像压缩； （7）电路布线； （8）流水作业调度； （9）背包问题； （10）最优二叉有哪些信誉好的足球投注网站树。 动态规划基本步骤 找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。 由于子链p(i，s)和p(i+s，j-s)的合并方式决定了p(i，j)在op(i+s)处断开后的合并方式，在op(i+s)处合并后其值为 m=(m1)op[i+s](m2) (1)当op[i+s]=+时，显然有a+c≤m≤b+d 由链p( i,j)合并的最优性可推出子链p(i，s)和p(i+s，j-s)的最优性，且最大值对应子链的最大值，最小值对应子链的最小值。 (2)当op[i+s]=‘*’时，由于v[i]可取负整数，子链的最大值相乘未必能得到主链的最大值。但最大值一定在边界点达到，即 min{ac，ad，bc，bd}≤m≤max{ac，ad，bc，bd} 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。 综上可知，多边形游戏问题满足最优子结构性质。 2.递归求解 由前面的分析可知，为了求链合并的最大值，必须同时求子链合并的最大值和最小值。因此，在整个计算过程中，应同时计算最大值和最小值。 设m[i,j,0]是链p(i,j)合并的最小值，而m[i,j,1]是最大值。若最优合并在op[i+s]处将p(i,j)分为两个长度小于j的子链p(i,i+s)和p(i+s,j-s)，且从顶点i开始的长度小于j的子链的最大值和最小值均已经计算出。为了叙述方便，记 a=m[i,i+s,0] ???????????????????????? b=m[i,i+s,1] ???????????????????????? c=m[i+s,j-s,0] ???????????????????????? d=m[i+s,j-s,1] (1)当op[i+s]=+时， ???????????????????????m[i,j,0]=a+c ?????????????????????? m[i,j,1]=b+d (2)当op[i+s]=*时， ??????????????????????? m[i,j,0]=min{ac,ad,bc,bd} ??????????????????????? m[i,j,1]=max{ac,ad,bc,bd} ???????? 综合(1)和(2)，将p(i,j)在op[i+s]处断开的最大值记为maxf(i,j,s)，最小值记为minf(i,j,s)，则 a+c?????????????????????????????? op[i+s]=+ ??????? minf(i,j,s)={??? min{ac,ad,bc,bd}?????????? op[i+s]=* ??????? ???????????????????????????? b+d??????????????????????????????? op[i+s]=+? ????? maxf(i,j,s)=｛ max{ac,ad,bc,bd}????????? op[i+s]=* ???????? 由于多边最优断开位置s有1≤s≤j-1的j-1种情况，由此可知 ?????????m[i,j,0]=min{minf(i,j,s)}??????? 1≤i,j≤n??????????? 1≤s＜j?? ?????? m[i,j,1]=max{maxf(i,j,s)}??????? 1≤i,j≤n??????????? 1≤s＜j?? 初始边界显然为 ?????????? m[i,1,0]=v[i]????????????????? 1≤i≤n ?????????? m[i,1,1]=v[i]????????????????? 1≤ i≤n ???????? 由于多边形是封闭的，在上面的计算中，当i+sn时，顶点i+s实际编号为(i+s)mod n。按上述递推式计算出的m[i,n,1]即为首次删去第i条边后得到的最大