• 正在加载中...
  • 分治算法

    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。

    编辑摘要

    目录

    概念/分治算法 编辑


    分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。
    分治法解题的一般步骤

    (1)分解,将要解决的问题划分成若干规模较小的同类问题;
    (2)求解,当子问题划分得足够小时,用较简单的方法解决;
    (3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。

    当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。这就是分治策略的基本思想。

     

     

    算法设计模式/分治算法 编辑

     

    它的一般的算法设计模式如下: 
    Divide-and-conquer(P)  
    1. if |P|≤n0  
    2. then return(ADHOc(P))  
    3. 将P分解为较小的子问题 P1 ,P2 ,...,Pk  
    4. for i←1 to k  
    5. do yi ← Divide-and-conquer(Pi) △ 递归解决Pi  
    6. T ← MERGE(y1,y2,...,yk) △ 合并子问题  
    7. return(T) 
    其中|P|表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时,直接用算法ADHOc(P)求解。算法MERGE(y1,y2,...,yk)是该分治法中的合并子算法,用于将P的子问题P1 ,P2 ,...,Pk的相应的解y1,y2,...,yk合并为P的解。 
    根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。 
    分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显,有些问题合并方法比较复杂,或者是有多种合并方案,或者是合并方案不明显,如例5。究竟应该怎样合并,没有统一的模式,需要具体问题具体分析。 
    分治法的复杂性分析  
    从分治法的一般设计模式可以看出,用它设计出的程序一般是一个递归过程。因此,分治法的计算效率通常可以用递归方程来进行分析。为方便起见,设分解阈值n0=1,且算法ADHOC解规模为1的问题耗费1个单位时间。又设分治法将规模为n的问题分成k个规模为n/m的子问题去解,而且,将原问题分解为k个子问题以及用算法MERGE将k个子问题的解合并为原问题的解需用f(n)个单位时间。如果用T(n)表示该分治法Divide-and-conquer(P)解规模为|P|=n的问题P所需的计算时间,则有:  
    (1) T(1) = 1  
    T(n) = kT(n/m) + f(n)  
    算法复杂性中递归方程解的渐进阶的解法介绍的解递归方程迭代法,可以求得(1)的解: 
    logm(n-1)  
    (2)T(n) = n^(logmK) + ∑ (k^j)*f(n/(m^j))  
    j=0 
    注意,递归方程(1)及其解(2)只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常,  
    我们可以假定T(n)是单调上升的,从而当mi≤nn0 
    由于我们关心的一般是最坏情况下的计算时间复杂度的上界,所以用等于号(=)还是小于或等于号(≤)是没有本质区别的分治法的几种变形。 


     

    几种分治的方法/分治算法 编辑


     

    1.二分法 dichotomy一种每次将原问题分解为两个子问题的分治法,是一分为二的哲学思想的应用。这种方法很常用,由此法产生了许多经典的算法和数据结构。 


    2.分解并在解决之前合并法 divide and marriage before conquest一种分治法的变形,其特点是将分解出的子问题在解决之前合并。 


    3.管道传输分治法 pipelined divide and conquer一种分治法的变形,它利用某种称为“管道”的数据结构在递归调用结束前将其中的某些结果返回。此方法经常用来减少算法的深度

     

    举例/分治算法 编辑

       

     

                            

    分治算法分治算法

    国际象棋棋盘上某个位置的一只马它是否可能只走63步正好走过除起点外的其他63个位置各一次?试设计一个分治算法

     

    算法步骤:
    1 :从左上角起,给棋盘编号(1,1),(1,2),。。。。。。(8,8),计为集合qp。tracks记录走过的每个点. (可以想象为坐标(x,y))

    2:设起点为(1,1),记为 当前位置 cp,

    3:搜索所有可走的下一步,根据“马行日”的走步规则,可行的点的坐标是x坐标加减1,y坐标加减2,

    或是x加减2,y加减1; (例如起点(1,1),可计算出(1+1,1+2),(1+1,1-2),(1-1,1+2),(1-1,1-2),(1+2,1+1),(1+2,1-1),(1-2,1+1),(1-2,1-1) 共8个点), 如果没有搜到可行点,程序结束。

    4:判断计算出的点是否在棋盘内,即是否在集合qp中;判断点是否已经走过,即是否在集合tracts中,不在才是合法的点。(在上面的举例起点(1,1),则合法的下一步是(2,3)和 (3,2))

    5:将前一步的位置记录到集合tracts中,即tracts.add(cp);选择一个可行点,cp=所选择点的坐标。

    6:如果tracts里的点个数等于63,退出程序,否则回到步骤3继续执行。

    相关文献

    添加视频 | 添加图册相关影像

    互动百科的词条(含所附图片)系由网友上传,如果涉嫌侵权,请与客服联系,我们将按照法律之相关规定及时进行处理。未经许可,禁止商业网站等复制、抓取本站内容;合理使用者,请注明来源于www.baike.com。

    登录后使用互动百科的服务,将会得到个性化的提示和帮助,还有机会和专业认证智愿者沟通。

    互动百科用户登录注册
    此词条还可添加  信息模块

    WIKI热度

    1. 编辑次数:6次 历史版本
    2. 参与编辑人数:4
    3. 最近更新时间:2011-07-26 20:55:09

    互动百科

    扫码下载APP