《算法设计与分析》PPT课件.ppt

第3章 动态规划,学习要点:理解动态规划算法的概念，动态规划vs递归分治 掌握动态规划算法的基本要素（1）最优子结构性质（2）重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。,通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题；（2）最长公共子序列；（3）最大子段和（4）凸多边形最优三角剖分；（5）(多边形游戏)（6）图像压缩；（7）背包问题；（8）最优二叉搜索树（9）(流水作业调度)（10）(电路布线),与分治法类似，其基本思想也是将待求解问题分解成若干个子问题;先求子问题解，然后合成原问题解,算法总体思想,大问题自上而下分解为子问题时，可以有多种分解方法。e.g.归并排序，矩阵连乘如果不同分解方法对应的子问题及其解不同，并导致合并后的原问题解不同，则需要考虑各种可能的分解方法。此时，无法直接采用分治法求解：e.g.矩阵连乘1.分解得到的子问题往往不是互相独立的，用分治法求解，需要计算的子问题数目太多，时间复杂性指数级别2.不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。E.g.Fibonacci数列计算，见后,与分治法区别,解决方法：保存已解决的子问题的答案，在需要时再找出已求得的答案，避免大量重复计算，得到多项式时间算法。利用表来记录子问题的答案，表的大小为多项式量级,T(n),示例：分治法 vs 动态规划,算法1基于递归分治 F(n)1.if(n=1 return 1;2.else return F(n-1)+F(n-2);问题：复杂性O(2n)原因：自上而下的递归计算过程中，一些子问题被多次重 复计算,Fibonacci数,F(6),F(4),F(3),F(2),F(1),F(0),F(2),F(1),F(0),F(1),F(5),F(4),F(3),F(2),F(1),F(0),F(1),F(3),F(2),F(2),F(1),F(0),F(1),F(1),F(0),子问题F(3)重复计算3次子问题F(2)重复计算5次,算法2：非递归的分治算法 保存子问题计算结果，只计算1次，以后碰到同样子问题时，直接调用已有结果F1(n)0.初始化数组 vi-1,0 i n 1.if vn 0 then 2.vn F1(n-1)+F1(n-2)3.return vn 数组vn:存储子问题结果的数组，vi：表示子问题Fi的解，vi=-1：表示子问题Fi还没有被计算问题：自上而下的计算过程中，避免了多次计算同一子问题，但又多次函数调用。每次调用需要花费较多时间用于参数传递和动态链接,算法3自下而上的迭代算法：动态规划算法F2(n)1.F(0)1;2.F(1)1;3.for i 2 to n do 4.Fi F1(i-1)+F1(i-2)/*问题-子问题间的递归公式 5.return Fn 特点：1）时间复杂性 O(n)2)自下而上，迭代计算 3)利用数组，保存中间（子问题）计算结果。每个子问题只计算一次,动态规划基本步骤,1.找出最优解的性质，刻划其结构特征-最优子结构特征2.递归地定义最优值：刻画原问题解与子问题解间的（数值）关系:表达式中存在寻优变量、最优目标值3.以自底向上的方式计算出各个子问题、原问题的最优值，并避免子问题的重复计算（记录已计算的子问题解）4.根据计算最优值时得到的信息，构造最优解,12,（1）矩阵连乘问题；乘法次数最少（2）最长公共子序列；公共子序列的长度最长（3）最大子段和子段中的数字之和最大（4）凸多边形最优三角剖分；三角形上权之和为最小（6）图像压缩；（9）背包问题；（10）最优二叉搜索树。（7）电路布线；（8）流水作业调度；作业运行时间最短（5）多边形游戏；,动态规划适宜解最优化问题,给定n个可连乘的矩阵A1,A2,An,连乘积A1A2,An。根据矩阵乘法结合律，可有多种不同计算次序，每种次序有不同的计算代价)数乘次数（取决于各矩阵的行、列数和计算次序）给定2个矩阵Api,pj,Bpj,pk,AB 为pi,pk矩阵，数乘次数pipjpk多个矩阵的连乘计算次序可用完全加括号来确定见下页,完全加括号的矩阵连乘积,这5种计算次序对应的计算代价分别为：16000,10500,36000,87500,34500,设有四个矩阵A,B,C,D,它们的维数分别是：总共有五种完全加括号的方式,举例,(40*30*5)+10*40*5+50*10*5,CD40,5,B(CD)10,5,A(B(CD)50,5,完全加括号的矩阵连乘积可递归地定义为：,（1）单个矩阵是完全加括号的；（2）矩阵连乘积 是完全加括号的，则 可 表示为2个完全加括号的矩阵连乘积 和 的乘积并加括号，即,加括号：矩阵连乘的计算次序,矩阵连乘问题,给定n个矩阵，其中 与 是可乘的，。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1，2，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。,方法1：穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序下的组合方式（即完全加括号的组合方式）为P(n)。每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)，关于P(n)的递推式如下：,穷举法,方法2：动态规划,将矩阵连乘积 简记为Ai:j，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全加括号方式为,计算量：Ai:k的计算量+Ak+1:j的计算量+Ai:k和Ak+1:j相乘的计算量,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。即：矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,分析最优解的结构 是否可用动态规划？,建立递归关系,设计算Ai:j，1ijn，所需要的最少数乘次数mi,j，则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n当ij时，断开位置k可以递归地定义mi,j为：,这里 的维数为,的位置只有 种可能,计算最优值,对于1ijn，不同的有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次 这也是该问题可用动态规划算法求解的又一显著特征。用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算：1）在计算过程中，保存已解决的子问题答案。每个子问题只计算一次 2）而在后面需要时只要简单查一下，从而避免大量的重复计算 最终得到多项式时间的算法,子问题Ai,i,1i n,void MatrixChain(int*p，int n，int*m，int*s)for(int i=1;i=n;i+)mii=0;/*规模为1的子问题的最优解 for(int r=2;r=n;r+)/*自下而上，从规模为r=2的子问题开始，依次计算规模为2、3、n的子问题 for(int i=1;i=n-r+1;i+)/*考察规模为r的共n-r+1个子问题 mi,j,j-i=r-1,int j=i+r-1;/*子问题左端点i，右端点j,规模r mij=0+mi+1j+pi-1*pi*pj;/*设置子问题mi,j的初始最优值 sij=i;/*记录子问题最优值的初始断点位置 for(int k=i+1;k j;k+)/*依次考察不同断点，计算mi,j最优值 int t=mik+mk+1j+pi-1*pk*pj;if(t mij)mij=t;sij=k;,输入参数,最优值,断开位置,子问题mi,j的递推比较,矩阵维度,1,n,子问题规模r：,2,n,r,左端点i：,1,(=n-1),n-r+1,右端点j：,2,j=i+r-1,n,i,子问题mi,j的断点k：,i+1,j,k,规模为r的子问题mi,j,共n-r+1个,mi,j,子问题：AiAi+1AkAj,r,断点,右端点,左端点,子问题规模/长度,共有 j-i个断点,示例,A2A3A4A5,1,1,6,6,1,2,5,6,1,3,4,6,1,4,3,6,1,5,2,6,1,6,算法复杂度分析：算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,27,总结矩阵连乘问题求解要素,1.原问题/子问题形式化表述2.（定量）最优化目标3.原问题/子问题最优解递归表达式,28,问题归结：原问题 子问题(问题规模更小),原问题:A(i,j),最优解:m(i,j),A(i,k),m(i,k),A(k,j),m(k,j),动态规划算法基本要素,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质 E.g.,这5种计算次序对应的计算代价分别为：16000,10500,36000,87500,34500 原问题最优解(最优次序)为:(A(B(CD),原问题最优解(最优次序)为:(A(B(CD)原问题分解为2个子问题：(A)(BCD)对子问题(BCD),其最优计算顺序仍然是(B(CD)，与原问题中计算顺序相同保证了：由子问题解合成原问题解时候，可以得到最优解,(ABCD),(A),(BCD),(B),(CD),(C),(D),(BCD),(B),(CD),(C),(D),全局最优,子问题最优,(BCD),(BC),(D),(B),(C),子问题非最优,10*40*30+10*30*5=13500,40*30*5+10*40*5=8000,如何证明一个问题具有最优子结构性质：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。最优子结构是问题能用动态规划算法求解的前提：利用此性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。,同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质 重复计算子问题，可能导致计算复杂度非多项式型E.g.1 E.g.2,用P54页递归算法，计算A1,4时的递归树,动态规划算法，对每一个子问题只解一次，子问题解保存在一个表格中；当再次需要解此子问题时，只是简单地用常数时间查看一下结果不同子问题个数一般随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，e.g.O(n3)，从而获得较高的解题效率（？未必，特别是当n很大时）问题具有重叠子问题性质是保证采用动态规划法可以获得更高效率（相比于分治、递归）的前提 反例：对第2章中排序问题，分治算法与动态规划法性能差别不大 3 2 7 9 1 6 8 5 1 2 3 5 6 7 8 9,递归分治法 vs 动态规划法,动态规划法带有全局最优化目标极大/极小化目标值；在子问题划分时，可以有多种划分方式，不同划分导致不同的目标值，因此需要在多种划分方式中选择使目标达到极值的划分方式分治法可以不涉及全局最优化目标，而且问题划分方式一般 是固定的E.g.动态规划-矩阵连乘:(ABCD)有以下3种分解/合成方法,(A)(BCD)(AB)(CD)(ABC)(D),最优目标,E.g.分治法-排序、大整数乘、矩阵乘 固定划分方式、无选择和最优化目标要求 1）3 2 7 9 1 6 8 5 1 2 3 5 6 7 8 9,2）,3）,递归分治法 vs 动态规划法（续）,分治法自上而下分解问题，有可能导致重复计算，e.g.斐波那契数列 动态规划自下而上合成问题，避免重复计算,备忘录方法,自上而下、递归、避免重复计算子问题的问题求解方法控制结构与直接递归方法的控制结构相同，为每个解过的子问题建立了备忘录以备需要时查看，避免对相同子问题的重复求解,E.g.矩阵连乘 矩阵mi,j初始化为0，表示子问题没有计算过,int LookupChain(int i，int j)/*求解问题 Ai,j=(Ai Ai+1 Aj)if(mij 0)return mij;/*Ai,j 如果以前以计算过，则 mi,j0，直接返回计算结果，避免重复计算 if(i=j)return 0;/*Ai,j=Ai,i,只有1个矩阵的最小规模子问题/*以下各步依次比较 k=i,j-1 等多种划分方法，求最优划分和最优值 int u=LookupChain(i，i)+LookupChain(i+1，j)+pi-1*pi*pj;sij=i;/*初始最佳划分点位置k=i for(int k=i+1;k j;k+)int t=LookupChain(i，k)+LookupChain(k+1，j)+pi-1*pk*pj;if(t u)u=t;sij=k;mij=u;return u;,Ai,i*Ai+1,j,Ai,k*Ak+1,j,备忘录 vs 动态规划,备忘录方法采用自上而下的递归分解法与动态规划法一样，避免子问题重复计算但由于采用递归，需要多次函数调用和参数传递，计算时间仍然比动态规划要大,最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xijE.g.对序列X=A，B，C，B，D，A，B，子序列Z=B，C，D，B，相应的递增下标序列为2，3，5，7。应用：网络内容审查,敏感字检查给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列,E.g.X=(A,B,C,B,D,A,B)Y=(B,D,C,A,B,A)子序列:Z1=(B,C,A),长度3 Z2=(B,C,B,A)，长度4,设计步骤1：判断最长公共子序列的结构是否具有最优子结构性质,设序列X(m)=x1,x2,xm和Y(n)=y1,y2,yn的最长公共子序列为Z(k)=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且Z(k-1)=z1,z2,zk-1 是X(m-1)=x1,x2,xm-1和Y(n-1)=y1,y2,yn-1的最长公共子序列,B,C,B,A,X(m):,C,B,A,Y(n):,B,B,C,B,X(m-1):,Y(n-1):,Z(k):,C,B,B,A,Z(k-1):,C,B,B,问题规模前缀,问题归结：原问题 子问题(问题规模更小),子问题最优解：Z(k-1)Z(k)Z(k)上述3种情况下，原问题最优解包括了子问题最优解！,前缀,3种情况：,(2)若xmyn且zkxm，则Z(k)是x(m-1)和Y(n)的最长公共子序列,B,C,B,A,C,B,A,B,B,C,B,C,B,B,A,X(m):,Y(n):,X(m-1):,Z(k):,问题规模前缀,A,(3)若xmyn且zkyn，则Z(k)是X(m)和y(n-1)的最长公共子序列,B,C,B,A,C,B,A,B,C,B,B,A,C,B,A,B,X(m):,Y(n-1):,Y(n):,Z(k):,问题规模 前缀,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀(i.e.子问题)的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,设计步骤2：子问题的递归结构,根据最优子结构性质，建立子问题最优值的递归关系。cij：序列X(i)和Y(j)的最长公共子序列的长度，X(i)=x1,x2,xi；Y(j)=y1,y2,yj。当i=0或j=0时，即其中1个序列为空，则空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其它情况下，由最优子结构性质可建立递归关系如下：,3种情况,计算最优值,对X(m)和Y(n)，总共有(mn)个不同的子问题，用动态规划算法自底向上地计算最优值，以提高算法效率。,void LCSLength(int m，int n，char*x，char*y，int*c，int*b),数组x*和y*：存储2个输入序列X(m)、Y(n)输出数组c：cij存储序列Xi、Yj的最长公共子序列的长度输出数组b：bij 记录cij的值是由哪个子问题得到的(3种情 况之一)，构造最长公共子序列时用到,X(i)=x1,x2,xi,1i m；Y(j)=y1,y2,yj,1j n；,void LCSLength(int m，int n，char*x，char*y，int*c，int*b)int i，j;for(i=1;i=cij-1)/*情况2 cij=ci-1j;bij=2;else cij=cij-1;/*情况3 bij=3;,每个数组单元的计算耗时O(1)，算法耗时：O(mn),算法LCSLength构造了数组bij，据此可递归构造出X(i)、Y(j)的最长公共子序列：,void LCS(int i，int j，char*x，int*b)if(i=0|j=0)return;if(bij=1)LCS(i-1,j-1,x,b);coutxi;/*第1种情况下，X(i)和Y(j)的最长公共子序列由X(i-1)和 Y(j-1)的解LCS(i-1,j-1,x,b)，加上位于最后的Xi 组成 else if(bij=2)LCS(i-1，j，x，b);else LCS(i，j-1，x，b);/*其它2种情况下，原问题解 等于子问题解,过程：从bm,n开始，依其值在数组b中搜索。1）bi,j=1,Xi和Yj的最长公共子序列由Xi-1和Yj-1的最长公共子序列，在尾部加上xi得到2）bi,j=2,Xi和Yj的最长公共子序列与Xi-1和Yj的的最长公共子序列相同3）bi,j=3,Xi和Yj的最长公共子序列与Xi和Yj-1的的最长公共子序列相同,算法中，每次递归调用使i或j减一，算法的计算时间为O(m+n),算法改进,在算法lcsLength和lcs中，可进一步将数组b省去：数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于数组b而仅借助于c本身在O(1)时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少：在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。,最大子段和,给定n个整数组成的序列a1,a2,an，求该序列形如，1i、j n,的子段和的最大值E.g.-2,11,-4,13,-5,-2，最大子段和=20 子段的起点i、长度、终点j不固定,一、简单算法 用数组a存储给定的n个整数a1,a2,an，注意到，采用2重循环，计算复杂性为O(n2),int MaxSum(int n,int*a，int bestj=j return sum,i:,1,n,i,j:,i,n,j,2重循环,55,问题采用二维表述MaxSum(i,j)，算法两重循环，导致二次项复杂性O(n2),自上而下分治算法,目标：进一步改进算法复杂性将序列a1:n分解为长度相等的2段a1:n/2和an/2+1:n，分别求出这2个子段的和，与a1:n的最大子段和相比，有三种情况1）a1:n/2与a1:n的最大子段和相同 最大子段落在前半部分2）an/2+1:n与a1:n的最大子段和相同 最大子段落在后半部分3）a1:n的最大子段和为，并且1i n/2,n/2+1 j n 最大子段横跨中点,对第3种情况，an/2和an/2+1 一定在最优子序列中：1)在a1:n/2中计算出S1=2)在an/2+1:n中计算出S2=3)最优值：S1+S2,an/2+1,*,*,an/2,i,j,leftsleftsum,rightsrightsum,int MaxSubSum(int*a,int left,int right)数组 子段左界 子段右界 int sum=0 if(left=right)sum=aleft 0?aleft:0;else int center=(left+right)/2;一分为二 int leftsum=MaxSubSum(a,left,center);求左子段最优值 int rightsum=MaxSubSum(a,center+1,right,);求右子段最优值 int s1=0;int lefts=0;for(int i=center;i=left;i-)/*假设为第3种情况，求左子段中的最优子段和值s1，由中点开始，自右向左搜索 lefts+=aj;if(leftss1)s1=lefts;,int s2=0;int rights=0;for(int i=center+1;i s2)s2=rights;sum=s1+s2;与第1、第2种情况比较 if(sumleftsum)sum=leftsum;if(sumrightsum)sum=rightsum;return sum int MaxSum(int n,int*a)return MaxSubSum(a,1,n),典型分治算法，递归式时间复杂性O(nlogn)问题采用二维表述MaxSubSum(left,right)，子问题解合并为原问题解时，扫描整个序列(第3种情况)，导致算法复杂性无法成为线性复杂性,最大子段问题动态规划算法,最优子结构性质：根据分治法，分析左右子段的s1、s2与原序列最优值间的关系需要知道段与子段之间最优值间的递归关系记 bj=,1 j n,1,j,bj=max,e.g.i=i2,i1,i2,i3,aj,j-1,n,1 j-1,1 j,bj一定累加了aj,需要构造一维问题表述，以降低复杂性,对所求最大子段和，有如下关系：将原问题转化为 对子问题bj的求极值,j 1,n,最多n个子问题,问题表述：2维表示：左端i，右端j 1维表示bj,左端j，利于降低算法复杂性,根据bj的定义，bj从右端aj处开始，一定包括了aj 当bj-10时，bj=bj-1+aj，当bj-1=0时,bj=aj故得到如下递归方程：,int MaxSum(int n,int*a)/*计算长度为n的最大子段和 int sum=0;b=0;for(int i=1;i 0)b+=ai;else b=ai;if(bsum)sum=b;return sum;,从序列左端第1个元素a1开始，自左向右，根据递归方程，逐步计算bi,1in。算法时间、空间复杂性均为O(n)。,-2,11,-4,13,-5,-2,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T三角形顶点：凸多边形顶点，边：多边形边、弦。最优值？！：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w（如欧氏距离）。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小 最优值。,示例：利用三角剖分，计算GSM/CDMA网络小区覆盖范围Voronoi图,三角剖分的结构及其相关问题,矩阵连乘/表达式的完全加括号方式问题与三角剖分问题具有相似性对应于相同理论模型，可相互归结(reduction):1）多个矩阵的排列顺序 对应于图中顶点排列顺序 2）序列中2个矩阵的加括号(Ai Al)对应于 顶点Ai 与Al间的边或弦表达式的完全加括号问题可以表示为一棵完全二叉树，称为表达式的语法树 e.g.完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。,三角剖分的结构及其相关问题,(A1(A2A3)(A4(A5A6),多出的一条边,n个矩阵连乘A1,n对应于凸(n+1)边形的三角剖分,凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示：1）树根节点对应V0V62）叶节点对应边Vi-1Vi3）非叶结点对应剖分多边形的弦边三角剖分与矩阵连乘积对应关系1.矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。2.三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。,最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质：根据顶点vk，将序列分为2部分v0,v1,vk、vk+1,v1,vn-1 若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，例如图(b)中的V3，则T的权为3个部分权的和：1）三角形v0vkvn的权，e.g.v0v3v62）子多边形v0,v1,vk权,e.g.v0v1v2v33)子多边形vk,vk+1,vn权,e.g.v3v4v5v6子问题划分：一分为三可以断言：由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。,最优三角剖分的递归结构,问题/子问题形式化表述：j-i+2个顶点组成的多边形Pvi-1,vi,vj,1i j n问题/子问题最优化目标 tij，1ijn,凸子多边形vi-1,vi,vj的最优三角剖分所对应的权函数值。为方便起见，设退化的多边形vi-1,vi具有权值0。原问题目标：凸(n+1)边形P的最优权值为t1n最小化,72,问题归结：原问题 子问题(问题规模更小),e.g.i=0,k=3,j=6,vk,(A1(A2A3)(A4(A5A6),子问题最优解：tvi-1,vk wvi-1vkvj tvk+1,vj,73,最优三角剖分的递归结构,tij的值利用最优子结构性质递归地计算:1)当j-i1时，凸子多边形至少有3个顶点。/*vi-1,vi,vj2)用顶点vk,进行子问题划分3）由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1,由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置由此，tij可递归地定义为：,e.g.,void MinWeightTriangulation(int n，Type*t,int*s)for(int i=1;i=n;i+)tii=0;for(int r=2;r=n;r+)for(int i=1;i=n-r+1;i+)int j=i+r 1 tij=ti+1j+w(i-1,i,j)sij=i;for(int k=i+1;k i+r-1;k+)int u=tik+tk+1j+W(i-1,k,j);if(utij)tij)=u;sij)=k;,时间复杂性O(n3)，空间复杂性O(n2),一分为三，断点k，找到更好的划分，并记录结果,t:记录子问题最优值s：记录子问题最优划分点,子问题vi-1、vi,、vj,子问题规模r=j-i+1,两重循环，自下而上，不同规模r的子问题,i-1,i,j,一分为二，断点i,多边形Pvi-1,vi,vj的划分：1.一分为二2.一分为三,76,时间复杂性较高O(n3)，当n较大时，算法运行时间较长,77,三角剖分的应用,1.Delaunay三角网格与光线追踪渲染 计算机图形学、计算机游戏、虚拟现实、图像处理2.Voronoi图 计算几何,78,Delaunay三角网格,图元对象的三角网格表示,三角形各边不相交,79,渲染：为场景中对象/图元增加颜色、亮度、纹理,游戏引擎与光线渲染,80,追踪渲染中的光线与对象/图元求交运算：判断不同方向的光线与场景中哪些图元、图元的哪部分相交，以便计算相交点处的光照强度，呈现出对象各部分的明亮分布。对场景中的（非规则、复杂）对象/图元，将其表面表示为Delaunay三角网格，追踪光线传播轨迹，计算1）入射光线与对象表面的相交位置：与哪个三角形相交、交点坐标2）入射光线角度和光照强度3）反射/折射光线角度和光照强度,(Eye),81,光线追踪与渲染关键点1：对象/图元表面的三角化表示，便于光线相交计算2：GPU运算,基于GPU的光线追踪渲染,82,E.g.利用三角剖分、Voronoi图计算基站覆盖范围、邻区层次,83,假设在草地中有N个火源点，同时点燃，并且以同样的速度向各个方向蔓延，那么燃烧熄灭处所形成的轨迹图便是Voronoi图。,计算几何学中的Voronoi图：,84,1）以基站为顶点，作出三角剖分图Delaunay三角网；2）计算各个三角形的垂心3）按空间逆序连接各个垂心，得到以各个垂心为母点的Voronoi图三角剖分图的对偶图,1）,2）,3）,三角形及其垂心,85,1个地区的实际GSM网络中，n：基站数目，超过10,000,特定小区及其四层邻区,全网基站V图（部分）,86,动态规划法的适用性！,动态规划导致的算法复杂性阶次有可能较高，e.g.，O(nk),k3，三角剖分算法O(n3),实际应用中，当问题规模很大时，e.g.n10,000，采用复杂性阶次较高的动态规划算法求解，运行时间过长，不具有实用性！E.g.见下页例子,87,Assume N=100,000 and processor speed is 1,000,000,000 operations per second(10亿次/秒，普通微机运算速度),88,假设单核微机 1.主频为 F=3GHz=3 109次/每秒 2.1个机器指令周期时长 t=1/F=(1/3)*10-9 秒 3.1条指令平均需要3个周期，则1条指令平均执行时间为(3/3)*10-9 秒CPU运算速度：每秒执行的指令数目=1/1条指令平均执行时间=(3/3)*109 条/秒=10亿条指令/秒 如果基于微机平台，采用动态规划三角剖分方法，计算基站Voronoi图，当基站数目n10,000时，运行时间2-3天，不可接受!,89,动态规划法的适用性,需要结合实际问题背景，优化算法，降低算法复杂性 分析递归表达式，避免过度搜索子问题的各种组合，根据启发式信息，选取某一种或少数某几种组合由求解全局最优解（最小、最大），改为求解全局次优解（比较小、比较大）E.g.三角剖分不需要搜索、比较Pvi-1,vi,vj中的每个vk，而是按照一定启发式信息，优先选取某个剖分点vk，e.g.vk=v3，避免最内层循环，将算法复杂性由O(n3)降为O(n2),.,穷搜,90,void MinWeightTriangulation(int n，Type*t,int*s)for(int i=1;i=n;i+)tii=0;for(int r=2;r=n;r+)/*第1层循环 for(int i=1;i=n-r+1;i+)/*第2层循环 int j=i+r 1 tii=ti+1j+w(i-1,i,j)sii=i;for(int k=i+1;k i+r-1;k+)int u=tik+tk+1j+W(i-1,k,j);if(utij)tij)=u;sij)=k;,利用启发式信息，在第2层循环内部，直接选取某个vk，避免第3层循环，算法时间复杂性降为O(n2),Z找到更好的划分，并记录结果,t:记录子问题最优值s：记录子问题最优划分点,子问题vi、vj,子问题规模r=j-i+1,自下而上，不同规模r的子问题,i,i+1,j,91,动态规划法的适用性,E.g.利用启发式（而非动态规划）三角剖分算法，得到以基站为顶点的Delaunay三角网有多种启发式构造方法在此基础上转换为Voronoi图，计算全网基站覆盖范围优点：算法运行时间可接受，e.g.4小时左右缺点：1.有可能无法完全满足三角剖分要求，极少部分的弦相交 2.Delaunay三角网上的各三角形边之和有可能非全局最小，而只是局部极小、比较小实际问题中，从实用性、适用性角度，tradeoff!between 算法解质量and 算法运行时间解质量：是否达到全局最大、最小,多边形游戏,多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。,10,22,9,4,15,36,27,v7,v1,v2,v3,v4,v5,v6,+,+,+,*,*,*,*,1,2,3,4,5,6,7,10,22,9,4,15,36,27,v7,v1,v2,v3,v4,v5,v6,+,+,*,*,*,*,2,3,4,5,6,7,Step1:,v7,Step2:,32,v17,10,22,9,4,15,36,27,v1,v2,v3,v4,v5,v6,+,+,*,*,*,*,2,3,4,5,6,7,Step2:,顶点减为6个,Step3:,v17,19,v34,Step3:,v17,32,9,36,27,v2,v5,v6,+,*,*,*,*,2,3,5,6,7,19,v34,顶点减为5个,多边形游戏,游戏的得分/最优值：最后所剩顶点上的整数值目标：最大化最后所剩顶点上的整数值问题解的结构：不同的删除边、合并顶点的顺序,最优子结构性质,问题形式化表述p(i，j)：在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j)可表示为：vi,opi+1,opi+j-2,vi+j-1,e.g.i=2,j=5 p(2,5):v2,*,v3,+,v4,*,v5,+,v6 op3+1=+,如果这条链的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链p(i，j)分割为2个子链：1）p(i,s)2）p(i+s,j-s)E.g.i=2,j=5,s=2,opi+2=op4=op3+1=+2)p(i,s)=p(2,2):v2,*,v33)p(i+s,j-s)=p(4,3):v4,*,v5,+,v6,P(i,s)与子链的关系由2条子链合并而成,p(i,s)=p(2,2)m1=36,p(i+s,j-s)=p(4,3)m2=max(36+27)*15,27+36*15,最优子结构性质,设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。e.g.p(i,s)=p(2,2),m1=9*4=36m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。e.g.p(i+s,j-s)=p(4,3),15*36+27 m2(27+36)*5 依此定义有am1b，cm2d,最优子结构性质,子链p(i，s)和p(i+s，j-s)的合并方式决定了p(i,j)在opi+s处断开后的合并方式，在opi+s处合并后其值为 m=(m1)opi+s(m