递归和分治动态规划贪心算法回溯法分支限界法随机算法课件

University of Science and Technology of China2024/7/271算法设计复习算法设计复习内容提要：p算法设计思想回顾（递归和分治、动态规划、贪心算法、回溯法、分支限界法、随机算法）p 经典例子讲解算法设计策略已学过的算法设计策略：已学过的算法设计策略：递归和分治动态规划贪心算法 回溯法 分支限界法 随机算法2024/7/272University of Science and Technology of China3l基本思想：把一个规模大的问题划分为规模较小的子问题，然后分而治之，最后合并子问题的解得到原问题的解。l步骤：分割原问题：求解子问题：合并子问题的解为原问题的解。l在分治法中，子问题一般是相互独立的，因此，经常通过递归调用算法来求解子问题。Sch1-4 分治法University of Science and Technology of China4Sch1-4 分治法分治法所能解决的问题一般具有以下几个特征：分治法所能解决的问题一般具有以下几个特征：该问题的规模缩小到一定的程度就可以容易地解决；该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质利用该问题分解出的子问题的解可以合并为该问题的解；该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。University of Science and Technology of China5例1：最近点对问题l为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数 x1,x2,xn。最接近点对即为这n个实数中相差最小的2个实数。l假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。l递归地在S1和S2上找出其最接近点对p1,p2和q1,q2，并设d=min|p1-p2|,|q1-q2|，S中的最接近点对或者是p1,p2，或者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。l能否在线性时间内找到p3,q3？Sch1-4 分治法University of Science and Technology of China6Sch1-4 分治法如果S的最接近点对是p3,q3，即|p3-q3|d，则p3和q3两者与m的距离不超过d，即p3(m-d,m，q3(m,m+d。u由于在S1中，每个长度为d的半闭区间至多包含一个点（否则必有两点距离小于d），并且m是S1和S2的分割点，因此(m-d,m中至多包含S中的一个点。由图可以看出，如果(m-d,m中有S中的点，则此点就是S1中最大点。u因此，我们用线性时间就能找到区间(m-d,m和(m,m+d中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。University of Science and Technology of China7Sch1-4 分治法选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=mind1,d2，S中的最接近点对或者是d，或者是某个p,q，其中pP1且qP2。能否在线性时间内找到p,q？University of Science and Technology of China8Sch1-4 分治法考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)d。满足这个条件的P2中的点一定落在一个d2d的矩形R中u由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。u因此，在分治法的合并步骤中最多只需要检查6n/2=3n个候选者能否在线性时间内找到p,q？证明:将矩形R的长为2d的边3等分，将它的长为d的边2等分，由此导出6个(d/2)(2d/3)的矩形。若矩形R中有多于6个S中的点，则由鸽舍原理易知至少有一个(d/2)(2d/3)的小矩形中有2个以上S中的点。设u，v是位于同一小矩形中的2个点，则distance(u,v)d。这与d的意义相矛盾。University of Science and Technology of China9l为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。l因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。Sch1-4 分治法University of Science and Technology of China10Sch1-4 分治法double cpair2(S)n=|S|;if(n 2)return;1、m=S中各点x间坐标的中位数;构造S1和S2；/S1=pS|x(p)m2、d1=cpair2(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;University of Science and Technology of China11p基本思想：将待求解问题分解成若干个子问题,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。通过保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。p基本步骤：找出最优解的性质，并刻划其结构特征。递归地定义最优值。以自底向上的方式计算出最优值。根据计算最优值时得到的信息，构造最优解。Sch1-4 动态规划University of Science and Technology of China12p基本要素：最优子结构性质：原问题的最优解包含着子问题的最优解，可以通过反证法来证明问题具有最优子结构性质。重叠子问题：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。p问题的关键在于构造子问题空间。一个经验性规则就是，尽量保持这个空间简单，然后在需要时再扩充它。Sch1-4 动态规划University of Science and Technology of China13例子2：凸多边形最优三角剖分问题l用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。l若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。l多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。l在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。Sch1-4 动态规划Sch1-4 动态规划p凸多边形最优三角剖分的问题是：凸多边形最优三角剖分的问题是：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。可以定义三角形上各种各样的权函数，如定义：(vivjvk)=|vivj|+|vivk|+|vkvj|其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分University of Science and Technology of China15三角形剖分的结构及其相关问题p一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图(a)所示。p凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示。p矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。Sch1-4动态规划University of Science and Technology of China16最优子结构性质：l凸多边形的最优三角剖分问题有最优子结构性质。l证明：事实上，若凸(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不是最优三角剖分的矛盾。Sch1-4 动态规划法University of Science and Technology of China17递归结构：l定义tij，1in时，顶点i+s实际编号为(i+s)mod n。按上述递推式计算出的mi,n,1即为游戏首次删去第i条边后得到的最大得分。Sch1-4 动态规划University of Science and Technology of China24基本要素：p贪心选择性质：所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。p最优子结构性质：问题的最优解包含其子问题的最优解。*对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。Sch1-4 贪心算法University of Science and Technology of China25l例5：最小生成树问题 设G=(V,E)是无向连通带权图，即一个网络。E中每条边(v,w)的权为cvw。如果G的子图G是一棵包含G的所有顶点的树，则称G为G的生成树。生成树上各边权的总和称为该生成树的耗费。在G的所有生成树中，耗费最小的生成树称为G的最小生成树。网络的最小生成树在实际中有广泛应用。例如，在设计通信网络时，用图的顶点表示城市，用边(v,w)的权cvw表示建立城市v和城市w之间的通信线路所需的费用，则最小生成树就给出了建立通信网络的最经济的方案。Sch1-4 贪心算法University of Science and Technology of China26p最小生成树性质：设G=(V,E)是连通带权图，U是V的真子集。如果(u,v)E，且uU，vV-U，且在所有这样的边中，(u,v)的权cuv最小，那么一定存在G的一棵最小生成树，它以(u,v)为其中一条边。这个性质有时也称为MST性质。用贪心算法设计策略可以设计出构造最小生成树的有效算法。本节介绍的构造最小生成树的Prim算法和Kruskal算法都可以看作是应用贪心算法设计策略的例子。尽管这2个算法做贪心选择的方式不同，它们都利用了上面的最小生成树性质：Sch1-4 贪心算法University of Science and Technology of China27l证明：假设G的任何一棵最小生成树都不含边(u,v)。将边(u,v)添加到G的一棵最小生成树T上，将产生含有边(u,v)的圈，并且在这个圈上有一条不同于(u,v)的边(u,v)，使得uU,vV-U。如下图所示，将边(u,v)删去，得到G的另一棵生成树T。由于cuv=cu v，所以T的耗费=T的耗费。于是，T是一颗含有边(u,v)的最小生成树，这与假设矛盾。Sch1-4 贪心算法UuuVvv含边(u,v)的圈University of Science and Technology of China28lPrime算法 设G=(V,E)是连通带权图，V=1,2,n，算法思想为：首先置S=1，然后，只要S是V的真子集，就作如下的贪心选择：选取满足条件iS，jV-S，且cij最小的边，将顶点j添加到S中。这个过程一直进行到S=V时为止。在这个过程中选取到的所有边恰好构成G的一棵最小生成树。Sch1-4 贪心算法Void Prime(n,c)T=;S=1;while(S!=V)(i,j)=i S且j V-S的最小权边；T=T U(i,j);S=S U j;University of Science and Technology of China29Sch1-4 贪心算法 利用最小生成树性质和数学归纳法容易证明，上述算法中的边集合T始终包含G的某棵最小生成树中的边。因此，在算法结束时，T中的所有边构成G的一棵最小生成树。例如，对于右图中的带权图，按Prim算法选取边的过程如下页图所示。University of Science and Technology of China30Sch1-4 贪心算法University of Science and Technology of China31 在上述Prim算法中，还应当考虑如何有效地找出满足条件iS,jV-S，且权cij最小的边(i,j)。实现这个目的的较简单的办法是设置2个数组closest和lowcost。在Prim算法执行过程中，先找出V-S中使lowcost值最小的顶点j，然后根据数组closest选取边(j,closestj)，最后将j添加到S中，并对closest和lowcost作必要的修改。用这个办法实现的Prim算法所需的计算时间为Sch1-4 贪心算法University of Science and Technology of China32pKruskal算法 Kruskal算法构造G的最小生成树的基本思想是：首先将G的n个顶点看成n个孤立的连通分支。将所有的边按权从小到大排序。然后从第一条边开始，依边权递增的顺序查看每一条边，并按下述方法连接2个不同的连通分支：当查看到第k条边(v,w)时，如果端点v和w分别是当前2个不同的连通分支T1和T2中的顶点时，就用边(v,w)将T1和T2连接成一个连通分支，然后继续查看第k+1条边；如果端点v和w在当前的同一个连通分支中，就直接再查看第k+1条边。这个过程一直进行到只剩下一个连通分支时为止。Sch1-4 贪心算法University of Science and Technology of China33l例如，对前面的连通带权图，按Kruskal算法顺序得到的最小生成树上的边如下图所示。Sch1-4 贪心算法University of Science and Technology of China34时间复杂度：当图的边数为e时，Kruskal算法所需的时间是 ：l当 时，Kruskal算法比Prim算法差；l当 时，Kruskal算法却比Prim算法好得多。Sch1-4 贪心算法University of Science and Technology of China谢谢！2024/7/2738Q&A