第3章 动态规划3

3.5凸多边形最优三角剖分多边形是平面上一条分段线性闭曲线。——由一系列首尾相接的直线段所组成的。若多边形的边除了连接顶点外没有别的交点，则称该多边形为一简单多边形。一个简单多边形将平面分成三个部分：内部；边界；外部用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}•多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小。问题的提出：三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图(a)所示。语法树中的每一个叶结点表示表达式中的一个原子。在语法树中，若一结点有一个表示表达式El的左子树，以及一个表示表达式Er的右子数，则以该结点为根的子树表示表达式（El，Er）。因此，有n个原子的完全加括号表达式对应于唯一的一棵有n个叶结点的语法数。凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示。•矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积A[i+1:j]。最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P={v0,v1,…,vn-1}的最优三角剖分T包含三角形v0vkvn，1≤k≤n-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形{v0,v1,…,vk}和{vk,vk+1,…,vn}的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有{v0,v1,…,vk}或{vk,vk+1,…,vn}的更小权的三角剖分将导致T不是最优三角剖分的矛盾。最优三角剖分的递归结构定义t[i][j]，1≤ij≤n为凸子多边形{vi-1,vi,…,vj}的最优三角剖分所对应的权函数值，即其最优值。为方便起见，设退化的多边形{vi-1,vi}具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t[1][n]。t[i][j]的值可以利用最优子结构性质递归地计算。当j-i≥1时，凸子多边形至少有3个顶点•由最优子结构性质，t[i][j]的值应为t[i][k]的值加上t[k+1][j]的值，再加上三角形vi-1vkvj的权值，其中i≤k≤j-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使t[i][j]值达到最小的位置。由此，t[i][j]可递归地定义为：jijivvvwjktkitjitjkijki)}(]][1[]][[{min0]][[1图像压缩计算机中常用象素点灰度值序列{p1,p2,…,pn}表示图象。其中pi,表示象素点i的灰度值。通常灰度值的范围是0~255。因此，需要用8位表示一个象素。图象的变位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm。第i个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。11][][ikklit设则第i个象素段Si为},,{][][1][ilititippS设1maxlog][][1][kilitkitiph则hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，则需要用8位表示l[i]。因此，第i个象素段所需的存储空间为l[i]*b[i]+11位。按此格式存储象素序列{p1,p2,…,pn}，需要mibilmi11][*][1位的存储空间。图象压缩问题要求确定象素序列{p1,p2,…,pn}的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。最优子结构性质设l[i]，b[i]，是{p1,p2,…,pn}的最优分段。显而易见，l[1]，b[1]是{p1,…,pl[1]}的最优分段，且l[i]，b[i]，是{pl[1]+1,…,pn}的最优分段。即图象压缩问题满足最优子结构性质。设s[i]，1≤i≤n，是象素序列{p1,…,pn}的最优分段所需的存储位数。由最优子结构性质易知：11)},1max(b*][{min][}256,min{1ikikkisisik1}{maxlog),bmax(kjkipji其中0-1背包问题问题的提出：给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?在选择装入背包的物品时，对每种物品I只有两种选择，即装入背包或不装入背包。不能将物品I装入背包多次，也不能只装入部分的物品i。因此，该问题称为0-1背包问题。此问题的形式化描述是，给定c0,wi0,Vi0,1=i=n,要求找出一个n元0-1向量（x1,x2,……,xn),xiЄ{0,1},1=i=n,使得而且达到最大。0-1背包问题是一个特殊的整数规划问题。niiixv1maxnixCxwiniii1},1,0{1设所给0-1背包问题的子问题递归关系：nikkkxvmaxnkixjxwknikkk},1,0{的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，…，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下iiiiwjwjjimvwjimjimjim0),1(}),1(),,1(max{),(nnnwjwjvjnm00),(最优二叉搜索树二叉搜索树（1）若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值；（3它的左、右子树也分别为二叉排序树45125333724100619078在随机的情况下，二叉查找树的平均查找长度和是等数量级的nlog