[理学]算法设计与分析课件 第2章 递归与分治.pptVIP

73 将求解2k个选手的比赛日程问题划分为依次求解 21,22,…,2k个选手的比赛日程问题。 74 75 76 77 78 79 12 13 当n=1时，问题比较简单。此时，只要将编号为1的圆盘从塔座a直接移至塔座b上即可。 当n＞1时，需要利用塔座c作为辅助塔座。此时若能设法将n-1个较小的圆盘依照移动规则从塔座a移至塔座c，然后，将剩下的最大圆盘从塔座a移至塔座b，最后，再设法将n-1个较小的圆盘依照移动规则从塔座c移至塔座b。 由此可见，n个圆盘的移动问题可分为2次n-1个圆盘的移动问题，这又可以递归地用上述方法来做。由此可以设计出解Hanoi塔问题的递归算法如下。 在问题规模较大时，较难找到一般的方法，因此我们尝试用递归技术来解决这个问题。 14 由上图解，可将Hanoi(n) 的问题，分解为两个Hanoi(n-1) 的问题和一个Move单步操作。满足递归关系。建立递归： 当n=1时, Hanoi(1,A,B,C)=Move(1,A,B) 当n1时, Hanoi(n,A,B,C) = Hanoi(n-1,A,C,B) + Move(n,A,C) + Hanoi(n-1, B,A,C) 15 16 17 18 20 解决方法：在递归算法中消除递归调用，使其转化为非递归算法。 27 21 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，且各个子问题是相互独立的，即子问题之间不包含公共的子问题。 利用该问题分解出的子问题的解可以合并为该问题的解； 24 25 也就是将一个问题划分成大小相等的k个子问题（通常k＝2），这种使子问题规模大致相等的做法是出自一种平衡（Balancing）子问题的思想，它几乎总是比子问题规模不等的做法要好。 26 28 29 30 当然这样存储后，需要有类型转换的操作，不同语言转换的操作差别虽然较大，但都是利用数字字符的ASCII码进行的。其它的技巧和注意事项通过下面的例子来说明。本节只针对大 整数的计算进行讨论，对高精度实数的计算可以仿照进行。 32 移位相加---时间复杂性为O(n2) 33 34 为了降低时间复杂度，必须减少乘法的次数 35 传统的方法：O(n2) ?效率太低 分治法: O(n1.59) ü较大的改进 36 如果将大整数分成更多段，用更复杂的方式把它们组合起来，将有可能得到更优的算法。 这个思想导致了快速傅利叶变换(Fast Fourier Transform)的产生，该方法也可以看作是一个复杂的分治算法。 38 矩阵乘法是线性代数中最常见的运算之一，它在数值计算中有广泛的应用。 39 复杂性分析： 当n=2，则2个2阶方阵的乘积可以直接计算出来，共需8次乘法和4次加法。 当n2，可以将子矩阵分块，直到子矩阵的阶降为2。这就产生了一个分治降阶的递归算法。 于是：计算2个n阶方阵的乘积转化为计算8个n/2阶方阵的乘积和4个n/2阶方阵的加法。2个n/2×n/2矩阵的加法显然可以在O(n2)时间内完成。 40 提出了一种新算法来减少2个n/2阶方阵乘积的乘法次数。由传统的8次变为7次，但增加了加、减法的运算次数。 注意( 德国数学家)Strassen矩阵乘法目前还没有实际意义。当n =32时，显示出优越性。 42 分治法: O(n2.81) 当n=32，显示出优越性。 45 46 47 49 当k=0时覆盖它需要常数时间O(1); 当k0时,测试哪个子棋盘残缺以及形成3个残缺子棋盘需要O(1),覆盖4个残缺子棋盘需4次递归调用,共需时间4T(k－1)。 50 72 法3：线性时间选择： 选择问题 算法的时间复杂度分析 选择问题 应用专题四 几何问题中的分治法 最接近点对问题 凸包问题 问题描述： 设p1=(x1, y1), p2=(x2, y2), …, pn=(xn, yn)是平面上n个点构成的集合S，最近对问题就是找出集合S中距离最近的点对。 严格地讲，最接近点对可能多于一对，简单起见，只找出其中的一对作为问题的解。 最接近点对问题 最接近点对问题 简单应用 假设在一片金属上钻n 个大小一样的洞，如果洞太近，金属可能会断。若知道任意两个洞的最小距离，可估计金属断裂的概率。 这种最小距离问题实际上也就是距离最近的点对问题。 最接近点对问题 分析： 直接方法： 通过检查所有的n(n－1 ) / 2对点，并计算每一对点的距离，可以找出距离最近的一对点。 这种方法所需要的时间为O(