递归、分治、动态规划、回溯.ppt

《递归、分治、动态规划、回溯.ppt》由会员分享，可在线阅读，更多相关《递归、分治、动态规划、回溯.ppt（73页珍藏版）》请在三一办公上搜索。

1、递归、分治、动态规划与回溯,回溯、递归、递推是计算机算法中基础内容，范围极其广泛。,递归与分治基本原理,对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,递归与分治基本原理,递归与分治基本原理,递归的概念,直接或间接地调用自身的算法称为递归算法。用函数自身给出定义的函数称为递归函数。由分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像

2、一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许多高效算法。,递推与递归,递归与递推表面看来是相逆的过程，其实也是相似的，最终的计算都是从小算到大。递推的使用环境要求高导致了递推的高效性，递推没有重复计算什么数据，保持了高效。递归大多数会重复计算子问题，导致时间浪费，所以一般不要使用过深的递归，甚至会空间溢出。,但是也不能说递推好，递归差，因为递归却能解决很多递推做不到的事情，在某些特定的环境下也能实现高效，并且递归容易使用。我们要就事论事！,斐波那契数列（Fibonacci），对于f（30），如果使用递归则需要运行1664079次，而递推只需30次就可以了，速度悬殊。,递归：long

3、f(long n)if i3 then return 1;else f(i-1)+f(i-2);,递推：long f(long n)a 1:=1;a 2:=1;for i:=1 to n-2 dof i+2:=f i+f i+1;,递推与递归,1.经典递归例如Hanoi塔问题：经典的递归，原问题包含子问题。有些问题或者数据结构本来就是递归描述的，用递归做很自然。2.递归与递推，数学式关系利用递归的思想建立递推关系，如由兔子生崽而来的fibonacci数列。但递推由于没有返回段，因此更为简单，有时可以直接用循环实现。3.分治等以大化小算法不少分治方法是源于递归思想，或是递归分解+合并处理。,递归

4、的应用范围,递归的应用范围,4.回溯 规模较小的问题用回溯解决比较自然。注意递归前后要保证现场的保存和恢复，即正确的转化问题。5.动态规划 动态规划的子问题重叠性质与递归有某种相似之处。递归+动态修改查表是一种不错的建立动态规划模型的方法。树、图、排序等符合递归子问题思想的结构 树、图等数据结构本身就是递归结构，因此当然是使用递归来处理。7.其他 例如排列组合等，很杂的。,递归举例,例1 阶乘函数阶乘函数可递归地定义为：,边界条件,递归方程,边界条件与递归方程是递归函数的二个要素，递归函数只有具备了这两个要素，才能在有限次计算后得出结果。,例2 Fibonacci数列无穷数列1，1，2，3，5

5、，8，13，21，34，55，被称为Fibonacci数列。它可以递归地定义为：,边界条件,递归方程,第n个Fibonacci数可递归地计算如下：public static int fibonacci(int n)if(n=1)return 1;return fibonacci(n-1)+fibonacci(n-2);,递归举例,例3 Ackerman函数当一个函数及它的一个变量是由函数自身定义时，称这个函数是双递归函数。Ackerman函数A(n，m)定义如下：,递归举例,例3 Ackerman函数前2例中的函数都可以找到相应的非递归方式定义：,但本例中的Ackerman函数却无法找到非递归

6、的定义。,递归举例,例3 Ackerman函数A(n，m)的自变量m的每一个值都定义了一个单变量函数：M=0时，A(n,0)=n+2M=1时，A(n,1)=A(A(n-1,1),0)=A(n-1,1)+2，和A(1,1)=2故A(n,1)=2*nM=2时，A(n,2)=A(A(n-1,2),1)=2A(n-1,2)，和A(1,2)=A(A(0,2),1)=A(1,1)=2，故A(n,2)=2n。M=3时，类似的可以推出M=4时，A(n,4)的增长速度非常快，以至于没有适当的数学式子来表示这一函数。,递归举例,例4 排列问题设计一个递归算法生成n个元素r1,r2,rn的全排列。,设R=r1,r2

7、,rn是要进行排列的n个元素，Ri=R-ri。集合X中元素的全排列记为perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素；当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。,例5 整数划分问题将正整数n表示成一系列正整数之和：n=n1+n2+nk，其中n1n2nk1，k1。正整数n的这种表示称为正整数n的划分。求正整数n的不同划分个数。例如正整数6有如下11种不同的划分：6；5+1；4+2，4+1+1

8、；3+3，3+2+1，3+1+1+1；2+2+2，2+2+1+1，2+1+1+1+1；1+1+1+1+1+1。,递归举例,(2)q(n,m)=q(n,n),mn;最大加数n1实际上不能大于n。因此，q(1,m)=1。,(1)q(n,1)=1,n1;当最大加数n1不大于1时，任何正整数n只有一种划分形式，即,(4)q(n,m)=q(n,m-1)+q(n-m,m),nm1;正整数n的最大加数n1不大于m的划分由n1=m的划分和n1n-1 的划分组成。,(3)q(n,n)=1+q(n,n-1);正整数n的划分由n1=n的划分和n1n-1的划分组成。,例5 整数划分问题前面的几个例子中，问题本身都具有

9、比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,递归举例,例5 整数划分问题前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,递归举例,例6 Hanoi塔问题设a,b,c是3个

10、塔座。开始时，在塔座a上有一叠共n个圆盘，这些圆盘自下而上，由大到小地叠在一起。各圆盘从小到大编号为1,2,n,现要求将塔座a上的这一叠圆盘移到塔座b上，并仍按同样顺序叠置。在移动圆盘时应遵守以下移动规则：规则1：每次只能移动1个圆盘；规则2：任何时刻都不允许将较大的圆盘压在较小的圆盘之上；规则3：在满足移动规则1和2的前提下，可将圆盘移至a,b,c中任一塔座上。,递归举例,在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。,当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。当n1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较

11、小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。,例6 Hanoi塔问题,public static void hanoi(int n,int a,int b,int c)if(n 0)hanoi(n-1,a,c,b);move(a,b);hanoi(n-1,c,b,a);,思考题：如果塔的个数变为a,b,c,d四个，现要将n个圆盘从a全部移动到d，移动规则不

12、变，求移动步数最小的方案。,递归举例,递归小结,优点：结构清晰，可读性强，而且容易用数学归纳法来证明算法的正确性，因此它为设计算法、调试程序带来很大方便。缺点：递归算法的运行效率较低，无论是耗费的计算时间还是占用的存储空间都比非递归算法要多。,分治法的基本步骤,divide-and-conquer(P)if(|P|=n0)adhoc(P);/解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for(i=1,i=k,i+)yi=divide-and-conquer(Pi);/递归的解各子问题 return merge(y1,

13、.,yk);/将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,分治法的复杂性分析,一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时

14、间，则有：,通过迭代法求得方程的解：,注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。,二分搜索技术,分析：如果n=1即只有一个元素，则只要比较这个元素和x就可以确定x是否在表中。因此这个问题满足分治法的第一个适用条件,分析：比较x和a的中间元素amid，若x=amid，则x在L中的位置就是mid；如果xai，同理我们只要在amid的后面查找x即可。无论是在前面还是后面查找x，其方法都和在a中查找x一样，只不

15、过是查找的规模缩小了。这就说明了此问题满足分治法的第二个和第三个适用条件。,分析：很显然此问题分解出的子问题相互独立，即在ai的前面或后面查找x是独立的子问题，因此满足分治法的第四个适用条件。,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。分析：,该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题;分解出的子问题的解可以合并为原问题的解；分解出的各个子问题是相互独立的。,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法：public static int

16、binarySearch(int a,int x,int n)/在 a0 amiddle)left=middle+1;else right=middle-1;return-1;/未找到x,算法复杂度分析：每执行一次算法的while循环，待搜索数组的大小减少一半。因此，在最坏情况下，while循环被执行了O(logn)次。循环体内运算需要O(1)时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn)。,思考题：给定a，用二分法设计出求an的算法。,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,a,b,c,d,复杂度分析T(n

17、)=O(n2)没有改进,X=Y=X=a 2n/2+b Y=c 2n/2+d XY=ac 2n+(ad+bc)2n/2+bd,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:,XY=ac 2n+(ad+bc)2n/2+bd 为了降低时间复杂度，必须减少乘法的次数。XY=ac 2n+(a-c)(b-d)+ac+bd)2n/2+bdXY=ac 2n+(a+c)(b+d)-ac-bd)2n/2+bd,复杂度分析T(n)=O(nlog3)=O(n1.59)较大的改进,细节问题：两个XY的复杂度都是O(nlog3)，但考虑到a+c,b+d可能得到

18、m+1位的结果，使问题的规模变大，故不选择第2种方案。,大整数的乘法,请设计一个有效的算法，可以进行两个n位大整数的乘法运算,小学的方法：O(n2)效率太低分治法:O(n1.59)较大的改进更快的方法?,如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。最终的，这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生。该方法也可以看作是一个复杂的分治算法，对于大整数乘法，它能在O(nlogn)时间内解决。是否能找到线性时间的算法？目前为止还没有结果。,Strassen矩阵乘法,A和B的乘积矩阵C中的元素Ci,j定义为:,若依此定义来计算A和

19、B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的 个元素所需的计算时间为O(n3),传统方法：O(n3),Strassen矩阵乘法,使用与上例类似的技术，将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵。由此可将方程C=AB重写为：,传统方法：O(n3)分治法:,由此可得：,复杂度分析T(n)=O(n3)没有改进,Strassen矩阵乘法,传统方法：O(n3)分治法:,为了降低时间复杂度，必须减少乘法的次数。,复杂度分析T(n)=O(nlog7)=O(n2.81)较大的改进,Strassen矩阵乘法,传统方法：O(n3)分治法:O(n2.81)

20、更快的方法?,Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或矩阵的更好算法。在Strassen之后又有许多算法改进了矩阵乘法的计算时间复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。,快速排序,private static int partition(int p,int r)int i=p,j=r+1;Comparable x=ap;/将=x的元素交换到左边区域/将 0);if(i=j)break;M

21、yMath.swap(a,i,j);ap=aj;aj=x;return j;,初始序列,j-;,5,7,5,2,6,8,i+;,5,6,5,2,7,8,j-;,5,2,5,6,7,8,i+;,完成,5,2,5 6 7,8,private static int randomizedPartition(int p,int r)int i=random(p,r);MyMath.swap(a,i,p);return partition(p,r);,快速排序,快速排序算法的性能取决于划分的对称性。通过修改算法partition，可以设计出采用随机选择策略的快速排序算法。在快速排序算法的每一步中，当数组还

22、没有被划分时，可以在ap:r中随机选出一个元素作为划分基准，这样可以使划分基准的选择是随机的，从而可以期望划分是较对称的。,最坏时间复杂度：O(n2)平均时间复杂度：O(nlogn)辅助空间：O(n)或O(logn)稳定性：不稳定,最接近点对问题,给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。,最接近点对问题,如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-

23、d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中有S中的点，则此点就是S1中最大点。因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。,能否在线性时间内找到p3,q3？,最接近点对问题,下面来考虑二维的情形。,选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。能否在线性时间内找到p,q？,最接近点对问题,考虑P

24、1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的P2中的点一定落在一个d2d的矩形R中由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6n/2=3n个候选者,能否在线性时间内找到p3,q3？,证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则dista

25、nce(u,v)d。这与d的意义相矛盾。,为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。,最接近点对问题,最接近点对问题,public static double cpair2(S)n=|S|;if(n m2.d1=cpair2(

26、S1);d2=cpair2(S2);3.dm=min(d1,d2);,4.设P1是S1中距垂直分割线l的距离在dm之内的所有点组成的集合；P2是S2中距分割线l的距离在dm之内所有点组成的集合；将P1和P2中点依其y坐标值排序；并设X和Y是相应的已排好序的点列；5.通过扫描X以及对于X中每个点检查Y中与其距离在dm之内的所有点(最多6个)可以完成合并；当X中的扫描指针逐次向上移动时，Y中的扫描指针可在宽为2dm的区间内移动；设dl是按这种扫描方式找到的点对间的最小距离；6.d=min(dm,dl);return d;,复杂度分析T(n)=O(nlogn),设计一个满足以下要求的比赛日程表：(1

27、)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,循环赛日程表,设计一个满足以下要求的比赛日程表：(1)每个选手必须与其他n-1个选手各赛一次；(2)每个选手一天只能赛一次；(3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选手设计的比赛日程表来决定。递归地用对选手进行分

28、割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,动态规划思想,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。,T(n),动态规划思想,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。,动态规划算法的基本要素,一、最优子结构,矩阵连乘计算次序问题的最优解包含着其子问

29、题的最优解。这种性质称为最优子结构性质。在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。这种性质称为子问题的重叠性质。动态规划算法，对每

30、一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,m0private static int lookupChain(int i,int j)if(mij 0)return mij;if(i=j)return 0;int u=lookupChain(i+1,j)+pi-1*pi

31、*pj;sij=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;,最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk，是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。例如，序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X

32、和Y的公共子序列。给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk，则(1)若xm=yn，则zk=xm=yn，且zk-1是xm-1和yn-1的最长公共子序列。(2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。(3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最优子结构性质。,子问题的递归结构,由最长公共子序列问题的最优子

33、结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中，Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,Algorithm lcsLength(x,y,b)1:mx.length-1;2:ny.length-1;3:ci0=0;c0i=0;4:for(int i=1;i=cij-1)10:cij=ci-1j;11:b

34、ij=2;12:else 13:cij=cij-1;14:bij=3;,构造最长公共子序列Algorithm 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);System.out.print(xi);else if(bij=2)lcs(i-1,j,x,b);else lcs(i,j-1,x,b);,算法的改进,在算法lcsLength和lcs中，可进一步将数组b省去。事实上，数组元素cij的值仅由ci-1j-1，ci-1j和cij-1这3个数组元素的值所确定。对于给定的数组元素cij，可以不借助于

35、数组b而仅借助于c本身在时间内确定cij的值是由ci-1j-1，ci-1j和cij-1中哪一个值所确定的。如果只需要计算最长公共子序列的长度，则算法的空间需求可大大减少。事实上，在计算cij时，只用到数组c的第i行和第i-1行。因此，用2行的数组空间就可以计算出最长公共子序列的长度。进一步的分析还可将空间需求减至O(min(m,n)。,凸多边形最优三角剖分,用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形

36、的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。,三角剖分的结构及其相关问题,一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示。矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦

37、vivj，ij，对应于矩阵连乘积Ai+1:j。,最优子结构性质,凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。,最优三角剖分的递归结构,定义tij，1ijn为凸子多边形vi-1,vi,vj的最优三角剖分所对应的权函数值，即其最优值。为方便起

38、见，设退化的多边形vi-1,vi具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t1n。tij的值可以利用最优子结构性质递归地计算。当j-i1时，凸子多边形至少有3个顶点。由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置。由此，tij可递归地定义为：,多边形游戏,多边形游戏是一个单人玩的游戏，开始时有一个由n个顶点构成的多边形。每个顶点被赋予一个整数值，每条边被赋予一个运算符“+”或“*”。所有边依

39、次用整数从1到n编号。游戏第1步，将一条边删除。随后n-1步按以下方式操作：(1)选择一条边E以及由E连接着的2个顶点V1和V2；(2)用一个新的顶点取代边E以及由E连接着的2个顶点V1和V2。将由顶点V1和V2的整数值通过边E上的运算得到的结果赋予新顶点。最后，所有边都被删除，游戏结束。游戏的得分就是所剩顶点上的整数值。问题:对于给定的多边形，计算最高得分。,最优子结构性质,在所给多边形中，从顶点i(1in)开始，长度为j(链中有j个顶点)的顺时针链p(i，j)可表示为vi，opi+1，vi+j-1。如果这条链的最后一次合并运算在opi+s处发生(1sj-1)，则可在opi+s处将链分割为2

40、个子链p(i，s)和p(i+s，j-s)。设m1是对子链p(i，s)的任意一种合并方式得到的值，而a和b分别是在所有可能的合并中得到的最小值和最大值。m2是p(i+s，j-s)的任意一种合并方式得到的值，而c和d分别是在所有可能的合并中得到的最小值和最大值。依此定义有am1b，cm2d(1)当opi+s=+时，显然有a+cmb+d(2)当opi+s=*时，有minac，ad，bc，bdmmaxac，ad，bc，bd 换句话说，主链的最大值和最小值可由子链的最大值和最小值得到。,图像压缩,图像的变位压缩存储格式将所给的象素点序列p1,p2,pn,0pi255分割成m个连续段S1,S2,Sm。第i

41、个象素段Si中(1im)，有li个象素,且该段中每个象素都只用bi位表示。设 则第i个象素段Si为设，则hibi8。因此需要用3位表示bi,如果限制1li255，则需要用8位表示li。因此，第i个象素段所需的存储空间为li*bi+11位。按此格式存储象素序列p1,p2,pn，需要 位的存储空间。图像压缩问题要求确定象素序列p1,p2,pn的最优分段，使得依此分段所需的存储空间最少。每个分段的长度不超过256位。,图像压缩,设li，bi，是p1,p2,pn的最优分段。显而易见，l1，b1是p1,pl1的最优分段，且li，bi，是pl1+1,pn的最优分段。即图像压缩问题满足最优子结构性质。设si

42、，1in，是象素序列p1,pn的最优分段所需的存储位数。由最优子结构性质易知：其中,算法复杂度分析：由于算法compress中对k的循环次数不超这256，故对每一个确定的i，可在时间O(1)内完成的计算。因此整个算法所需的计算时间为O(n)。,电路布线,在一块电路板的上、下2端分别有n个接线柱。根据电路设计，要求用导线(i,(i)将上端接线柱与下端接线柱相连，如图所示。其中(i)是1,2,n的一个排列。导线(i,(i)称为该电路板上的第i条连线。对于任何1i(j)。电路布线问题要确定将哪些连线安排在第一层上，使得该层上有尽可能多的连线。换句话说，该问题要求确定导线集Nets=(i,(i),1i

43、n的最大不相交子集。,记。N(i,j)的最大不相交子集为MNS(i,j)。Size(i,j)=|MNS(i,j)|。(1)当i=1时，(2)当i1时，2.1 j(i)。此时，。故在这种情况下，N(i,j)=N(i-1,j)，从而Size(i,j)=Size(i-1,j)。2.2 j(i)，(i,(i)MNS(i,j)。则对任意(t,(t)MNS(i,j)有ti且(t)(i)。在这种情况下MNS(i,j)-(i,(i)是N(i-1,(i)-1)的最大不相交子集。2.3 若，则对任意(t,(t)MNS(i,j)有 ti。从而。因此，Size(i,j)Size(i-1,j)。另一方面，故又有Size

44、(i,j)Size(i-1,j)，从而Size(i,j)=Size(i-1,j)。,电路布线,(1)当i=1时(2)当i1时,流水作业调度,n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。流水作业调度问题要求确定这n个作业的最优加工顺序，使得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。,分析：直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。设全部作业的集合

45、为N=1，2，n。SN是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。,流水作业调度,设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时，安排作业(2)，(n)所需的时间。记S=N-(1)，则有T=T(S,b(1)。,证明：事实上，由T的定义知TT(S,b(1)。若TT(S,b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。则(1)，(2)，(n)是N的一个调

46、度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S,b(1)。这就证明了流水作业调度问题具有最优子结构的性质。,由流水作业调度问题的最优子结构性质可知，,Johnson不等式,对递归式的深入分析表明，算法可进一步得到简化。设是作业集S在机器M2的等待时间为t时的任一最优调度。若(1)=i,(2)=j。则由动态规划递归式可得:T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij)其中，,如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。,流

47、水作业调度的Johnson法则,交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji)其中，当作业i和j满足Johnson不等式时，有由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题，必存在最优调度，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意ij有由此可知，所有满足Johnson法则的调度均为最优调度。,算法描述,流水作业调度问题的Johnson算法(1)令(2)将N1中作业依ai的非减序排序；将

48、N2中作业依bi的非增序排序；(3)N1中作业接N2中作业构成满足Johnson法则的最优调度。,算法复杂度分析：算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。,0-1背包问题,给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为C。问应如何选择装入背包的物品，使得装入背包中物品的总价值最大?0-1背包问题是一个特殊的整数规划问题。,0-1背包问题,设所给0-1背包问题的子问题,的最优值为m(i，j)，即m(i，j)是背包容量为j，可选择物品为i，i+1，n时0-1背包问题的最优值。由0-1背包问题的最优子结构性质，可以建立计算m(i，j)的递归式如下。,算法复杂度分析：从m(i，j)的递归式容易看出，算法需要O(nc)计算时间。当背包容量c很大时，算法需要的计算时间较多。例如，当c2n时，算法需要(n2n)计算时间。,