1、用多边形顶点的逆时针序列表示凸多边形，用多边形顶点的逆时针序列表示凸多边形，即即P=v0,v1,vn-1表示具有表示具有n条边的凸多边形。条边的凸多边形。若若vi与与vj是多边形上不相邻的是多边形上不相邻的2个顶点，则线段个顶点，则线段vivj称为多边形的称为多边形的一条弦一条弦。弦将多边形分割成。弦将多边形分割成2个个多边形多边形vi,vi+1,vj和和vj,vj+1,vi多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交是将多边形分割成互不相交的三角形的弦的集合的三角形的弦的集合T。给定凸多边形给定凸多边形P P，以及定义在由多边形的边和，以及定义在由多边形的边和弦组成的三角形上的权
2、函数弦组成的三角形上的权函数w w。要求确定该凸。要求确定该凸多边形的三角剖分，使得该三角剖分中多边形的三角剖分，使得该三角剖分中诸三角诸三角形上权之和为最小。形上权之和为最小。问题的提出：问题的提出：三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二一个表达式的完全加括号方式相应于一棵完全二叉树，称为叉树，称为表达式的语法树表达式的语法树。例如，完全加括号的矩阵连乘积例如，完全加括号的矩阵连乘积(A(A1 1(A(A2 2A A3 3)(A)(A4 4(A(A5 5A A6 6)所相应的语法树所相应的语法树如图如图(a)(a)所示。所示。语法树中的每一个语法树中的每一个叶结
3、点表示表达式中的叶结点表示表达式中的一个原子一个原子。在语法树中，若一结点有一个。在语法树中，若一结点有一个表示表达式表示表达式El的左子树，以及一个表示表的左子树，以及一个表示表达式达式Er的右子数，则以该结点为根的子树的右子数，则以该结点为根的子树表示表达式表示表达式（El，Er）。因此，有因此，有n个原子的完全加括号表达式对应于个原子的完全加括号表达式对应于唯一的一棵有唯一的一棵有n个叶结点的语法数。个叶结点的语法数。凸多边形凸多边形vv0 0,v,v1 1,v vn-1n-1 的三角剖分也可以用的三角剖分也可以用语法树表示。例如，图语法树表示。例如，图(b)(b)中凸多边形的三中凸多边
4、形的三角剖分可用图角剖分可用图(a)(a)所示的语法树表示。所示的语法树表示。矩阵连乘积中的每个矩阵矩阵连乘积中的每个矩阵A Ai i对应于凸对应于凸(n+1)(n+1)边形中的一条边边形中的一条边v vi-1i-1v vi i。三角剖分中的一条。三角剖分中的一条弦弦v vi iv vj j，ijij，对应于矩阵连乘积，对应于矩阵连乘积Ai+1:jAi+1:j。凸多边形的最优三角剖分问题有凸多边形的最优三角剖分问题有最优子结构性质最优子结构性质。事实上，若凸事实上，若凸(n+1)(n+1)边形边形P=vP=v0 0,v,v1 1,v,vn-1n-1 的最优的最优三角剖分三角剖分T T包含三角形
5、包含三角形v v0 0v vk kv vn n，1kn-11kn-1，则，则T T的的权为权为3 3个部分权的和：三角形个部分权的和：三角形v0vkvnv0vkvn的权，子多边的权，子多边形形vv0 0,v,v1 1,v,vk k 和和vvk k,v,vk+1k+1,v,vn n 的权之和。可以的权之和。可以断言，由断言，由T T所确定的这所确定的这2 2个子多边形的三角剖分也个子多边形的三角剖分也是最优的。因为若有是最优的。因为若有vv0 0,v,v1 1,v,vk k 或或vvk k,v,vk+1k+1,v,vn n 的更小权的三角剖分将导致的更小权的三角剖分将导致T T不是不是最优三角剖
6、分的矛盾。最优三角剖分的矛盾。定义定义tijtij，1ijn1i0,wi0,Vi0,1=i=n,要求找出一个要求找出一个n元元0-1向量向量（x1,x2,xn),xi0,1,1=i=n,使得使得而且而且达到最大。达到最大。0-10-1背包问题是一个背包问题是一个特殊的整数规划问题特殊的整数规划问题。niiixv1maxnixCxwiniii1,1,01设所给设所给0-1背包问题的子问题背包问题的子问题递归关系：递归关系：nikkkxvmaxnkixjxwknikkk,1,0的最优值为的最优值为m(im(i，j)j)，即，即m(im(i，j)j)是背包容量为是背包容量为j j，可选择，可选择物品
7、为物品为i i，i+1i+1，n n时时0-10-1背包问题的最优值。由背包问题的最优值。由0-10-1背背包问题的最优子结构性质，可以建立计算包问题的最优子结构性质，可以建立计算m(im(i，j)j)的递归的递归式如下式如下iiiiwjwjjimvwjimjimjim0),1(),1(),1(max),(nnnwjwjvjnm00),(精品课件精品课件！精品课件精品课件！二叉搜索树二叉搜索树（1 1）若它的左子树不空，则左子树上）若它的左子树不空，则左子树上所有所有节点的值节点的值均小于均小于它的根节点的值；它的根节点的值；（2 2）若它的右子树不空，则右子树上）若它的右子树不空，则右子树上所有所有节点的值节点的值均大于均大于它的根节点的值；它的根节点的值；（3 3 它的左它的左、右子树也分别为二叉排序树右子树也分别为二叉排序树45125333724100619078在随机的情况下，二叉查找树的平均查找长度和 是等数量级的nlog
