递归与分治策略(三)

分治法的基本思想

分治法的基本思想是将一个规模为n的问题分解为k个规模较小的子问题,这些子问题互相独立且与原问题相同。递归地解这些问题,然后将各子问题的解合并得到原问题的解,它的一般算法设计模式如下:

divide-and-conquer(P)
{
    if(|P|<=n0) adhoc(P);  
    for(i=1;i<=k;i++)//divida P into smaller subinstances P1,P2,...,PK;
        yi=divide-and-conquer(Pi);
    return merge(y1,y2,...,yk);
}

这确实是一段不太容易看懂的伪代码,不要着急现在来解释一下这段代码究竟做了什么。divide-and-conquer是分治法的英文表达,|P|表示问题P的规模,n0表示一个阈值,表示当问题P的规模不超过n0时,问题已经很容易解出,不必再继续分解。adhoc(P)是该分治法中的基本子算法,用于直接解小规模的问题P。当P的规模不超过n0时,直接用算法adhoc(P)求解。算法merge(y1,y2,…,yk)是该分治法中的合并子算法,用于将P的子问题P1,P2,…,Pk的解y1,y2,…,yk合并为P的解。

 

 

发表评论

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