《算法设计与分析.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析.ppt（22页珍藏版）》请在三一办公上搜索。
1、,第2章 分治,棋盘覆盖,问题描述：在一个 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,棋盘覆盖,算法实现：当k1时，将 棋盘分割为4个 子棋盘(a)所示。特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如(b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘22。,棋
2、盘覆盖,复杂度分析T(n)=O(4k)渐进意义下的最优算法,分治算法总体思想,分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。对这k个子问题分别求解。如果子问题的规模仍然不够小，则再划分为k个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。,分治法总体思想,将求出的小规模的问题的解合并为一个更大规模的问题的解，自底向上逐步求出原来问题的解。,分治法的适用条件,利用分治法求解的问题，应同时满足如下4点要求：原问题在规模缩小到一定程度时可以很容易地求解 绝大多数问题都可以满足这一点，因为问题的计算复杂性一般是 随着问题规模的减
3、小而减小 原问题可以分解为若干个规模较小的同构子问题 这一点是应用分治法的前提，此特征反映了递归思想。满足该 求的问题通常称该问题具有最优子结构性质。各子问题的解可以合并为原问题的解 它决定了问题的求解可否利用分治法。如果这一点得不到保证 通常会考虑使用后面要讲的贪心法或动态规划法。原问题所分解出的各个子问题之间是相互独立的 这一条涉及到分治法的效率，如果各子问题是不独立的，则分治 法要做许多不必要的工作，对公共的子问题进行重复操作，此时 通常会考虑使用后面要讲的动态规划法。,分治法解决问题的步骤,利用分治法求解问题的算法通常包含如下几个步骤：分解(Divide)将原问题分解为若干个相互独立、
4、规模较小且与原问题形式相同 的一系列子问题。解决(Conquer)如果子问题规模小到可以直接被解决则直接求解，否则需要递归 地求解各个子问题。合并(Combine)将各个子问题的结果合并成原问题的解。有些问题的合并方法比较明显；有些问题的合并方法比较复杂，或者存在多种合并方案；有些问题的合 并方案不明显。究竟应该怎样合并，没有统一的模式，需要具体问题具体分析。,原问题应该分为多少个子问题才较适宜？各个子问题的规模应该怎样才为适当？这些问题很难存在一个统一的答案。实践证明，在用分治法设计算法时，最好使各子问题的规模大致相同。,分治法的复杂性分析,一个分治法将规模为n的问题分成k个规模为nm的子问
5、题去解。设分解阀值n0=1，且解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,Strassen矩阵乘法,问题描述：A和B的乘积矩阵C中的元素Ci,j定义为:,若依此定义来计算A和B的乘积矩阵C，则每计算C的一个元素Cij，需要做n次乘法和n-1次加法。因此，算出矩阵C的个元素所需的计算时间为O(n3),Strassen矩阵乘法,算法实现：传统方法：算法的时间复杂度分治法:,将矩阵A，B和C中每一矩阵都分块成4个大小相等的子矩阵
6、。由此可将方程C=AB重写为：,由此可得：,复杂度分析T(n)=O(n3)没有改进,Strassen矩阵乘法,算法实现：传统方法：算法的时间复杂度分治法:,为了降低时间复杂度，必须减少乘法的次数。,Strassen矩阵乘法,算法实现：传统方法：算法的时间复杂度：分治法:算法的时间复杂度：更快的方法？,在Strassen之后又有许多算法改进了矩阵乘法的计算时间 复杂性。目前最好的计算时间上界是 O(n2.376)是否能找到O(n2)的算法？目前为止还没有结果。Hopcroft和Kerr已经证明(1971)，计算2个矩阵的乘积，7次乘 法是必要的。因此，要想进一步改进矩阵乘法的时间复杂性，就不能
7、再基于计算22矩阵的7次乘法这样的方法了。或许应当研究或 矩阵的更好算法。,最接近点对问题,问题描述 给定平面上n个点的集合S，找其中的一对点，使得在n个点组成的所有点对中，该点对间的距离最小。,为了使问题易于理解和分析，先来考虑一维的情形。此时，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
8、,p2，或 者是q1,q2，或者是某个p3,q3，其中p3S1且q3S2。能否在线性时间内找到p3,q3？,如果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的解。
9、,能否在线性时间内找到p3,q3？,最接近点对问题,最接近点对问题,下面来考虑二维的情形,能否在线性时间内找到p,q？,选取一垂直线l:x=m来作为分割直线。其中m为S中 各点x坐标的中位数。由此将S分割为S1和S2。递归地在S1和S2上找出其最小距离d1和d2，并设 d=mind1,d2，S中的最接近点对或者是d，或者 是某个p,q，其中pP1且qP2。,最接近点对问题,能否在线性时间内找到p3,q3？,考虑P1中任意一点p，它若与P2中的点q构成最接近点对的候选 者，则必有distance(p，q)d。满足这个条件的P2中的点一定 落在一个d2d的矩形R中由d的意义可知，P2中任何2个S中
10、的点的距离都不小于d。由此可 以推出矩形R中最多只有6个S中的点。因此，在分治法的合并步骤中最多只需要检查6n/2=3n个候选 者,为了确切地知道要检查哪6个点，可以将p和P2中 所有S2的点投影到垂直线l上。由于能与p点一起 构成最接近点对候选者的S2中点一定在矩形中，所以它们在直线l上的投影点距p在l上投影点的 距离小于d。由上面的分析可知，这种投影点最 多只有6个。因此，若将P1和P2中所有S中点按其y坐标排序，则对P1中所有点，对排好序的点列作一次扫描，就可以找出所有最接近点对的候选者。对P1中 每一点最多只要检查P2中排好序的相继6个点。,最接近点对问题,最接近点对问题,复杂度分析T(n)=O(nlogn),名人问题,在一群人中寻找一个人，这个人被所有人认识，但他却不认识人群中的任何一个人,算法一：判断 是否为1，并且 是否为N 该算法的时间复杂度为：,名人问题,算法二：由N-1归纳出N个人的情况若N-1中没有名人，则只需判断 是否为1，并且 是否为N若N-1中有一个名人，则只需判断 是否为1，并且 是否为N 该算法的时间复杂度为：,在一群人中寻找一个人，这个人被所有人认识，但他却不认识人群中的任何一个人,名人问题,在一群人中寻找一个人，这个人被所有人认识，但他却不认识人群中的任何一个人,算法三：，若 则；若 则 该算法的时间复杂度为：,
