分治算法

分治算法演讲者：唐文武郑建丽分治算法1.基本概念2.基本思想3.基本步骤4.适用情况5.经典问题6.复杂性分析7.程序设计过程分治算法——基本概念什么是分治法？吃橙子问题：我们知道橙子的皮很难剥，所以通常会将橙子切开成N块，这样比吃一整个来说更加效率且方便。在计算机上，我们称这种方法为”分治法“。分治算法——基本概念分而治之精髓：“分”--将问题分解为规模更小的子问题；“治”--将这些规模更小的子问题逐个击破；“合”--将已解决的子问题合并，最终得出原问题的解；分治法的思想是“分而治之”，是一种很重要的算法。分治算法——基本概念对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。这种算法设计策略叫做分治法(divideandconquer)。分治算法——基本思想问题的提出现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？解决方法：暴力法?分治法？。。。分治算法——基本思想暴力法：将这些硬币2枚一组分为40组，每次只称一组硬币，若发现轻的则为假币，最坏情况下称40次才可找出假币。显然效率很低。。。分治算法——基本思想分治法1.方法一：仔细思考上面的分法比较一次只能排除2枚硬币，利用只有一枚假币的性质，我们试着改变一下方法：将所有硬币平均分为两组，每次称两组硬币，这样比较一次可排除一半硬币，最坏情况下只需称7次。显然每比较一次能排除的硬币越多越好还有更好的分法？分治算法——基本思想2.方法二：把所有的硬币尽量平均地分成三组，至少有两组硬币数是相同的，每次称相同的两组，这样每比较一次可排除约2/3的硬币数，最坏情况下只需称4次。分治算法——基本思想思考1，是不是分得越多越好？由暴力法得知显然不是2，如何分？尽量分成规模相同的N个子问题3，分到什么程度为止？子问题小到无法再分或者可以简单直接得进行求解分治算法——基本思想由分治法产生的子问题往往是原问题的较小模式，反复应用分治手段，使其规模不断缩小，最终很容易直接求出其解。如果原问题可分割成k个子问题，1k≤n，且这些子问题都可解并可利用这些子问题的解求出原问题的解，那么这种分治法就是可行的。分治算法——基本步骤分治法在每一层递归上由三个步骤组成：step1：分解(divide)：将原问题分解为若干规模较小、相互独立、与原问题形式相同的子问题。step2：解决(conquer)：若子问题规模较小，则直接求解；否则递归求解各子问题。step3：合并(combine)：将各子问题的解合并为原问题的解。分治算法——基本步骤它的一般算法设计范型如下：Divide-and-Conquer(P)1.if|P|≤n02.thenreturn(ADHOC(P))3.将P分解为较小的子问题P1,P2,...,Pk4.fori←1tok5.doyi←Divide-and-Conquer(Pi)△递归解决Pi6.T←MERGE(y1,y2,...,yk)△合并子问题7.return(T)分治算法——基本步骤分治算法——适用情况分治法所能解决的问题一般具有以下几个特征：1)问题规模缩小到一定的程度就可以容易地解决2)问题具有最优子结构性质。3)利用该问题分解出的子问题的解可以合并为该问题的解；4)子问题相互独立，即子问题之间不包含公共的子子问题。分治算法——经典问题1.求最值2.快速排序3.循环比赛4.棋盘覆盖分治算法——求最值问题：求一组数中的最大值和最小值。方法一：假设数据个数为n，存放在数组a[1...n]中，则遍历数组a[1...n]中的每个数，不断更新min和max，则最后得到的max和min即为数组的最大值和最小值分治算法——求最值方法一:该方法的时间复杂度为T(n)分治算法——求最值方法二：分治策略设计：把n（n2）个数据，不断进行二分，直到各组剩下两个元素或者不可再分，分别对各组求其最大值、最小值，再进行合并，合并时只要更新最大最小值即可，最后就可以得到全部元素的最大最小值。分治算法——求最值方法二：该算法复杂度T（logn）求第K大值？分治算法——快速排序问题：将一组数据按顺序排列，a[1...10]={6,1,2,7,9,3,4,5,10,8}解决思路：快速排序：首先选择一个基数，这里我们选择6，分别从初始序列“6,1,2,7,9,3,4,5,10,8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。最后基数6会将数列划分成左边的数小于6，右边的数大于6的两个子数组，分别对两个子数组进行递归求解，最后合并所有的解。分治算法——快速排序分治算法——快速排序分治算法——快速排序分治算法——快速排序快速排序该算法复杂度T（nlogn）如何用快速排序的思想求第K大值？分治算法——循环比赛问题：设有n支(n=2^m,这里m=3)编号为1到n的球队进行单循环比赛，计划在n-1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在n-1天内每个队都与不同的对手比赛。解决思路：这道题如果我们想要直接给出结果或用搜索算法来解似乎比较复杂，所以我们采用分治法来解。我们要设计一张8×8的比赛安排表a[1..8,1..8]，只需要设计出表的上半部分，即两张4×4的安排表a[1..4,1..4]和a[1..4,5..8]即可。之后，通过已经设计出来的表的左上角a[1..4,1..4]复制出表的右下角a[5..8,5..8]，通过右上角a[1..4,5..8]制出表的左下角a[5..8,1..4]。同样，任一张4×4的比赛安排表可以通过两张2×2的比赛安排表产生。继续直到两张1×1的比赛安排表，这是问题的最小规模，即可赋初值解决。分治算法——循环比赛安排结果：分治算法——棋盘覆盖问题：棋盘是一个有2k×2k（k≥1）个方格的棋盘，其中恰有一个方格残缺。用L型骨牌覆盖，在此覆盖中要求：1）两个L型骨牌不能重叠2）L型骨牌不能覆盖残缺方格，但必须覆盖其他所有的方格1）问题分解过程如下：以k=2时的问题为例，用二分法进行分解，得到的是如下图所示，用双线划分的四个k=1的棋盘。但要注意这四个棋盘，并不都是与原问题相似且独立的子问题。因为当图中的残缺方格在左上部时，第1个子问题与原问题相似，而右上角、左下角和右下角三个子棋盘（也就是图中标识为2、3、4号子棋盘），并不是原问题的相似子问题，自然也就不能独立求解了。当使用一个①号三格板（图中阴影）覆盖2、3、4号三个子棋盘的各一个方格后，如图所示，我们把覆盖后的方格，也看作是残缺方格（称为“伪”残缺方格），这时的2、3、4号子问题就是独立且与原问题相似的子问题了。分治算法——棋盘覆盖分治算法——棋盘覆盖4X4棋盘：分治算法——复杂性分析一个分治法将规模为n的问题分成k个规模为n／m的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：T（n）=kT(n/m)+f(n)分治算法——复杂性分析通过迭代法求得方程的解：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当m^i≤nm^(i+1)时，T(m^i)≤T(n)T(m^(i+1))分治算法——程序设计过程1、先找到最小问题规模时的求解方法2、然后考虑随着问题规模增大时的求解方法3、找到求解的递归函数式后（各种规模或因子），设计递归程序即可。分治算法谢谢！