算法设计思想回顾(递归和分治、动态规划、贪心算法、回溯法、分支限界

UniversityofScienceandTechnologyofChina主讲人：吕敏Email:{[e-mail]}Spring2012，USTC算法基础UniversityofScienceandTechnologyofChina2020/11/162算法设计复习内容提要：算法设计思想回顾（递归和分治、动态规划、贪心算法、回溯法、分支限界法、随机算法）经典例子讲解UniversityofScienceandTechnologyofChina算法设计策略已学过的算法设计策略：递归和分治动态规划贪心算法回溯法分支限界法随机算法2020/11/163UniversityofScienceandTechnologyofChina4基本思想：把一个规模大的问题划分为规模较小的子问题，然后分而治之，最后合并子问题的解得到原问题的解。步骤：①分割原问题：②求解子问题：③合并子问题的解为原问题的解。在分治法中，子问题一般是相互独立的，因此，经常通过递归调用算法来求解子问题。Sch1-4分治法UniversityofScienceandTechnologyofChina5Sch1-4分治法分治法所能解决的问题一般具有以下几个特征：①该问题的规模缩小到一定的程度就可以容易地解决；②该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质③利用该问题分解出的子问题的解可以合并为该问题的解；④该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好。UniversityofScienceandTechnologyofChina6例1：最近点对问题为了使问题易于理解和分析，先来考虑一维的情形。此时，S中的n个点退化为x轴上的n个实数x1,x2,…,xn。最接近点对即为这n个实数中相差最小的2个实数。假设我们用x轴上某个点m将S划分为2个子集S1和S2，基于平衡子问题的思想，用S中各点坐标的中位数来作分割点。递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2}，并设d=min{|p1-p2|,|q1-q2|}，S中的最接近点对或者是{p1,p2}，或者是{q1,q2}，或者是某个{p3,q3}，其中p3∈S1且q3∈S2。能否在线性时间内找到p3,q3？Sch1-4分治法UniversityofScienceandTechnologyofChina7Sch1-4分治法如果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-d,m]中至多包含S中的一个点。由图可以看出，如果(m-d,m]中有S中的点，则此点就是S1中最大点。因此，我们用线性时间就能找到区间(m-d,m]和(m,m+d]中所有点，即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。UniversityofScienceandTechnologyofChina8Sch1-4分治法选取一垂直线l:x=m来作为分割直线。其中m为S中各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设d=min{d1,d2}，S中的最接近点对或者是d，或者是某个{p,q}，其中p∈P1且q∈P2。能否在线性时间内找到p,q？UniversityofScienceandTechnologyofChina9Sch1-4分治法考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选者，则必有distance(p，q)＜d。满足这个条件的P2中的点一定落在一个d×2d的矩形R中由d的意义可知，P2中任何2个S中的点的距离都不小于d。由此可以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6×n/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的意义相矛盾。UniversityofScienceandTechnologyofChina10为了确切地知道要检查哪6个点，可以将p和P2中所有S2的点投影到垂直线l上。由于能与p点一起构成最接近点对候选者的S2中点一定在矩形R中，所以它们在直线l上的投影点距p在l上投影点的距离小于d。由上面的分析可知，这种投影点最多只有6个。因此，若将P1和P2中所有S中点按其y坐标排好序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中每一点最多只要检查P2中排好序的相继6个点。Sch1-4分治法UniversityofScienceandTechnologyofChina11Sch1-4分治法doublecpair2(S){n=|S|;if(n2)return;1、m=S中各点x间坐标的中位数;构造S1和S2；//S1={p∈S|x(p)=m},S2={p∈S|x(p)m}2、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);returnd;}时间复杂度：T(n)=O(nlogn)44)()2/(2)1()(nnnOnTOnTUniversityofScienceandTechnologyofChina12基本思想：将待求解问题分解成若干个子问题,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。通过保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。基本步骤：①找出最优解的性质，并刻划其结构特征。②递归地定义最优值。③以自底向上的方式计算出最优值。④根据计算最优值时得到的信息，构造最优解。Sch1-4动态规划UniversityofScienceandTechnologyofChina13基本要素：①最优子结构性质：原问题的最优解包含着子问题的最优解，可以通过反证法来证明问题具有最优子结构性质。②重叠子问题：递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。问题的关键在于构造子问题空间。一个经验性规则就是，尽量保持这个空间简单，然后在需要时再扩充它。Sch1-4动态规划UniversityofScienceandTechnologyofChina14例子2：凸多边形最优三角剖分问题用多边形顶点的逆时针序列表示凸多边形，即P={v0,v1,…,vn-1}表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形{vi,vi+1,…,vj}和{vj,vj+1,…vi}。多边形的三角剖分是将多边形分割成互不相交的三角形的弦的集合T。在凸多边形P的一个三角剖分T中，各弦互不相交，且弦数已达到最大，即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角剖分中，恰好有n-3条弦和n-2个三角形。Sch1-4动态规划UniversityofScienceandTechnologyofChinaSch1-4动态规划凸多边形最优三角剖分的问题是：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数w。要求确定该凸多边形的三角剖分，使得即该三角剖分中诸三角形上权之和为最小。可以定义三角形上各种各样的权函数ω，如定义：ω(vivjvk)=|vivj|+|vivk|+|vkvj|其中，|vivj|是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分UniversityofScienceandTechnologyofChina16三角形剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积((A1(A2A3))(A4(A5A6)))所相应的语法树如图(a)所示。凸多边形{v0,v1,…vn-1}的三角剖分也可以用语法树表示。例如，图(b)中凸多边形的三角剖分可用图(a)所示的语法树表示。矩阵连乘积中的每个矩阵Ai对应于凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积A[i+1:j]。Sch1-4动态规划UniversityofScienceandTechnologyofChina17最优子结构性质：凸多边形的最优三角剖分问题有最优子结构性质。证明：事实上，若凸(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不是最优三角剖分的矛盾。Sch1-4动态规划法UniversityofScienceandTechnologyofChina18递归结构：定义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]可递归地定义为：Sch1-4动态规划法jijivvvwjktkitjitjkijki)}(]][1[]][[{min0]][[1UniversityofScienceandTechnologyofChina19例3：图像压缩问题图象的变位压缩存储格式将所给的象素点序列{p1,p2,…,pn},0≤pi≤255分割成m个连续段S1,S2,…,Sm。第i个象素段Si中(1≤i≤m)，有l[i]个象素,且该段中每个象素都只用b[i]位表示。设,则第i个象素段Si为设，则hib[i]8。因此需要用3位表示b[i],如果限制1l[i]255，则需要用8位表示l[i]。因此，第i个象素段所需的存储空间为l[i]*b[i]+11位。按此格式存