Machine World | Math World

记录实验过程

【算法设计与分析】递归与分治策略(二)

【基本思想】

    将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。

【适用条件】

该问题的规模缩小到一定的程度就可以容易地解决;

该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;

利用该问题分解出的子问题的解可以合并为该问题的解;

该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题;

【基本步骤】

分治法的三个步骤:

(1) 分解(Divide):

    将原问题分成成一系列子问题;

(2) 求解(Conquer):

    递归地解各个子问题。若子问题足够小,则直接求解;

(3) 合并(Combine):

    将子问题的结果合并成原问题的解

【设计模式】

divide-and-conquer(P){
    if(|P| <= n0){
        adhoc(P); //解决小规模问题
    }
    divide P into smaller subinstances P1,P2, ...Pk //分解子问题
    for(i = 1; j <= k; i++){
        yi = divide-and-conquer(Pi); //递归求解子问题
    }
    return merge(y1,...,yk);   //合并子问题
}

【启发式规则】

平衡子问题:

    在用分治法设计算法时,最好使子问题的规模大致相同。也就是将一个问题划分成大小相等的k个子问题(通常k=2),这种使子问题规模大致相等的做法是出自一种平衡(Balancing)子问题的思想,它几乎总是比子问题规模不等的做法要好。

独立子问题:

    各子问题之间相互独立,这涉及到分治法的效率,如果各子问题不是独立的,则分治法需要重复地解公共的子问题。

【典型情况】

《【算法设计与分析】递归与分治策略(二)》

【复杂度分析】

一个分治法将规模为n的问题分成k个规模为n/m的子问题去解. 设分解阀值n0=1, 且解规模为1的问题耗费1个单位时间, 再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间. 用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间, 则有:

\(T(n) = \begin{cases} O(1) && n= 1\\ kT(n/m) + f(n) &&n > 1\end{cases} \)

注意:递归方程及其解只给出n等于m的方幂时T(n)的值,但是如果认为T(n)足够平滑,那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的,从而当mi≤n<mi+1时,T(mi)≤T(n)<T(mi+1)。

【应用举例】

Strassen矩阵乘法(分治、剪枝)[附Python源码]

【参考文献】

  • 2019年广西师范大学计算机与信息工程学院算法设计与分析课件[OL].李志欣教授.2019.01.01

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注